CS450: Advanced Algorithms (Spring 2023)
| Credits | 8 | |
| Lecturers | Alessandro Chiesa and Michael Kapralov | |
| Schedule | Lectures: Tuesdays 11-13 in SG1 and Wednesdays 12-14 in CO3.
Exercises: Fridays 10-13 in CM1105 and INF1. |
A first graduate course in algorithms, this course assumes minimal background but moves rapidly. The objective is to learn the main techniques of algorithm design and analysis while building a repertory of basic algorithmic solutions to problems in many domains.
This is a course for Master students. Lectures will be in English.
For more details see the official coursebook.
Important dates
- Mid-term exam: TBD
- Final exam: during exam session (exact date TBD)
Topics
A preliminary list of topics:- When and why do greedy algorithms work? Matroids and 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)
Reading
The detailed schedule, lecture notes, and additional links to material is on the course moodle.Mid-term and Final Exam
You can use a single hand-written A4-page on which you can write anything on both sides. (No magnifying glasses allowed!)Grading
Grades will be based on two homeworks [30%], the midterm [30%], and the final exam [40%].Syllabus
| Subject | Date | Time | Description | Location | |
| Lecture 1 | 2023-02-21 | 11:00 - 13:00 | When and why does GREEDY work? | SG1 | |
| Lecture 2 | 2023-02-22 | 12:00 - 14:00 | Matroid Intersection and Bipartite Matchings | CO3 | |
| Lecture 3 | 2023-02-28 | 11:00 - 13:00 | Matchings, Intro to Linear Programming | SG1 | |
| Lecture 4 | 2023-03-01 | 12:00 - 14:00 | Linear Programming: Extreme Points | CO3 | |
| Lecture 5 | 2023-03-07 | 11:00 - 13:00 | Linear Programming: Duality | SG1 | |
| Lecture 6 | 2023-03-08 | 12:00 - 14:00 | Hungarian Method and Weighted Vertex Cover | CO3 | |
| 2023-03-14 | 11:00 - 13:00 | Cancelled | |||
| Lecture 7 | 2023-03-15 | 12:00 - 14:00 | Approximation Algorithms | CO3 | |
| Lecture 8 | 2023-03-21 | 11:00 - 13:00 | Approximation Algorithms using LPs | SG1 | |
| Lecture 9 | 2023-03-22 | 12:00 - 14:00 | Solving LPs using Multiplicative Weights | CO3 | |
| Lecture 10 | 2023-03-28 | 11:00 - 13:00 | Hedging for LPs and Intro to Randomized Algorithms | SG1 | |
| Lecture 11 | 2023-03-29 | 12:00 - 14:00 | Randomized Algorithms (Karger's Min-Cut Algorithm) | CO3 | |
| Midterm Exam | 2023-03-31 | 10:00 - 13:00 | |||
| Lecture 12 | 2023-04-04 | 11:00 - 13:00 | Sampling and Concentration Inequalities | SG1 | |
| Lecture 13 | 2023-04-05 | 12:00 - 14:00 | Graph Sparsification | CO3 | |
| Lecture 14 | 2023-04-18 | 11:00 - 13:00 | Graph Sparsification | SG1 | |
| Lecture 15 | 2023-04-19 | 12:00 - 14:00 | Hashing | CO3 | |
| Lecture 16 | 2023-04-25 | 11:00 - 13:00 | Streaming Algorithms | SG1 | |
| Lecture 17 | 2023-04-26 | 12:00 - 14:00 | Distinct elements, AMS sketch | CO3 | |
| Lecture 18 | 2023-05-02 | 11:00 - 13:00 | Distinct elements, AMS sketch | SG1 | |
| Lecture 19 | 2023-05-03 | 12:00 - 14:00 | Locality Sensitive Hashing | CO3 | |
| Lecture 20 | 2023-05-09 | 11:00 - 13:00 | Streaming Algorithms | SG1 | |
| Lecture 21 | 2023-05-10 | 12:00 - 14:00 | Submodularity and Minimization | CO3 | |
| Lecture 22 | 2023-05-16 | 11:00 - 13:00 | Submodularity and Minimization | SG1 | |
| Lecture 23 | 2023-05-17 | 12:00 - 14:00 | Submodularity and Maximization | CO3 | |
| Lecture 24 | 2023-05-23 | 11:00 - 13:00 | Introduction to Spectral Graph Theory | SG1 | |
| Lecture 25 | 2023-05-24 | 12:00 - 14:00 | Online Algorithms | CO3 | |
| Lecture 26 | 2023-05-30 | 11:00 - 13:00 | Spectral Graph Theory and Connectivity | SG1 | |
| Lecture 27 | 2023-05-31 | 12:00 - 14:00 | CO3 |