
Computer Science 423
Theory of Algorithms
Robert Tarjan 
Spring 2003 
Directory
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 (handwritten 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:307: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 worstcase 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:0012:20, Room: CS 105 (Small Auditorium)
Web page: http://www.cs.princeton.edu/courses/archive/spring03/cs423/
Professor: Robert Tarjan
 324 CS Building  2584797 ret@cs.princeton.edu
Secretary: Mitra Kelly  323 CS Building  2584562 mkelly@cs.princeton.edu
TA1: Subhash Khot
 316 CS Building  2585386 khot@cs.princeton.edu. Office
hours: Tuesday 1112pm
TA2: Elisha Ziskind
 103C CS Building  2580419 eziskind@cs.princeton.edu.
Office hours: Thursday 23pm
Undergraduate Coordinator: Tina
McCoy  410 CS Building  2581746 tmmccoy@cs.princeton.edu
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 NPCompleteness, 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 mediumhard 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 writeups 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.
Recommendations:
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.
Handouts:
[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] Pathbased depthfirst
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] Masterkeyed 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] Minimumcost 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 )