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 FredmanTarjan 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 KargerKleinTarjan 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 ChuLiu ‘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  Worstcase update times: Greg Frederickson, Data Structures for OnLine 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 WulffNilsen, 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 shortestpaths from 210, 451, and from Jeff Erickson SSSP, APSP) R. Seidel. On the allpairsshortestpath problem, STOC 1992. Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92. 

2/5 Monday 
Lowstretch Trees  My notes  Lecture notes from our randomized algorithms course (S11). Alon, Karp, Peleg, West: A GraphTheoretic Game and its Application to the kServer 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 PetalDecompositions to Build a Low Stretch Spanning Tree. This paper gives the current best algorithm for the general graph case. Some other lowdiameter decomposition schemes: Miller, Peng, Xu: Parallel Graph Decompositions Using Random Shifts, SPAA. The CalinescuKarloffRabani/FakchareonpholRaoTalwar schemes, the Miller Peng Xu scheme. And applications of lowstretch spanning trees to some problems: Approximation Algorithms (a survey), solving linear systems (SpeilmanTeng, 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 
MaxWeight 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: zerosumgames, solving LPs.  My notes  
3/5 Monday 
Applications of MW: maxflows using electrical flows  My notes  
3/7 Wednesday 
Gradient Descent. Yet another lowregret 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 Interiorpoint Methods.  
3/28 Wednesday 
Concentration of Measure: “ChernoffHoeffding” 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: RentorBuy and Paging, Online PrimalDual  
4/16 Monday 
Approximation Algorithms  
4/18 Wednesday 
FixedParameter Tractable Algorithms  
4/23 Monday 
Final Project Presentations  
4/25 Wednesday 
Final Project Presentations  
4/30 Monday 

5/2 Wednesday Final exam slot 2:505:40 pm 
Final Project Presentations 