15-859(E): Advanced Algorithms, Fall 2009
- Lecturers: Anupam
Gupta and Danny Sleator
- Time: MW 3:00-4:20, GHC 4303
- Course Blog: http://cmu-advancedalgorithms.blogspot.com/
- Lecture 1: MSTs: intro, Prim, Kruskal, Boruvka, O(m log log n) time using
Fibonacci heaps, Fredman-Tarjan and O(m log* n) time
- Lecture 2: Heaps: Fibonacci heaps. (Sleator's Notes)
- Lecture 3 & 4: Analysis of disjoint set algorithms
- Lecture 5: A linear-time Randomized MST algorithm. Finding
Papers related to linear-time algorithms for MST verification and
finding F-light edges:
And papers on finding optimal branchings.
- R. Tarjan, Finding optimal branchings, Networks: an O(m log n) time algorithm. (and errata by Carmerini et al.)
- Gabow, Galil, Spencer and Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica.
- Mendelson, Tarjan, Thorup, Zwick. Melding priority queues, ACM TAlg (SODA 04, STACS 04).
- Lecture 6 (9/28): Finding Shortest Paths I. Ford, Dijkstra (and some
implementations), Bellman-Ford(-Moore), (valid) potentials and
negative cycles, Floyd-Warshall, Seidel.
Papers related to today's material.
- Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92.
- A. Shoshan, U. Zwick. All pairs shortest paths in undirected graphs with integer weights, FOCS 99.
Lecture 7 (9/30): Shortest Paths II. Finding potentials faster than Bellman-Ford.
Lecture 8 (10/5): van Emde Boas data structure. Perfect
- Peter van Emde Boas, R. Kaas, and E. Zijlstra: Design and
Implementation of an Efficient Priority Queue, Mathematical Systems
- Notes from Erik Demaine's course, and from Gudmund Frandsen
Lecture 9 (10/7): Fully-dynamic graph connectivity in O(log^2 n) update time.
Lecture 10 (10/12): Network Flows
Max-flow notes from Dexter Kozen's book. (CMU/Pitt only.)
Notes on push-relabel from a survey by Andrew Goldberg, Eva Tardos and Bob Tarjan. (CMU/Pitt only.)
Including details on efficiently implementing the algorithm.
Lecture 11 (10/14): Splay Trees. Dynamic Trees (part I).
Lecture 12 (10/19): Matchings, bipartite and non-bipartite, unweighted and weighted.
Lecture 13 (10/21): Dynamic trees (contd.)
Lecture 14 (10/26): Large Deviation (aka Chernoff-type) Bounds, Martingales and Azuma-Hoeffding.
Lecture 15 (10/28): Polyhedra, Linear Programs, Duality.
Lecture 16 (11/02): Solving LPs via the Ellipsoid method.
Lecture 17 (11/04): The Matching Polytope, Integrality of the bipartite matching polytope.
- Michel Goemans' lecture notes recommended for Lec 15
contain some of the ideas from this lecture too.
Lecture 18 (11/09): Max-flow min-cut proof, Seidel's linear-time LP algorithm.
Some more references, in case you're interested.
- Seidel's original paper.
- Suresh Venkatasubramanian's notes give the details on solving the recurrence that I glossed over in lecture.
Lecture 19 (11/11): More low-dimensional LPs, and reweighting techniques.
Lecture 20 (11/16): Online algorithms: ski-rental, list update, paging and k-server problems.
Lecture 21 (11/18): A (very) brief introduction to
Approximation algorithms (Part I).
Lecture 22 (11/23): A (very) brief introduction to
Approximation algorithms (Part II)
And some of the recent developments on Max-Cut.
Lecture 23 (11/30): Planar point location using persistent search trees.
Lecture 24 (12/2): Online algorithms revisited: randomized rent-or-buy two different ways.
The technique of solving LPs online:
And two recent papers about the randomized k-server problem based on online LPs.
1 (due Monday, September 28, beginning of class)
2 (due Monday, October 12, beginning of class)
3 (due Monday, November 23, beginning of class)
Maintained by Anupam Gupta and Danny Sleator