CPSC 629: Midterm Exam Review
Fall 2003

The exam will consist of some short answer questions and several "work-out" problems, similar in spirit to the homework, but not as involved (since time is limited).

For example, for dynamic programming, I will either give you the recursive solution up front, or will remind you of one we've seen before (lecture or reading or HW) and give you a hint as to how to modify it.

For the data structures (B-tree, binomial heap, Fibonacci heap), know how the operations work well enough that you could draw their result given a diagram (you don't have to be able to regurgitate pseudocode). Also, know all the running times of the operations and why (unless noted otherwise below).

Below, all references to "times" refer to worst-case times and amortized times (where appropriate).

In general, you should review your notes from lecture, the readings, and the homeworks (including examples of dynamic programming algorithms, greedy algorithms, amortized analyses). More details below: