Princeton University Computer Science Department

Computer Science 521 Advanced Algorithm Design Robert Tarjan

Fall 2002

Course Summary

• Advanced methods of algorithmic design and analysis;
• data structures;
• amortization;
• persistence;
• composite data structures;
• dynamic trees;
• linear programming;
• network optimization;
• randomization;
• selected topics.

Problem Sets

Note: Problem sets are due in class. If you think you will not be in class on the due date, please turn them in to Mitra Kelly (room 323).

• Problem Set 1 (due on 10/3) [PostScript] [Microsoft Word]
• Problem Set 2 (due on 10/17) [PostScript] [Microsoft Word]
• Problem Set 3 (due on 10/24) [PostScript] [Microsoft Word]
• Problem Set 4 (due on 12/5) [PostScript] [Microsoft Word]
• Final Project (due on 1/14) [PostScript] [Microsoft Word]

Lecture Notes

• September 17:
  • Lecture notes: [PostScript] [Microsoft Word]
  • Red-black trees [pdf] (check pages 1 and 2)

• September 19:
  • Lecture Notes: [PostScript] [Microsoft Word]
  • D. D. Sleator and R. E. Tarjan. Self adjusting binary trees. Journal of the ACM, 32(3):652-686, 1985. [pdf]
  • R. E. Tarjan. Amortized Computational Complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1986. (Copies are available outside room 323.)

• September 24:
  • Lecture Notes: [PostScript] [Microsoft Word]

• September 26:
  • Lecture Notes: [PostScript] [Microsoft Word]
  • N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669-679, 1986. [pdf]

• October 1:
  • Lecture Notes: [PostScript] [Microsoft Word]
  • P. Van Emde Boas. Preserving order in a forest in lass than logarithmic time and linear space. Information Processing Letters, 6:80-82, 1977.
  • P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), 1987.

• October 3:
  • Lecture Notes: [PostScript] [Microsoft Word]
  • H. Kaplan, C. Okasaki, and R. Tarjan. Simple confluently persistent catenable list. SIAM Journal on Computing, 30:965-977, 2000.

• October 8:
  • Lecture Notes: [PostScript] [Microsoft Word]
  • E. McCreight. Priority search trees. SIAM Journal on Computing, 14:257-276, 1985.
  • F. Preparata and M. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985. (Pages 13-15 and 352-355 are especially relevant.)
  • J. Bentley and J. Saxe. Decomposable searching problems, I: static-to-dynamic transformation. Journal of Algorithms 1:301-358, 1980.
  • J. Neivergelt and E. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2:301-358, 1980.
  • K. Mehlhorn. Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, 1985, 189-198.

• October 15:
  • Lecture Notes: [PostScript] [Microsoft Word]

• October 17:
  • Lecture Notes: [PostScript] [Microsoft Word]

• November 5:
  • Kevin Wayne talked about generalized minimum cost flows. [slides]
  • K. D. Wayne. A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. Proceedings of the 31st Annual Symposium on the Theory of Computing, 1999. [pdf]

• November 7:
  • No class (field trip to Friend Center to watch Michael Luby's talk on LT Codes).
  • M. Luby. LT Codes. Proceedings of the 43rd annual IEEE Symposium on Foundations of Computer Science (FOCS), 2002.

• November 12:
  • G. Kalai. Linear programming, the simplex algorithm and simple polytopes. Mathematical Programming (Series B), 79:217-234, 1997.

• November 14:
  • D. A. Karger, P. N. Klein, and R. E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, 1995.

• November 19:
  • B. Chazelle. The Soft Heap: An approximate priority queue with optimal error rate. Journal of the ACM, 47(6):1012-1027, 2000.
  • B. Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM, 47(6):1028-1047, 2000.
  • S. Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. Journal of the ACM, 49(1):16-34, 2002.
  • V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18(2):263-270, 1997.

• November 21:
  • T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-141, 1979.
  • A. L. Buschsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook. A new, simpler linear-time dominators algorithm. ACM Transactions on Programming Languages and Systems, 20(6):1265-1296, 1998.

• November 26:
  • Invited lecturer: Adam Buchsbaum, from AT&T Research
  • A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook. Linear-time pointer-machine algorithms for least common acestors, MST verification, and dominators. Proceedings of the 30th ACM Symposium on the Theory of Computing (STOC), 279-288, 1998.

• December 3:
  • J. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974.
  • R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics, 36(2):177-189, 1979.

• December 5:
  • Copy of slides on linear-time algorithm for four-coloring planar graphs given in class.

• December 10:
  • R. E. Tarjan. Two streamlined depth-first search algorithms. Fundamenta Informaticae, 9:85-94, 1986.
  • K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13:335-379, 1976.

• December 12:
  • R. E. Tarjan. Two streamlined depth-first search algorithms. Fundamenta Informaticae, 9:85-94, 1986.
  • N. Pippenger. Superconcentrators. SIAM Journal on Computing, 6(2):298-304, 1977.

• Other references:
  • N. E. Young, R. E. Tarjan, and J. B. Orlin. Faster parametric shortest path and minimum-balance algorithms. Networks, 21:205-221, 1991.
  • J. R. Driscoll, N. Sarnak, and D. D. Sleator. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989.
  • W. Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668-676, 1990.
  • R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23:309-311, 1978.
  • A. V. Goldberg and R. E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM, 36(4):873-886, 1989.
  • A. Subramanian. An explanation of splaying. Journal of Algorithms, 20:512-525, 1996.
  • A. V. Goldberg and R. E. Tarjan. Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research, 15(3):430-465, 1990.

Administrative Information

Lectures: TTh 1:30-2:50, room 402 CS (ocasionally TTh 3:00-4:30, room 401 CS)

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

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