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.)
- Chapter 4: Problems 5, 9, 13.
- Chapter 5: Problems 1, 5. (For your information,
Problem 4 in this chapter is extremely difficult and should not
be regarded as a fair practice question for the prelim!)
- Chapter 6: Problems 4, 6, 7, 19.