Review questions for Prelim 1

The first prelim in CS 4820 will take place on Thursday, February 24, from 7:30 to 9pm, in Baker Lab 200. The prelim will be a closed-book exam covering stable matching, greedy algorithms, divide-and-conquer, and dynamic programming. These topics constitute Chapters 1, 4, 5, and 6 of the textbook. Students are responsible for any of the material covered in the lectures or assigned readings, excluding the first lecture of the semester and the lecture on Dijkstra's algorithm. Students are not responsible for any sections of the book that were not among the assigned readings, even if those sections occur as part of Chapters 4, 5, or 6. However, the unassigned sections of those chapters often constitute good study material for reinforcing the concepts that you learned in the assigned readings, so browsing the unassigned sections of Chapters 4, 5, and 6 is recommended as a study strategy.

For additional practice, you are invited to try solving the following problems from the textbook. You are welcome to ask us about these problems in office hours this week. (Of course, the same invitation applies to any other problem you're trying to solve in preparation for the prelim; feel free to come to office hours and ask us about it.)