|
Computer Science 423
Theory of Algorithms
Robert Tarjan |
Spring 2002 |
Directory
Course Summary | Administrative Information
| Schedule | Handouts | Problem
Sets/Solutions
What's New
Problem set 5 will be ready for you by May 13th (May 2nd, 2002)
Extra credit problem set online now (May 2nd, 2002)
New handouts from Buchsbaum online now (April 30th, 2002)
Problem Set 6 Online (April 25th, 2002)
Problem Set 5 will be graded by Brian (April 22nd, 2002)
New handout online! (April 19th, 2002)
Tony's office hour and precept time changed back to normal (April 19th, 2002)
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 polynominal 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: TTH 11:00-12:20, Room: CS 104 (Large Auditorium)
Precepts: W 7:00 - 8:00pm, Room: CS 105 (Small Auditorium)
Web page: http://www.cs.princeton.edu/courses/archive/spring02/cs423/
Professor: Robert Tarjan
- 324 CS Building - 258-4797 ret@cs.princeton.edu
Office Hours: TTh 1:00-2:30pm or by appointment
Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly@cs.princeton.edu
TA1: Tony Wirth
- 003 CS Building - 258-2072 awirth@cs.princeton.edu
Office Hours: 2:30pm-3:30pm Wed or by appointment
TA2: Junwen Lai(Brian)
- 414 CS Building - 258-5388 lai@cs.princeton.edu no office hours
TA3: Edith Elkind
- 001b CS Building - 258-1781 elkind@cs.princeton.edu
Office Hours: 4:00pm-5:00pm Fri or by appointment
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 Thursdays at the beginning of
class. You may turn them in the following Tuesday 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 schedule
[2] Disjoint set union
[3] Linear time selection, binary heaps, binomial heaps [Kevin]
[4] All of the binary and binomial heaps [Kevin]
[5] splay tree handout
[6] Planar Point Location handout
[7] Depth-First Search
[8] MST slides
[9] Incredible Shrinking Blossom Algorithm
[10] Max flow problem
[11]Improving Table
Compression with Combinatorial Optimization
[12]Engineering the Compression of Massive Tables
[11]
Problem Sets/Solutions:
[1]/[1] ( due Feb 14th, graded by Tony )
[2]/[2] ( due Feb 28th, graded by Edith )
[3]/[3] ( due Mar 14th, graded by Tony )
[extra]/
[cover] ( due ? )
[4]/[4] ( due April 11th, graded by Edith )
[5]/[5] ( due April 25th, graded by Brian)
[6]/[6] ( due May 16th, graded by ?)
[extra 2]/[?] ( due May 16th, graded by ?)
[6]/[6]