Advanced Algorithms, ETH Zurich, Fall 2024

Instructor: Bernhard Haeupler, Maximilian Probst and Lengler Johannes

Teaching Assistants: Antti Roeyskoe, Richard Hladik, Patryk Morawski, Jakob Nogler and Andor Vari-Kakas

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

Lecture Time & Place: Monday 09:15-12:00, CAB G51

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: 16th December 2024, 9-12 AM, CAB G51. The exam is open-book.

Moodle: Advanced Algorithms 2024 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 40% (due dates: 28.10.2024 and 18.11.2024), and a 3-hour final exam 60% (the final exam will be an end-of-semester exam on 16.12.2024).

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 20% 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 (11 lectures in 3 blocks)

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

Preliminary exercise set (solutions)

Block 1: Approximation and Online Algorithms

(23.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)
(30.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)
(07.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)
(14.10) Lecture 04: Online Algorithms and Competitive Analysis --- Ski Rental, Paging
- 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: Streaming, Sketching and Sparsification

(21.10) Lecture 05: Advanced Hashing algorithms
- Chapter 5 of the Lecture Notes
- Exercise set 5 (solutions)
- Notes by Mikkel Thorup on more efficient hashing of integers and strings.
(28.10) Lecture 06: Streaming and Sketching: Statistics
(04.11) Lecture 07: Streaming and Sketching II: Graph Connectivity
(11.11) Lecture 08: Graph Sparsification: Spanners and Cut Sparsifiers
- Chapter 8 of the Lecture Notes
- Exercise set 8 (solutions)

Block 3: Selected Topics: Embeddings, Oblivious Routing, Multiplicative Weights

(18.11) Lecture 09: Ball Carving and Distance-Preserving Tree Embedding
- The 1996 paper of Bartal
- The 2003 paper of Fakcharoenphol, Rao, and Talwar
- Sections 8.5 & 8.6 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 14 of Gupta (15-859M, Randomized Algorithms, CMU, Spring 2011)
- Lectures 23 of Checkuri (CS 598, Approximation Algorithms, UIUC, Spring 2009)
(25.11) Lecture 10: L1 Metric Embedding and Sparsest Cut
- Chapter 10 of the Lecture Notes
- Exercise set 10 (solutions)
- Chapter 21 of Vazirani's Book on Approximation Algorithms
- Lectures 3 of Gupta and Ravi (15-859, Algorithmic Applications of Metric Embeddings, CMU, Fall 2003)
- Lectures 13 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
- Lectures 19 of Gupta (CS 15-854B, Advanced Approximation Algorithms, CMU Spring 2008)
- Lectures 20 & 21 of Checkuri (CS 598, Approximation Algorithms, UIUC, Spring 2009)
- The 1995 paper of Linial, London, and Rabinovich
- A survey by Indyk on algorithmic applications of embeddings from 2001
(02.12) Lecture 11: Multiplicative Weight Updates, Approximating Covering/Packing LPs, and Constructive Oblivious Routing
- Chapter 12 of the Lecture Notes
- Exercise set 11 (solutions)
- Lectures 16 and 17 of Gupta (15-859(E): Linear and Semidefinite Programming, CMU, Fall 2011)
- Lecture 4 of Vazirani and Rao (CS270, Algorithms, UC Berkeley, Spring 2011)
- Survey by Arora, Hazan, and Kale
- The 2008 paper of Raecke

(09.12) Course Review Session

(16.12) Exam
- 9-12 AM, CAB G51 (the usual lecture room). The exam starts at 9 AM, not the usual time of 9:15 AM. Be on time!
- The exam is open-book: you are permitted to consult any books, handouts, and personal notes you bring to the exam.
- The use of electronic devices, such as phones, smartwatches, and noise-cancelling earbuds/headphones is not allowed.
  The use of analog watches/clocks is allowed.
- Bring pens, your student ID, and any books, handouts, and personal notes you want to be able to consult. You do not need to bring your own blank paper; we will provide blank paper for you.

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.