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. The particular problems we will study are selected primarily because they are good illustrations of general techniques; they are not the primary focus of the class. You must practice ways of establishing that an algorithm is correct and analyzing 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.

List of readings

The exact readings will be determined after I have a chance to meet with the class. They will deal extensively with advanced techniques for the design and analysis of data structures, harnessing the power of cleverly implemented abstract data types, advanced examples of strategies for design and analysis, such as divide-and-conquer, greedy strategies, dynamic-programming, amortized analysis, and reduction of a given problem to a seemingly unrelated one. Much of the course is about how to structure your thinking so that you can easily think up and analyze solutions that would otherwise be out of reach.