Advanced Algorithms, ETH Zurich, Fall 2021

Instructor: Mohsen Ghaffari and Goran Zuzic
Teaching Assistants: Michal Dory, Saeed Ilchi, Jiahao Qu, and Vaclav Rozhon
Units: 3V+2U+3A, 9 Credits
Lecture Time & Place: Wednesdays 09:00-12:00 (HG D5.2)
Exercise Session Time & Place: Fridays 10:00-12:00 (CAB G59)
Office Hours: By appointment/email
Final Exam: Tuesday January 18, 2022, 09:00-12:00 (HG E 7)
Moodle: Advanced Algorithms 2021 on Moodle
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 0 and consult the instructor.
Other Links: Information on the Course Catalogue of ETH Zurich


Grading: Two graded homeworks 40% (due dates: November 10 and December 8), and a 3-hour final exam 60% (the final exam will be an end-of-semester exam on Tuesday, January 18, from 09:00 to 12:00).

Homeworks, Problem Sets, and Exercise Sessions: During the semester, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 20% of your grade. You should submit your solutions, which must be typeset in LaTeX, via moodle. 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 recommend 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 are the lecture notes for this course, but please keep in mind that the lecture notes will be updated throughout the semester. Please see the course moodle for the video recordings of the lectures, and also for the handwritten notes (from the shared screen on the zoom session).

Topic List (14 ⨉ 3-hour lectures, in 5 blocks)

The following shows the schedule of the course in the 2021 edition. The precise schedule and content will be updated throughout the semester. Hollow bullet points indicate additional sources and optional material.

Block 1: Basics of Approximation Algorithms

Block 2: Streaming & Sketching Algorithms

Block 3: Online Algorithms & Competitive Analysis

Block 4: Graph Sparsification

Block 5: Selected Topics in Approximation Algorithms

Additional Material: