Date Subject Notes References  
1/8
Monday
CLASS CANCELLED      
1/10
Wednesday
Course Policies, Procedures
Probability Basics
My notes    
1/15
Monday (MLK Day)
No class      
1/17
Wednesday
CLASS CANCELLED      
1/22
Monday
Deterministic MST algorithms My notes Surveys on MSTs by Jason Eisner and Martin Mares.
An older one by Graham and Hell.
The Fredman-Tarjan paper about Fibonacci heaps.
Some notes on Fibonacci heaps from Danny Sleator and Kevin Wayne (with figures).
Notes by Raimund Seidel and Gabriel Nivasch on the inverse Ackermann function.
 
1/24
Wednesday
Randomized MSTs My notes The Karger-Klein-Tarjan paper. Timothy Chan has a different proof of the sampling lemma.
The Komlos, King, and Hagerup papers on MST verification. Uri Zwick’s notes on MST verification.
References on arborescences:
Edmonds, Optimal Branchings, 1966. (I couldn’t find the Chu-Liu ‘65 and Bock ‘71 papers.) Our proof follows Karp ‘71.
R. Tarjan, Finding optimal branchings: an $O(m log n)$ time algorithm. (and errata by Carmerini et al.)
Current best: Mendelson, Tarjan, Thorup, Zwick, gave an $O(m log log n)$ algorithm in 2004.
 
1/29
Monday
Dynamic Graph Connectivity My notes Worst-case update times:
Greg Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications, 1985. (and slides by Ran Duan)
Kapron, King, and Mountjoy, Dynamic graph connectivity in polylogarithmic worst case time, 2012. (and slides)
some recent developments by Nanongkai and Saranurak and by Wulff-Nilsen, 2016
And for amortized update times which we did not go over:
the Holm, de Lichtenberg, Thorup paper (and slides by Pino Italiano and Ran Duan)
and a lower bound by Patrascu and Demaine.
 
1/31
Wednesday
Shortest Paths My notes Basic notes on shortest-paths from 210, 451, and from Jeff Erickson SSSP, APSP)
R. Seidel. On the all-pairs-shortest-path problem, STOC 1992.
Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92.
 
2/5
Monday
Low-stretch Trees My notes Lecture notes from our randomized algorithms course (S11).
Alon, Karp, Peleg, West: A Graph-Theoretic Game and its Application to the k-Server Problem, SICOMP.
Bartal: Probabilistic Approximation of Metric Spaces and its Algorithmic Applications, FOCS 96
Our presentation pretty much followed his general construction.
Fakcharoenphol, Rao, Talwar, A tight bound on approximating arbitrary metrics by tree metrics, STOC 03.
This paper gives the best possible algorithm for the metric graph case.
Abraham, Neiman: Using Petal-Decompositions to Build a Low Stretch Spanning Tree.
This paper gives the current best algorithm for the general graph case. Some other low-diameter decomposition schemes:
Miller, Peng, Xu: Parallel Graph Decompositions Using Random Shifts, SPAA. The Calinescu-Karloff-Rabani/Fakchareonphol-Rao-Talwar schemes, the Miller Peng Xu scheme. And applications of low-stretch spanning trees to some problems:
Approximation Algorithms (a survey), solving linear systems (Speilman-Teng, KMP, KOSZ).
 
2/7
Wednesday
Matchings in General Graphs: combinatorial algorithms My notes    
2/12
Monday
Matchings in General Graphs: linear programming. My notes    
2/14
Wednesday
Max-Weight Matchings in Graphs: A Pricing algorithm My notes    
2/19
Monday
Matchings in Graphs: Algebraic Algorithms My notes    
2/21
Wednesday
Smoothed Analysis Anupam’s scribed notes    
2/26
Monday
Online Learning and the Multiplicative Weights Framework Anupam’s scribed notes    
2/28
Wednesday
Applications of MW: zero-sum-games, solving LPs. My notes    
3/5
Monday
Applications of MW: max-flows using electrical flows My notes    
3/7
Wednesday
Gradient Descent. Yet another low-regret algorithm. My notes    
3/12
Monday
Mirror Descent: generalizing MW and GD My notes    
3/14
Wednesday
Class Cancelled      
3/19
Monday
Spring break!      
3/21
Wednesday
Spring break!      
3/26
Monday
Ellipsoid Algorithm and Overview of Interior-point Methods.      
3/28
Wednesday
Concentration of Measure: “Chernoff-Hoeffding” Bounds My notes (coming soon!)    
4/2
Monday
Dimension Reduction: JL and related topics My notes    
4/4
Wednesday
Streaming I: Computing Frequency Moments and JL My notes    
4/9
Monday
Dimension Reduction: Singular Value Decompositions      
4/11
Wednesday
Online Algorithms: Rent-or-Buy and Paging, Online Primal-Dual      
4/16
Monday
Approximation Algorithms      
4/18
Wednesday
Fixed-Parameter Tractable Algorithms      
4/23
Monday
Final Project Presentations      
4/25
Wednesday
Final Project Presentations      
4/30
Monday
       
5/2
Wednesday
Final exam slot 2:50-5:40 pm
Final Project Presentations