Advanced Algorithms, ETH Zurich, Fall 2019

Instructor: Mohsen Ghaffari
Teaching Assistants: Sebastian Brandt, Saeed Ilchi, and Vaclav Rozhon
Units: 2V+2U+1A = 6CP
Lecture Time & Place: Tuesdays 10:00-12:00 at CAB G61
Exercise Session Time & Place: Fridays 10:00-12:00 at CAB G59
Office Hours: By appointment/email
Prerequisite: Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Basic Inequalities.
For instance, having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally.
If you're not sure whether you're ready for this class or not, please try Problem Set 00 and consult the instructor.
Other Links: Information on the Course Catalogue of ETH Zurich


Grading: Two graded homeworks 30%, and a 3-hour final exam 70% (Saturday January 25, 09:00 to 12:00, in HG E7).

Homeworks, Problem Sets, and Exercise Sessions: After lectures 5 and 10, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 15% of your grade. You should submit your solutions, which must be typeset in LaTeX, within two weeks, by emailing them to Sebastian Brandt ( We will send you more detailed instructions via email. Moreover, we will regularly have other problem sets, roughly one per lecture. You do not need to hand in their solutions. However, we recommed that you try to solve all of these problems on your own, and seek help from the assistants, if needed. These problem sets will be discussed during the exercise sessions. The exercise sessions are an indispensable part of the course -- the material covered in them will be included in the final exam and we strongly recommend attending them.

Lecture Notes:

Here is a version of the lecture notes. Please note that this file will be polished and updated, throughout the semester. This is an updated version of an earlier compilation, which was used in the 2018 offering of the class. The first version of these notes was put together in 2018, scribed by Davin Choo.

Tentative Topic List

Hollow bullet points indicate optional material and additional sources.

Additional Material: