Credit points: 3.0.
This is an advanced course, suitable for graduate students and advanced undergraduates. Its goal is to introduce some of the important algorithmic problems, ideas and techniques, such as:
- Goldberg's algorithm for network flow
- Matchings in graphs: use of algebraic methods
- Randomized algorithms: matchings and min-cut
- Minimum cost flow: characterization, weakly polynomial and strongly polynomial algorithms
- Linear programming
- The simplex and ellipsoids methods for solving linear programs
- The minimax theorem and Yao's principle
- Approximation algorithmss for NP-hard problems: primal-dual method and randomized rounding
Grading Policy:
Final exam: 60% - 100% according to the MAGEN.
Assignments: up to 40% MAGEN (submission is in pairs).
There should be 3 or 4 MAGEN assignments.