- Instructor: Prof. Mohsen Ghaffari
- Units 2V+2U+1A = 6CP
- Lecture Time & Place: Tuesdays 10:00-12:00 at CAB G52
- 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

- (09/19) Lecture 01: Graph Sparsification Algorithms 1 --- Preserving Cuts
- 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)

- (09/26) Lecture 02: Graph Sparsification Algorithms 2 --- Preserving Distances, i.e., Spanners
- Lectures 6 and 7 of Vassilevska Williams (CS 267, Graph Algorithms, Stanford, Spring 2016)
- The 2001 paper of Thorup and Zwick
- The 2003 paper of Baswana and Sen

- (10/03) Lecture 03: Approximation Algorithms 1 --- Greedy: Set Cover, Vertex Cover, and Job Shop Scheduling
- (10/10) Lecture 04: Approximation Algorithms 2 --- PTAS and FPTAS, Knapsack and Bin Packing
- Chapters 8 and 9 in Vazirani's Book
- Chapter 3 in Williamson & Shmoys's Book
- Lecture 13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)

- (10/17) Lecture 05: Approximation Algorithms 3 --- FPRAS, DNF Counting, and Network Reliability
- Chapter 21 of Vazirani's Book
- The 1999 paper of Karger
- Lecture 11 of Sinclair (CS271 Randomness and Computation, Berkeley, Fall 2011)

- (10/24) Lecture 06: Approximation Algorithms 4 --- Randomized Rounding of LPs, Multi-Commodity Flow and Scheduling Unrelated Machines
- Chapter 17 of Vazirani's Book
- Chapter 5 in Williamson & Shmoys's Book
- Section 5.3 in Motwani & Raghavan's Book
- Lectures 10 & 11 of Checkuri (CS 583, Approximation Algorithms, UIUC, Spring 2011)

- (10/31) Lecture 07: Approximation Algorithms 5 --- Metric Embedding & Sparsest Cut
- Chapter 28 of Vazirani's Book
- Lectures 25 of Checkuri (CS 583, Approximation Algorithms, UIUC, Spring 2016)
- The 1995 paper of Linial, London, and Rabinovich

- (11/07) Lecture 08: Approximation Algorithms 6 --- Probabilistic Tree Embedding
- The 1996 paper of Bartal
- The 2003 paper of Fakcharoenphol, Rao, and Talwar
- Section 8.5 in Williamson & Shmoys's Book
- Lecture 14 of Gupta (15-859M, Randomized Algorithms, CMU, Spring 2011)
- Lectures 26 of Checkuri (CS 583, Approximation Algorithms, UIUC, Spring 2016)

- (11/14) Lecture 09: Online Algorithms 1 --- Ski Rental, Load Balancing, Paging
- Lecture 19 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lecture 22 of Karger (6.854 Advanced Algorithms, MIT, Fall 2005)
- Lecture 22 of Gupta (15-850, Advanced Algorithms, CMU, Spring 2017)

- (11/21) Lecture 10: Online Algorithms 2 --- Randomized Paging, and k-Server
- Lecture 20 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lectures 23 of Karger (6.854 Advanced Algorithms, MIT, Fall 2016)
- Survey by Koutsoupias

- (11/28) Lecture 11: Online Learning from Experts --- The Multiplicate Weight Updates Method
- (12/05) Lecture 12: Streaming & Sketching Algorithms 1 --- Streaming Model, Distinct Elements, and k-wise Independence
- Lecture 1 of Indyk (6.895 Sketching, Streaming and Sublinear Space Algorithms, MIT, Fall 2007)
- Lecture 2 of Nelson (CS 299r, Algorithms for Big Data, Harvard, Fall 2015)
- Lecture 4 of Karger (6.854 Advanced Algorithms, MIT, Fall 2016)
- Lecture 2 of Chekuri (CS 598CSC, Algorithms for Big Data, UIUC, Fall 2014)

- (12/12) Lecture 13: Streaming & Sketching Algorithms 2 --- Alon-Matias-Szegedy's Moment Estimator
- 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)
- 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

- (12/19) Lecture 14: Streaming & Sketching Algorithms 3 --- Ahn-Guha-McGregor's Graph Sketching
- 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

- Problem Set 1 due 09/25/2017: [PDF]