Algorithms and Complexity

Advanced Algorithms
Graduate Course - Summer Term 2019
Fabian Kuhn


Course description

In the course, we discuss modern algorithmic techniques. The course covers a variety of topics, such as for example:

  • approximation algorithms
  • randomized algorithms
  • graph embeddings
  • graph sparsification
  • theory of learning
  • sketching and streaming algorithms
  • continuous methods in combinatorial optimization

There is no formal requirement, however some background in algorithm design/analysis and probability theory is expected. Having passed the algorithm theory course (or a similar course) prior to taking the advanced algorithms lecture is highly recommended.


  • Lecture: Friday 10:00 - 12:00, Building 106 SR 00 007
  • Exercise Class: Friday 12:00 - 14:00, Building 106 SR 00 007


There will be a weekly exercise sheet, which is published here. While exercise sheets are not graded, you can do it yourself and submit your solution to us and we will give you some feedback on it. This is recommended, but not mandatory (in order to take the exam). Solutions of the exercise sheet will be discussed in the following exercise class.

Exercise sheet Assigned Solution

Problem Set 01 (Set Cover, Integrality Gap) 26.04.2019 Sample Solution 01
Problem Set 02 (Chernoff Bounds) 03.05.2019 Sample Solution 02
Problem Set 03 (Probabilistic Tree Embeddings) 10.05.2019 Sample Solution 03
Problem Set 04 (Cut Based Tree Decompositions) 17.05.2019 Sample Solution 04
Problem Set 05 (Multiplicative Weight Updates) 27.05.2019 Sample Solution 05
Problem Set 06 (Learning Linear Classifiers with MWU) 31.05.2019 Sample Solution 06
Problem Set 07 (Max Flow, Zero Sum Games, MWU) 14.06.2019 Sample Solution 07
Problem Set 08 (Additive & Multipl. Spanners, APSP) 28.06.2019 Sample Solution 08
Problem Set 09 (Cuts, Sparsifiers) 05.07.2019 Sample Solution 09
Problem Set 10 (Max Flow, Cong. Approximators) 15.07.2019 Sample Solution 10
Problem Set 11 (Aggregation in the MPC Model) 23.07.2019 Sample Solution 11

Lecture Material

All slides and recordings can be found on our Webserver.


  • A recording of the lecture on multiplicative weight updates by Ankur Moitra.
  • The lecture on multiplicative weight updates exactly covers the material, which is described in Section 1, 2 , and 3.1 of a very nice survey on the topic by Arora, Hazan, and Kale.
  • An application of the MWU algorithm for zero sum games.
  • The web page of Ankur Moitras Course.