Information for midterm exam: comp 160 Algorithms Spring 2013

The exam includes all the material covered in the course (both class and reading) up to the end of the "greedy algorithms section" as detailed in the table on the main course web page.

The exam is closed-book. You are expected to be well versed in 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 different 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.

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.
Proofs: induction, structural induction, 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.
More data structures: heaps, priority queues.
More problems covered and their algorithms: Integer multiplication, shortest paths (Dijkstra), Huffman coding, minimum spanning trees, set cover, clustering.