| 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 |