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.

- Mid-term exam: TBD
- Final exam: during exam session (exact date TBD)

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

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 |