15859(E): Advanced Algorithms, Fall 2009
 Lecturers: Anupam
Gupta and Danny Sleator
 Time: MW 3:004:20, GHC 4303
 Course Blog: http://cmuadvancedalgorithms.blogspot.com/
Lectures
 Lecture 1: MSTs: intro, Prim, Kruskal, Boruvka, O(m log log n) time using
Fibonacci heaps, FredmanTarjan 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 lineartime Randomized MST algorithm. Finding
mincost arborescences.
Papers related to lineartime algorithms for MST verification and
finding Flight 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), BellmanFord(Moore), (valid) potentials and
negative cycles, FloydWarshall, Seidel.
Papers related to today's material.
 Lecture 7 (9/30): Shortest Paths II. Finding potentials faster than BellmanFord.
 Lecture 8 (10/5): van Emde Boas data structure. Perfect
hashing.
 Peter van Emde Boas, R. Kaas, and E. Zijlstra: Design and
Implementation of an Efficient Priority Queue, Mathematical Systems
Theory 1977.
 Notes from Erik Demaine's course, and from Gudmund Frandsen
Lower bounds.
Perfect Hashing.
 Lecture 9 (10/7): Fullydynamic graph connectivity in O(log^2 n) update time.
 Lecture 10 (10/12): Network Flows

Maxflow notes from Dexter Kozen's book. (CMU/Pitt only.)

Notes on pushrelabel 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 nonbipartite, unweighted and weighted.
 Lecture 13 (10/21): Dynamic trees (contd.)
 Lecture 14 (10/26): Large Deviation (aka Chernofftype) Bounds, Martingales and AzumaHoeffding.
 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): Maxflow mincut proof, Seidel's lineartime LP algorithm.
 Seidel's original paper.
 Suresh Venkatasubramanian's notes give the details on solving the recurrence that I glossed over in lecture.
Some more references, in case you're interested.
 Lecture 19 (11/11): More lowdimensional LPs, and reweighting techniques.
 Lecture 20 (11/16): Online algorithms: skirental, list update, paging and kserver 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 MaxCut.
 Lecture 23 (11/30): Planar point location using persistent search trees.
 Lecture 24 (12/2): Online algorithms revisited: randomized rentorbuy two different ways.
The technique of solving LPs online:
And two recent papers about the randomized kserver problem based on online LPs.
Homework:
Homework
1 (due Monday, September 28, beginning of class)
Homework
2 (due Monday, October 12, beginning of class)
Homework
3 (due Monday, November 23, beginning of class)
Maintained by Anupam Gupta and Danny Sleator