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.
Schedule
- Lecture: Friday 10:00 - 12:00, Building 106 SR 00 007
- Exercise Class: Friday 12:00 - 14:00, Building 106 SR 00 007
Exercises
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.
Literature
- 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.