Advanced Algorithms, ETH Zurich, Fall 2025

Instructor: Bernhard Haeupler, Maximilian Probst and Lengler Johannes

Teaching Assistants: Antti Roeyskoe, Raghu Ravi, Ondrej Sladky, Park Sangbeom

Units: 3V+2U+3A, 9 Credits

Lecture Time & Place: Monday 09:15-12:00, HG D3.2

Exercise Sessions:

Mon 14:15-16:00 CAB G59 covering solutions to the last week's exercise set
Wed 12:15-14:00 CHN F46 and Thu 16:15-18:00 LFV E41 for working on the current week's exercises

Office Hours: By appointment/email

Final Exam: Oral exam, winter examination session (20 minutes of preparation time, which is open book, followed by a 15 minute oral exam. More details will be provided later).

Moodle: Advanced Algorithms 2025 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 the preliminary exercise set.

Other Links: Information on the Course Catalogue of ETH Zurich

Grading: Two graded homeworks 50% (due dates: 20.10.2025 and 1.12.2025), and an oral exam 50% (in the winter examination session).

Homeworks, Exercise Sets, and Exercise Sessions: During the semester, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 25% of your grade. You should submit your solutions, which must be typeset in LaTeX, via moodle.

Moreover, we will have weekly exercise sets, one released after every lecture on the lecture's topic. 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 exercise sets will be discussed during the exercise sessions. The exercise classes on Mondays are dedicated to covering solutions to last weeks' exercises: come to these sessions if you have solved the problems beforehand or just want to see the solutions. The exercise classes on Wednesdays and Thursdays are dedicated to working on the exercise set released that week: come to one of these sessions if you want help/hints from the asistants working on the exercise set. Of course, feel free to ask questions about the exercises on the Q/A forum on Moodle. There are no exercise classes on the first week of the semester.

The exercise sets are an indispensable part of the course -- the material covered in them will be included in the final exam.

Lecture Notes:

The lecture notes for this course are available on Moodle. Please keep in mind the lecture notes may be updated throughout the semester. The lecture notes are based on previous lecture notes by Mohsen Ghaffari, but have been substantially revised. The old notes are still available here.

Topic List (12 lectures in 3 blocks)

The following shows the schedule of the course in the 2025 edition. The precise schedule and content will be updated throughout the semester. Please note that the release and deadline of the second graded homework is not final, and may change as we are working on changes to the second half of the course. Hollow bullet points indicate additional sources and optional material not covered during the lecture.

Preliminary exercise set (solutions)

Block 1: Approximation and Online Algorithms

(22.09) Lecture 01: Greedy Algorithms and PTAS --- Set Cover, Knapsack, Bin Packing
- Chapters 1-2, 8-10 in Vazirani's Book on Approximation Algorithms
- Chapters 1-3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lectures 1-3 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
(29.09) Lecture 02: FPRAS --- Bin Packing, DNF Counting, Network Reliability
- Chapters 8-10 in Vazirani's Book on Approximation Algorithms
- Chapter 3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lectures 12-13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lecture 3 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
(06.10) Lecture 03: Rounding Linear Programs --- Vertex Cover, Set Cover, Integral Multicommodity Flow
- Chapters 14 of Vazirani's Book on Approximation Algorithms
- Chapter 5.11 in Williamson & Shmoys's Book on Approximation Algorithms
- Section 4.3 in Motwani & Raghavan's Book
- Lectures 9 & 10 of Checkuri (CS 583, Approximation Algorithms, UIUC, Spring 2011)
(13.10) Lecture 04: Online Algorithms and Competitive Analysis --- Ski Rental, Paging
- Chapter 5 of the Lecture Notes
- Exercise set 4 (solutions)
- Lectures 19 & 20 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lecture 22 of Karger (6.854 Advanced Algorithms, MIT, Fall 2005)
- Lectures 14 and 15 of Blum (15-854 Approximation and Online Algorithms, CMU, Spring 2000)
- Lecture 22 of Gupta (15-850, Advanced Algorithms, CMU, Spring 2017)
- Lecture 3 of Azar (0368.4041 Online and Approximation Algorithms, Tel Aviv University, Spring 2016)
- A survey by Koutsoupias on the k-Server Problem from 2009

Block 2: Algorithms for Big Data

(20.10) Lecture 05: Advanced Hashing algorithms
- Notes by Mikkel Thorup on more efficient hashing of integers and strings.
- Notes by Mikkel Thorup on linear probing with 5-independent hashing.

(27.10) Lecture 06: Streaming Frequency Moments
- Chapter 7 of the Lecture Notes
- Exercise set 6 (solutions)

(03.11) Lecture 07: Dimensionality Reduction
- Chapter 8 of the Lecture Notes
- Exercise set 7 (solutions)

(10.11) Lecture 08: Clustering
- Chapter 9 of the Lecture Notes
- Exercise set 8 (solutions)

Block 3: Modern Graph Algorithms

(17.11) Lecture 09: Low-Diameter Decomposition, Tree Embedding from Random Shift
- The 1996 paper of Bartal
- The 2013 paper of Miller, Peng, and Xu on random-shift low-diameter decomposition
- The 2025 paper of Kyng, Gutenberg, and Rieder on low-stretch tree embedding
- The 2003 paper of Fakcharoenphol, Rao, and Talwar (alternative / original approach to low-stretch tree embedding)
- Sections 8.5 & 8.6 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 14 of Gupta (15-859M, Randomized Algorithms, CMU, Spring 2011)
- Lecture 23 of Checkuri (CS 598, Approximation Algorithms, UIUC, Spring 2009)

(24.11) Lecture 10: Multiplicative Weight Update, Cut Sparsifier from MWU
- Chapter 11 of the Lecture Notes
- Exercise set 10 (solutions)

(01.12) Lecture 11: Greedy Spanner, Cut Sparsifier via Expander Decomposition, Balanced Sparse Cut

(08.12) Lecture 12: Computing Flows Fast
- Chapter 13 of the Lecture Notes
- Exercise set 12 (solutions)

(15.12) Course Review Session

(Winter Examination Session) Final Exam (Oral)
- 20 minutes of preparation time, which is open book, followed by the 15 minute oral exam.
- More details will be provided later.

Additional Material:

Basic Probability Inequalities: Please make sure that you are comfortable with the basics of probability, e.g., Linearity of Expectation, Markov, Chebyshev, and Chernoff /Hoeffding. You might find the following handout of Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring 2011) useful.