Advanced Algorithms
| Credits | 7 | |
| Lecturer | Michael Kapralov | |
| Schedule | Lectures: Tuesdays 8-10 in CE 2 and Thursdays 13-15 in CM 1. Exercises: Fridays 10-13 in CM 1105 (also INF 1 if necessary). |
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design while building a repertory of basic algorithmic solutions to problems in many domains.
This is a course for Master students. The lectures will be in English.
For more details see the official couse book here.
Important dates
- Mid-term exam: Friday 3 April
- Final Exam: During exam session (exact date TBD)
Topics to be covered
A preliminary list of potential topics:- When and why does the basic Greedy algorithm work? Matroids. Also, matroid intersection.
- Convex programming for discrete optimization: linear programming (extreme point structure, duality) and semidefinite programming.
- Approximation algorithms (tradeoff between time and solution quality).
- Simplex method, ellipsoid method, gradient descent, and multiplicative weight update method.
- Submodular function optimization: polynomial time minimization and approximate maximization.
- Online algorithms (tradeoff between knowledge about future and solution quality).
- Streaming algorithms (tradeoff between knowledge about future and solution quality).
- Randomized algorithms (hashing, power of two choices, Karger's min-cut algorithm).
- Spectral graph theory (random walks, Cheeger's inequality)