Information for final exam: comp 160 Algorithms Spring 2013

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.