Advanced Algorithms, ETH Zurich, Fall 2017
Instructor : Prof. Mohsen Ghaffari
Teaching Assistants : Manuela Fischer and Przemysław Uznański
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 .
Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally.
Other Links: Information on the Course Catalogue of ETH Zurich
Tentative Topic List
(09/19) Lecture 01: Graph Sparsification Algorithms 1 --- Preserving Cuts, i.e., Sparsifiers
(09/26) Lecture 02: Graph Sparsification Algorithms 2 --- Preserving Distances, i.e., Spanners
(10/03) Lecture 03: Approximation Algorithms 1 --- Greedy: Set Cover, Vertex Cover, Minimum Makespan Scheduling, and Monotone Submodular Maximization
(10/10) Lecture 04: Approximation Algorithms 2 --- PTAS and FPTAS: Knapsack, Bin Packing, and Minimum Makespan Scheduling
Scribe Notes 4
Problem Set 4
Chapters 8, 9, & 10 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/17) Lecture 05: Approximation Algorithms 3 --- FPRAS: DNF Counting, Network Reliability, and Counting Graph Colorings
Scribe Notes 5
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/24) Lecture 06: Approximation Algorithms 4 --- (Randomized) Rounding for LPs: Set Cover, Integer Multi-Commodity Flow, and Scheduling Unrelated Machines
Scribe Notes 6
Problem Set 6
Chapters 14 & 17 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/31) Lecture 07: Approximation Algorithms 5 --- Probabilistic Tree Embedding & Buy-at-Bulk Network Design
Scribe Notes 7
Problem Set 7
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)
(11/07) Lecture 08: Approximation Algorithms 6 --- L1 Metric Embedding & Sparsest Cut
Scribe Notes 8
Problem Set 8
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
(11/14) Lecture 09: Online Algorithms & Competitive Analysis 1 --- Ski Rental, Lost Cow, Linear Search, and Paging
Scribe Notes 9
Graded Homework 2, Deadline: November 28, 10:15 am
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
(11/21) Lecture 10: Online Algorithms & Competitive Analysis 2 --- k-Server, Online Routing of Virtual Circuits, and Online Bipartite Matching
Scribe Notes 10
Problem Set 10
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
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
A simple analysis by Birnbaum and Mathieu of the online matching of Karp, Vazirani, and Vazirani
Lecture 5 of Kleinberg (CS 6820: Algorithms, Cornell, Fall 2012)
A survey by Mehta on Online Matching and Ad Allocation from 2012
(11/28) Lecture 11: Streaming & Sketching Algorithms 1 --- Frequent Elements, Approximate Counting, and Distinct Elements
Scribe Notes 11
Problem Set 11
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)
(12/05) Lecture 12: Streaming & Sketching Algorithms 2 --- Alon-Matias-Szegedy's Moment Estimator and Space Complexity Lower Bounds
Scribe Notes 12
Graded Homework 3, Deadline: December 22, 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
(12/12) Lecture 13: Streaming & Sketching Algorithms 3 --- Ahn-Guha-McGregor's Graph Sketching, and Epsilon-Bias Spaces
Scribe Notes 13
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
(12/19) Lecture 14: Online Learning from Experts --- The Multiplicate Weight Updates Method
Scribe Notes 14
Final Exam, Open Book (without electronic devices), December 19, 4:00 to 7:00 pm in HG D7.1
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
Grading: Three graded homeworks 30%, and a 3-hour final exam 70% (Tuesday, Dec 19, from 16:00 to 19:00, in HG D7.1). Homeworks, Problem Sets, and Exercise Sessions: After lectures 3, 8, and 12, we will provide some specially-marked homeworks, which are to be graded; each homework will account for 10% of your grade. Manuela Fischer (manuela.fischer at inf.ethz.ch).