COS 528: Data Structures and Graph Algorithms
Robert Tarjan, Spring 2013
Course Description
Description: Data structures and algorithms for graph and network problems, including disjoint set union, heaps, search trees, search on graphs, minimum spanning trees, shortest paths, network flows, and matchings. The intent of the course is to examine the most efficient algorithms known for a variety of combinatorial problems and to discover the principles underlying the design and analysis of these algorithms. The emphasis is on asymptotic worst-case and amortized analysis.
Graded Work: Problem sets and a research-oriented project. Details TBD.
Class Schedule: MW 11:00-12:20, CS Rm. 301
Office Hours: After class and by appointment, CS Rm. 324
Email: ret AT cs ...
Problem Set 1 — Union-Find
- Problems
- Due: 3/13/13
2/4 — Union-Find, Part I: Design Space
- Analysis slides here.
2/6 — Rank-Balanced Trees I
Guest Talk by Siddhartha Sen.- B. Haeupler, S. Sen, and R. E. Tarjan, “Rank-balanced trees,” ACM Trans. on Algorithms, submitted; preliminary version in WADS 2009, pp. 351-362.
2/11 — Union-Find, Part II: Tree Compression
- Analysis slides here.
2/13 — Union-Find, Part III: Compression Bounds
- Analysis slides here.
2/18 — Union-Find, Part IV: O(α(n,d)) Bound and Application to NCA
- Analysis slides here.
- Top-down slides here via Raimund Seidel.
- Alternate notes on top-down analysis here via Jeff Erickson.
- NCA slides here.
2/20 — Nearest Common Ancestors II; Depth-First Search
- DFS slides here.
2/25 — NCA ↔ RMQ; Topological Orderings & Strong Components
- See Erickson's course site (below) for a list of references pertaining to the relationship between the nearest common ancestor and range-minimum query problems.
- Strong component slides here.
2/27 — Dominators
- Slides here.
3/4 — Loop Hierarchies
- Notes pending.
3/6 — Cycle Detection Under Edge Addition, Part I
3/11 — Cycle Detection Under Edge Addition, Part II
- M. A. Bender, J. T. Fineman, S. Gilbert, and R. E. Tarjan, “A New Approach to Incremental Cycle Detection and Related Problems,” CoRR abs/1112.0784.
3/13 — Dynamic Connectivity I
- J. Holm, K. de Lichtenberg, M. Thorup, “Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity,” J. ACM 48, 4 (July 2001), 723-760.
- B. M. Kapron, V. King, B. Mountjoy, “Dynamic graph connectivity in polylogarithmic worst case time,” Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms 1131-1142, 2012.
3/25 — Dynamic Connectivity II; Diameter Estimation
- D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani, “Fast estimation of diameter and shortest paths (without matrix multiplication),” SIAM J. Comput., 28(4):1167–1181, 1999.
- L. Roditty, V. V. Williams, “Approximating the diameter of a graph,” arXiv:1207.3622v1 [cs.DS] (2012).
3/27 — Dynamic Connectivity III; Minimum Spanning Trees I
- D. R. Karger, P. N. Klein, R. E. Tarjan, “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees,” J. ACM 42(2): 321-328 (1995).
4/1 — Rank-Balanced Trees II; Minimum Bottlneck Spanning Tree
Guest Talk by Siddhartha Sen.4/3 — Minimum Spanning Trees II; Directed Minimum Spanning Trees I
- H. N. Gabow, Z. Galil, T. H. Spencer, R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica 6(2): 109-122 (1986).
- Notes on DMSTs from Uri Zwick here
4/8 — Directed Minimum Spanning Trees II; Fibonacci Heaps I
- M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM 34, 3 (July 1987), 596-615.
4/10 — Fibonacci Heaps II; Lazy Fibonacci Heaps
- Notes on lazy Fibonacci heaps here.
4/15 — Matching I; Diameter Approximation II
4/17 — Diameter Approximation III; Matching II; Max-Flow I
- V. Vazirani, “An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm,” 2013.
4/22 — Max-Flow II
4/24 — Max-Flow III
- A. V. Goldberg, R. E. Tarjan, “A new approach to the maximum-flow problem,” JACM 35 (1988), pp.921-940.
- Goldberg-Tarjan notes available here.
- A. V. Goldberg, S. Rao, “Beyond the flow decomposition barrier,” JACM 45 (1998), pp. 783-797.
- Goldberg-Rao notes available here.