The exam includes all the material covered in the course (with one exception, see (*) below). The exam is closed-book. You are expected to be well versed in all problems, algorithms, and all methods of analysis we used in the class, explain how they work, explain how they are used for the specific examples we covered, and use them to analyze new problems. You are expected to remember the algorithms covered in class at reasonable level of detail. I will not expect all fine details of pseudo-code to be memorized, but you should be able to explain how the algorithms work, apply them to new data, and develop their analysis. Portions marked as optional reading will not be covered in the exam.

The exam will include simple "knowledge questions" checking whether you are familiar with the material covered, "skill questions" checking whether you have the various skills required for algorithm analysis, and "problem solving questions" where you are asked to design a new algorithm for a problem.

The following lists (as requested by some students) enumerate the
topics along several dimensions. However, I may have missed some
things.
*
The table listing material and reading on the main course web
page is the definitive list of topics for the exam.
*
If in doubt send a
query and I will be happy to clarify.

** Sorting and selection: ** Insertion sort, bubble sort, merge
sort, quick sort, radix
sort, counting sort, heap sort, lower bounds for sorting,
randomized selection and medians.

** Design and analysis methods: ** Divide and conquer algorithms, greedy
algorithms, dynamic programming algorithms, design motivated by
amortized analysis.

** Proofs: ** induction (over integers), structural induction (over
structure of data or algorithm's computation), loop invariants, proofs by
contradiction, randomized analysis.

** Run time analysis: ** O() notation, worst case analysis relying
on loop structure, divide and conquer algorithms and their
recurrences, 3 methods for solving recurrences (unfolding, induction,
master theorem), randomized analysis, random variables and their
expected values,
dynamic programming algorithms and
their bottom up versions, amortized analysis (aggregate, accounting
method, potential method).

** More data structures: ** heaps, priority queues, disjoint sets,
hash tables and universal hashing, dynamically sized tables, Fibonacci
heaps, BST, B-Trees.

** More problems covered and their algorithms: **
Integer multiplication,
shortest paths (Dijkstra, 3 variants for all-pairs), Huffman coding,
minimum spanning trees, clustering, set-cover approximation
algorithm, LCS, HMM decoding.

** Basics of Complexity theory: ** P, verification algorithms, NP,
reductions, NP-completeness, concrete problems that are NP-Complete.

(*) Lecture material that discussed Markov Decision Processes and their solutions is not included in the exam.