Chapters for the first midterm

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.

Topics to review

Here are more specific topics you should review:

Exam format

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.

Review questions

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

Sample question

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.