Advanced Algorithms, ETH Zurich, Fall 2018

Teaching Assistants: Sebastian Brandt and Manuela Fischer

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 consult the instructor.

Other Links: Information on the Course Catalogue of ETH Zurich

Grading: Three graded homeworks 30%, and a 3-hour final exam 70% (time and location to be determined).

Homeworks, Problem Sets, and Exercise Sessions: After lectures 4, 7, and 12, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 10% of your grade. You should submit your solutions within two weeks (to be made precise). The solutions must be typeset in LaTeX and should be emailed to Manuela Fischer (manuela.fischer at inf.ethz.ch) before the indicated deadline. Moreover, we will regularly have other problem sets, roughly one per lecture. You do not need to hand in their solutions. However, we strongly recommed that you try to solve all of these problems on your own, and seek help from the assistants, if you get stuck. 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 (last update Feb 5, 2019): Here is a compilation of the scribe notes of the 2018 offering, courtesy of Davin Choo.

Tentative Topic List

(09/18) Lecture 01: Approximation Algorithms 1 --- Greedy: Set Cover, Vertex Cover, and Monotone Submodular Maximization
- Scribe Notes 1 from 2018
- Scribe Notes 3 from 2017
- Problem Set 0
- Problem Set 1
- Chapters 1, 2, & 10 in Vazirani's Book on Approximation Algorithms
- Chapters 1 & 2 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lectures 1 & 2 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
(09/25) Lecture 02: Approximation Algorithms 2 --- PTAS and FPTAS: Knapsack and Bin Packing
- Scribe Notes 2 from 2018
- Scribe Notes 4 from 2017
- Problem Set 2
- Chapters 8 and 9 in Vazirani's Book on Approximation Algorithms
- Chapter 3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 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)
(10/02) Lecture 03: Approximation Algorithms 3 --- Greedy and PTAS: Bin Packing and Minimum Makespan Scheduling
- Scribe Notes 3 from 2018
- Scribe Notes 4 from 2017
- Chapters 9 and 10 in Vazirani's Book on Approximation Algorithms
- Chapter 3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 12 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lecture 3 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
(10/09) Lecture 04: Approximation Algorithms 4 --- FPRAS: DNF Counting and Counting Graph Colorings
- Scribe Notes 4 from 2018
- Scribe Notes 5 from 2017
- Graded Homework 1, Deadline: October 24, 11:59 pm
- 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)
(10/16) Lecture 05: Approximation Algorithms 5 --- (Randomized) Rounding for LPs: Set Cover and Congestion in Multi-Commodity Routing
- Scribe Notes 5 from 2018
- Scribe Notes 6 from 2017
- Problem Set 4
- 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)
(10/23) Lecture 06: Approximation Algorithms 06 --- Probabilistic Tree Embedding & Buy-at-Bulk Network Design
- Scribe Notes 6 from 2018
- Scribe Notes 7 from 2017
- Problem Set 5
- 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)
(10/??) (May Be Skipped) Lecture ??: Approximation Algorithms 07 --- L1 Metric Embedding & Sparsest Cut
- Scribe Notes 8 from 2017
- Problem Set 6
- 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
(10/30) Lecture 07: Streaming & Sketching Algorithms 1 --- Frequent Elements, Approximate Counting, and Distinct Elements
- Scribe Notes 7 from 2018
- Scribe Notes 11 from 2017
- Problem Set 7
- Lectures 1 & 2 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 2 of Chekuri (CS 598CSC, Algorithms for Big Data, UIUC, Fall 2014)
(11/06) Lecture 08: Streaming & Sketching Algorithms 2 --- Distinct Elements continued, and Alon-Matias-Szegedy's Moment Estimators
- Scribe Notes 8 from 2018
- Scribe Notes 12 from 2017
- Graded Homework 2, Deadline: November 23, 11:59 pm
- Lecture 2 of Indyk (6.895 Sketching, Streaming and Sublinear Space Algorithms, MIT, Fall 2007)
- Lecture 3 of Nelson (CS 299r, Algorithms for Big Data, Harvard, Fall 2015)
- Weeks 11 & 12 of Nikolov (CSC473: Advanced Algorithm Design, Toronto, Winter 2017)
- Lecture 3 of Chekuri (CS 598CSC, Algorithms for Big Data, UIUC, Fall 2014)
- Lecture 7 of Krauthgamer and Naor (Randomized Algorithms, Weizmann Institute, Fall 2015)
- The 1996 paper of Alon, Matias, and Szegedy
(11/13) Lecture 09: Streaming & Sketching Algorithms 3 --- Ahn-Guha-McGregor's Graph Sketching
- Scribe Notes 9 from 2018
- Scribe Notes 13 from 2017
- Problem Set 8
- 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)
- Lecture 12 of Chekuri (CS 598CSC, Algorithms for Big Data, UIUC, Fall 2014)
- The 2012 paper of Ahn, Guha, and McGregor
- Survey by McGregor
(11/20) Lecture 10: Graph Sparsification Algorithms 1 --- Preserving Distances, i.e., Spanners
- Scribe Notes 10 from 2018
- Scribe Notes 2 from 2017
- Problem Set 10
- 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
(11/27) Lecture 11: Graph Sparsification Algorithms 2 --- Preserving Cuts, i.e., Sparsifiers
- Scribe Notes 11 from 2018
- Scribe Notes 1 from 2017
- Problem Set 11
- 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)
(12/04) Lecture 12: Online Algorithms & Competitive Analysis 1 --- Ski Rental, Lost Cow, Linear Search, and Paging
- Scribe Notes 12 from 2018
- Scribe Notes 9 from 2017
- Problem Set 12
- Graded Homework 3 will be added here, Deadline: Dec 21, 11:59 pm
- 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
(12/11) Lecture 13: Online Algorithms & Competitive Analysis 2 --- Paging, Yao's Principle, and k-Server
- Scribe Notes 13 from 2018
- Scribe Notes 10 from 2017
- Problem Set 13
- 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
(12/18) Lecture 14: Online Learning from Experts --- The Multiplicate Weight Updates Method and Online Routing of Virtual Circuits
- Scribe Notes 14 from 2018
- Scribe Notes 14 from 2017
- Lecture 4 of Vazirani and Rao (CS270, Algorithms, UC Berkeley, Spring 2011)
- Lecture 11 of Gupta (15-850: Advanced Algorithms, CMU, Spring 2017)
- Lecture 1 of Madry (CS-621 Theory Gems, EPFL, Fall 2012)
- Survey by Arora, Hazan, and Kale
- Chapter 7 of the lecture notes of Plotkin (CS369, Online Algorithms, Stanford Spring 2013)
- A 1997 paper of Aspnes, Azar, Fiat, Plotkin, and Waarts on Online Routing

Additional Material:

Basic Probability Inequalities: Please make sure that you are comfortable with the basic probability inequlities, e.g., Markov, Chebyshev, and Chernoff/Hoeffding.
- 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).