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:

Topics:

• Dynamic Programming (Ch 15). Be familiar with the paradigm and under what situations it applies. Given a recursive solution to a problem, be able to convert it into a DP algorithm.

• Greedy Algorithms (Ch 16). Be familiar with the paradigm and under what situations it applies. Know what a matroid is and how matroid theory relates to greedy algorithms.

• Amortized Analysis (Ch 17). Know what amortized analysis is and how it is used to bound the running time of a sequence of operations. Know the three approaches (aggregate, accounting, and potential).

• B-Trees (Ch 18). Know the definition of a B-tree of degree t, why the height is logarithmic, and why that is important.

• Binomial Heaps (Ch 19). Know the definition of a binomial heap.

• Fibonacci Heaps (Ch 20). Know the definition of a Fibonacci heap. For the time analysis, know that the key point is bounding D, the maximum degree. When decrease-key and delete are excluded from consideration, you should know why D is O(log n). When decrease-key and delete are included, you do not have to memorize the analysis (involving Fibonacci numbers) that showed D is O(log n).

• Disjoint Sets (Ch 21). Know the definition of the Disjoint Sets abstract data type. Know the linked list representation, the times for the operations, and why. Know the forest representation, both with and without union by rank and path compression; know the times for the operations with union by rank only and why; know the times for the operations with both heuristics, but you don't need to memorize the analysis. Note that in class I presented the analysis from the first edition of the book, not the second edition.