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.

Link to instructions for checking in programming assignments

List of readings

• Techniques for proving correctness; representative problems (Chapter 1)
• Asymptotic analysis of algorithm efficiency ("big-O") (Chapter 2)
• Basic graph algorithms (Chapter 3)
• Greedy algorithms and their proofs of correctness (Chapter 4)
• Divide-and-conquer algorithms (Chapter 5)
• Dynamic programming (Chapter 6)
• Network flow, if time permits (some sections of Chapter 7)

During lectures, we will touch on other topics, such as undecidability, use of reductions to show lower bounds or membership of a problem in a hard class, application of data-structure design tricks to ADT's you have not seen in CS200.