The first midterm exam will cover chapters 2, 4, 5, 7, and 19-22. Even though chapters 21 and 22 also cover proofs of correctness, I will not be asking any questions about proof of correctness on this exam. Those types of questions will appear on a later exam.
Here are more specific topics you should review:
The exam will be a written, in-class exam. The exam is a closed book exam, but I will allow you to bring a single page of notes with you to the exam.
Here are some problems from the textbook that you can look at to review for the exam:
Chapter 4: 4.3-1, 4.5-1, 4.5-3
Random variables: 7.2-6
Graph problems: 20.3-11, 20.3-12, 20.4-2. 20.4-3, 21.1-1, 21.1-3
One of the problems on the exam will ask you to solve a problem involving graphs. Here is an example of a typical problem from a past exam:
A spanning tree in a fully connected graph is a set of edges that connects all of the vertices in the graph together and does not have any cycles. Explain how you could use the BFS algorithm to compute a spanning tree for a fully connected, undirected graph.
To answer these graph questions you will typically either explain how your algorithm works in words, or you can write some pseudocode for your algorithm.