This course teaches general techniques for designing and analyzing algorithms. The exact coverage is subject to change. Possible topics include:

• Introduction: Stable matchings, some representative problems, and the basics of algorithm design.
• Greedy Algorithms: General greedy techniques, minimum spanning trees
• Divide and Conquer
• Dynamic Programming: Weighted interval scheduling, knapsack, and many applications.
• Flows and Cuts in Networks: Max-flow Min-cut Theorem, augmenting paths, basic applications.
• Applications of Flows: Extensions of flows to more general models, more advanced applications.
• Computational Hardness, Reductions, and NP-Completeness
• Algorithms for Hard Problems: Approximation Algorithms, Randomized Algorithms, Local Search

We will have approximately 10 homework assignments, a midterm exam, and a final exam. There will also be an in-class quiz during the second week of class testing knowledge that is pre-requisite for this class.

Course Learning Objectives: Students who successfully complete this course will be able to analyze and design efficient algorithms for a variety of computational problems. They will also be able to communicate their ideas in the form of precise algorithm descriptions and rigorous proofs.