Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Robert Tarjan

Spring 2003

Course Summary | Administrative Information | Handouts | Problem Sets

What's New

[5/16] PS 6 is ready for pickup outside room 323
[5/2] PS 5 solutions online
[4/25] PS 6 online
[4/21] NO precept tonight
[4/16] PS 5 updated again
[4/14] PS 5 updated
[4/9] PS 5 online
[4/1] PS 4 updated again
[3/31] PS 4 updated
[3/26] PS 4 online
[3/5] Updated PS 3 (new due date) and "Graph, search, components" notes
[3/5] Problem set 3 online
[2/27] PS 2 corrected again
[2/26] Disjoint set class notes (hand-written and typed) posted
[2/24] Note: Collaboration is allowed for PS2
[2/19] Corrected problem set 2 posted
[2/19] Problem set 2 online
[2/18] There will be a makeup precept tonight (Tuesday) 6:30-7:30pm, usual place (rm 105).
[2/10] Problem set 1 and course info online

Course Summary

This course is designed to provide students with an understanding of the principles and techniques used in the design and analysis of computer algorithms. The course is primarily theoretical and does not require programming, but it does require understanding of the notion of a mathematical proof and some knowledge of elementary discrete mathematics. We will discuss and analyze a variety of data structures and algorithms chosen for their importance and their illustration of fundamental concepts. We shall emphasize analyzing the worst-case running time of an algorithm as a function of input size. We shall also spend some time exploring the boundary between feasible computations, taken to be those doable in polynomial time, and infeasible computations. This will include discussion of the notorious P=NP? Question. Prerequisites: COS 226 and COS 341 or permission of the instructor.

Administrative Information

Lectures: MW 11:00-12:20, Room: CS 105 (Small Auditorium)

Web page:

Professor: Robert Tarjan - 324 CS Building - 258-4797

Secretary: Mitra Kelly - 323 CS Building - 258-4562

TA1: Subhash Khot - 316 CS Building - 258-5386 Office hours: Tuesday 11-12pm

TA2: Elisha Ziskind - 103C CS Building - 258-0419 Office hours: Thursday 2-3pm

Undergraduate Coordinator: Tina McCoy - 410 CS Building - 258-1746

Required Text:

Corman, Leiserson, Rivest and Stein, Introduction to Algorithms, Second Edition, MIT Press, 2001.

Useful Resource:

[1] Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., 1979
[2] Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, 1983.
[3] Cupillari, The Nuts and Bolts of Proofs, PWS Publishing, 1993.

Course Work:

There will be about six problem sets based on material in the book or covered in lectures. The problems will range from medium-hard to challenging. You should not necessarily expect to solve all parts of all problems, but you should read, think about, and try hard to solve all of them, allowing yourself plenty of time before the problems are due to think about and work on them.

Help on problem sets:

You will be graded both on the correctness of your solutions and on the clarity and conciseness of your exposition. On problem sets allowing collaboration, you may discuss the problems with others and consult reference materials. However, your solution write-ups should be entirely your own, and you should carefully cite outside sources of ideas, whether they are friends, research papers, or books. To learn the most, you should first try each problem entirely on your own, without outside help. On problem sets not allowing collaboration, all your ideas and all your work should be on your own.

Late Problem Sets:

Problem Sets will be due on Wednesdays at the beginning of class. You may turn them in the following Monday for half credit. Any late submissions will receive no credit, unless there are serious extenuating circumstances.


Attend class: Some material covered will not be in the book, and I will present some material differently from the book.
Read the Book: It is a basic source.
Do the problem sets: Give yourself plenty of time for this.


[1] Course information
[2] Course schedule
[3] Material covered in CS 226
[4] Disjoint set notes (transparencies)
[5] Disjoint set notes (notes)
[6] Sorting, selecting and searching (transparencies)
[7] Graph, search, components (transparencies)
[8] Depth first search (notes)
[9] Path-based depth-first search for strong and biconnected components (Gabow)
[10] Properties of depth first search (transparencies)
[11] A fast algorithm for finding dominators in a flowgraph (Lengauer & Tarjan)
[12] Planar graphs (transparencies)
[13] Master-keyed mechanical locks fall to cryptographic attack (SIAM News)
[14] Shortest paths (transparencies)
[15] Minimum Spanning trees (transparencies)
[16] Thinning by random sampling (transparencies)
[17] Maximum network flow (transparencies)
[18] Minimum-cost network flow (transparencies)
[19] Edmond's incredible shrinking blossom algorithm (notes)
[20] Matching (transparencies)
[21] Reductions (transparencies)
[22] NP Complete (transparencies)
[23] Coping with NP Completeness (transparencies)
[24] Peculiar problems (transparencies)

Problem Sets:

[1] ( due Feb 19th )
[2] ( due Mar 5th )
[3] ( due Mar 26th ) Solutions
[4] ( due Apr 9th )
[5] ( due Apr 23th ) Solutions
[6] ( due May 13th )