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
- (22.09) Lecture 01: Greedy --- Set Cover, Vertex Cover, and Knapsack via Dynamic Programming
- 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: PTAS and FPTAS --- Knapsack and Bin Packing, [+ Optional: Minimum Makespan Scheduling]
- 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: FPRAS --- DNF Counting, [+ Optional: Network Reliability,] and Counting Graph Colorings
- Chapter 28 of Vazirani's Book on Approximation Algorithms
- The 1999 paper of Karger
- Lectures 10 & 11 of Sinclair (CS271 Randomness and Computation, Berkeley, Fall 2011)
- Lectures 14 of Sinclair (CS294 Markov Chain Monte Carlo: Foundations and Applications, Berkeley, Fall 2009)
- (13.10) Lecture 04: Rounding Linear Programs --- Vertex Cover and Set Cover, Congestion in Multi-Commodity Routing, Matching in Bipartite Graphs, [+ Optional: Scheduling on Unrelated Machines]
- 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)
Block 2: Streaming & Sketching Algorithms
- (20.10) Lecture 05: Connectivity via Graph Sketching
- Chapter 11 of the Lecture Notes
- Problem Set 5
- Graded Homework 1. Deadline: 11:59 pm on November 10 (submit via Moodle).
- Lectures 13 and 16 of Indyk (6.895 Sketching, Streaming and Sublinear Space Algorithms, MIT, Fall 2007)
- Lecture 7 of Nelson (CS 299r, Algorithms for Big Data, Harvard, Fall 2015)
- The 2012 paper of Ahn, Guha, and McGregor
- Survey by McGregor
- (27.10) Lecture 06: Frequent Elements, Approximate Counting, and Distinct Elements, and Moment Estimations
- Lectures 1-3 of Nelson (CS 299r, Algorithms for Big Data, Harvard, Fall 2015)
- Weeks 11 & 12 of Nikolov (CSC473: Advanced Algorithm Design, Toronto, Winter 2017)
- Lectures 5 & 6 of Karger (6.854 Advanced Algorithms, MIT, Fall 2016)
- Lecture 7 of Krauthgamer and Naor (Randomized Algorithms, Weizmann Institute, Fall 2015)
- The 1996 paper of Alon, Matias, and Szegedy
Block 3: Online Algorithms & Competitive Analysis
- (03.11) Lecture 07: Ski Rental, Lost Cow, Linear Search, and 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)
- Chapters 1 to 4 of Borodin and El-Yaniv's Book on Online Computation and Competitive Analysis
- A survey by Irani on Competitive Analysis of Paging
- (10.11) Lecture 08: Paging, Yao's Principle, and k-Server
- Lecture 3 of Azar (0368.4041 Online and Approximation Algorithms, Tel Aviv University, Spring 2016)
- Chapter 10 of Borodin and El-Yaniv's Book on Online Computation and Competitive Analysis
- A survey by Koutsoupias on the k-Server Problem from 2009
Block 4: Graph Sparsification
- (17.11) Lecture 09: Distance-Preserving Graph Sparsification, i.e., Spanners
- Lectures 6 and 7 of Vassilevska Williams (CS 267, Graph Algorithms, Stanford, Spring 2016)
- The 1999 paper of Aingworth, Chekuri, Indyk, and Motwani
- The 2013 paper of Chechik
- The 2003 paper of Baswana and Sen
- (24.11) Lecture 10: Cut-Preserving Graph Sparsification
- Chapter 13 of the Lecture Notes
- Problem Set 10
- Graded Homework 2. Deadline: 11:59 pm on December 8 (submit via Moodle).
- The 1996 paper of Benczur and Karger
- Lecture 5 of Krauthgamer and Naor (Randomized Algorithms, Weizmann Institute, Fall 2015)
- Lecture 13 of Bansal (2WO08, Graphs and Algorithms, Eindhoven Univ. of Tech, Spring 2015)
Block 5: Selected Topics in Approximation Algorithms
- (01.12) Lecture 11: Distance-Preserving Tree Embedding and Buy-at-Bulk Network Design
- 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)
- (08.12) Lecture 12: L1 Metric Embedding and Sparsest Cut
- 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
- (15.12) Lecture 13: Cut-Preserving Tree Embedding, Oblivious Routing, and Balanced Cut
- Chapters 15.2 and 15.3 in Williamson & Shmoys's Book on Approximation Algorithms
- The 2008 paper of Raecke
- The 2009 paper of Anderson and Feige
- (22.12) Lecture 14: Multiplicative Weight Updates, Approximating Covering/Packing LPs, and Constructive Oblivious Routing
- 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
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 sources useful: A handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring 2011), and another handout by Angelika Steger and Emo Welzl (Randomized Algorithms and Probabilistic Methods, ETH, Fall 2017).