Illinois Institute of Technology CS-535 Advanced Algorithms Notes
This course covers the design of efficient exact and approximation algorithms for a variety of problems, with mathematical proof of correctness and analyses of time and space requirements and approximation bounds. Topics include shortest paths with arbitrary lengths, negative circuits and minimum mean circuits, minimum spanning arborescence, bipartite matching, non-bipartite matching, min-cost T-joins, maximum flow, min-cost flow, circulation and transshipments, submodular functions and polymatroids, and approximation algorithms for NP-hard problems. Lectures and exercises also cover a wide range of practical applications.
Broadly, the course has three objectives:
- Learn how to abstract a real-world computational problem into a mathematically clean core.
- Identify the algorithm design techniques appropriate for the context, based on the structure of the problem.
- Mathematically analyze the algorithms, and quantify the relative merits of various design choices.
- CS 430
- Homework assignments on theoretical and practice problems
- Midterm and final exams
| Topic | Hours |
|---|---|
| Shortest Path with Arbitrary Lengths | 2 |
| Negative Circuit and Minimum-Mean Circuit | 2 |
| Bipartite Matching and Covering | 4 |
| Weighted Bipartite Matching and Covering | 4 |
| Maximum Flow and Applications | 6 |
| Min-Cost Flow, Circulation, and Transshipment | 4 |
| General Matching and Covering | 3 |
| Weighted General Matching and Covering | 2 |
| Min-Cost T-Join and Applications | 1 |
| Minimum Spanning Arborescence | 3 |
| Submodular Functions and Polymatroids | 6 |
| Approximation Algorithms | 8 |
- A. Schrijver, Combinatorial Optimization: Polyhedra And Efficiency, Springer, 2003 (required).
- J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009.
- Illinois Institute of Technology