Course Goals

The course is about learning and practicing principles for organizing your thinking when solving programming problems, and not about memorizing details and facts. You must practice ways of establishing that an algorithm is correct and anlyzing its time bound. Getting good at these skills will allow you to come up with efficient algorithms of your own, by figuring out what steps are needed in the pseudocode or program code to get the proof of correctness to go through, or to reduce the running time. You will also learn to recognize what kinds of optimizations on a program are a waste of time, as they will have little or no impact on the running time of the program as a whole.

List of likely topics

• Practice at algorithm-design techniques, such as divide-and-conquer (Ch. 4), dynamic programming (Ch. 15), greedy strategies (Ch. 16), amortized analysis (Ch. 17), randomization, and reductions from one problem to another. Applications drawn from various topics in the course.
• Treaps, 2-3 trees, meldable heaps, splay trees (handouts), O(n log n + m) union-find data type (Sections 21.1, 21.2), and applications drawn from various topics in the course.
• Illustrations of techniques on: various algorithms for minimum spanning tree;
• Computational geometry (Ch. 33);
• Fast Fourier Transform (Ch. 30);
• Expected-time analysis of Quicksort (Ch. 7) and Selection (Ch. 9);
• O(n) worst-case analysis of Selection (Ch. 9)
• Maximum flow (Ch. 26)