Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Robert Tarjan

Fall 2007

Directory
General Information

Course Summary

Administrative Information

Lectures: MW 1330-1450, Room: 402

Professor: Robert Tarjan - 324 CS Building - 258-4797 ret@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Course Secretary: Mitra Kelly- 323 CS Building - 258-4562 mkelly@cs.princeton.edu

General Informtion

Class cancelled on 10/22

Homeworks

Problem Set 1: due Wed, Oct 10 in class
Problem Set 2: due Mon, Nov 5th in class
Optional Problem 1
Open Problem 2
Mid-Term Project:Choice of paper due October 24; Project due Nov 7th
Problem Set 3: due Mon, December 10 in class
Final Project: due Tuesday, January 15, 2008

Lecture outlines and assigned readings


Date
 Topic
 Readings
Monday 9/17
 Maximum Flow
Wednesday 9/19 Maximum Flow "A New Approach to the Maximum-Flow Problem" by Andrew V. Goldberg and Robert E. Tarjan.
Journal of ACM, Vol. 35, No.4, October 1988, pp. 921-940.
Link


"A Fast and Simple Algorithm for the Maximum Flow Problem" by R.K. Ahuja and James B. Orlin
Operations Research, Vol. 37, No. 5, September-October 1989, pp. 748-759.Link
Monday 9/24
 Maximum Flow "Beyond the Flow Decomposition Barrier" by Andrew V. Goldberg and Satish Rao
Journal of ACM, Vol. 45, No. 5, September 1998, pp. 783-797.Link


"Network Flow and Testing Graph Connectivity" by Shimon Even and Robert E. Tarjan
SIAM Journal of Computing, Vol. 4, December 1975, pp.507-518. Link

Wednesday 9/26
 Linear Programming (Kevin Wayne) Linear Programming Lecture 1 (by Kevin Wayne)
Link
Monday 10/1
 Linear Programming (Kevin Wayne) Linear Programming Lecture 2
Link
Wednesday 10/3
 Linear Programming (Kevin Wayne) Lecture Notes on the ellipsoid algorithm
Link

Linear Programming Lecture 3
Link

Monday 10/8
 A Riff on the Goldberg-Rao Maximum Flow
Link

Self Adjusting Binary Search Trees
Link

Wednesday 10/17
 Routing Flow Through a Strongly Connected Graph
Link

An Analysis of highest-level selection rule of the pre-flow push max-flow algorithm
Link

Wednesday 10/24
 Amortized Efficiency of lists Update and Paging Rules
Link
Monday 11/5
 Mergeable Trees
Link
Monday 11/12
 A Randomized Linear-Time Algorithm to Find Minimum Spanning trees
Link

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity....
Link

Wednesday 11/14
 Lecture 5
Link
Monday 11/19
(no class)
 Minimum Spanning Tree AlgorithmsTrees: A Mathematcial Tool for all Seasons by Joe Malkevitch (CUNY-York College)
website: www.ams.org/featurecolumn/archive/trees.html
Wednesday 11/28
 An O(nlogn) algorithm for maximum st-flow in a directed planar graph
Link
Monday 12/3
 Planar Point Location Using Persistant Search Trees
Link
Monday 12/10
 Online Topological Ordering
Link

An algorithm for online topological ordering
Link