|
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 (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: http://www.cs.princeton.edu/courses/archive/spring03/cs423/
Professor: Robert Tarjan
- 324 CS Building - 258-4797 ret@cs.princeton.edu
Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly@cs.princeton.edu
TA1: Subhash Khot
- 316 CS Building - 258-5386 khot@cs.princeton.edu. Office
hours: Tuesday 11-12pm
TA2: Elisha Ziskind
- 103C CS Building - 258-0419 eziskind@cs.princeton.edu.
Office hours: Thursday 2-3pm
Undergraduate Coordinator: Tina
McCoy - 410 CS Building - 258-1746 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 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.
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] 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 )