Computer Science 4020

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.