|
Computer Science 521
Advanced Algorithm Design
Robert Tarjan |
Fall 2002 |
Directory
General Information
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).
Lecture Notes
- September 17:
- 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:
- 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:
- October 17:
- 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
Webmaster: Renato Werneck - rwerneck@cs.princeton.edu