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.
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 |