Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Robert Tarjan

Spring 2010

COURSE INFORMATION | LECTURES | ASSIGNMENTS

Course Description



Text: CLRS: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.

Recommendations: Attend class. Much material covered will not be in CLRS, and I will present much material differently from CLRS. I will try to provide additional handouts on material not in CLRS. Read CLRS. It is a basic source. Do the problem sets. Give yourself plenty of time for this.

Administrative Information

Lectures: MW 11:00-12:20, Room: Friend 008

Professor: Robert Tarjan - 324 CS Building - 258-4797 ret AT cs DOT princeton DOT edu

Undergraduate Coordinator: Donna O'Leary - 210 CS Building - 258-1746 doleary AT cs DOT princeton DOT edu

Course Secretary: Mitra Kelly -323 CS Building - 258-4562 mkelly AT cs DOT princeton DOT edu

Teaching Assistants:

Rong Ge - 216 CS Building - 258-5389 rongge AT cs DOT princeton DOT edu, Office hours: Mon and Tue 4 to 5 pm
Anuradha Venugopalan - 103A CS Building - 258-6795 avenugop AT cs DOT princeton DOT edu, Office Hours: Thurs and Fri 5:30 to 6:30 pm

Precept: Tuesdays 7-8pm CS105

Useful Links

Previous semester(s): Spring 2009, Spring 2008, Spring 2007, and previous years.

Useful Sources

Sedgewick, Algorithms in Java, Third Edition, Parts 1-4, Addison-Wesley, 2003.
Sedgewick, Algorithms in Java, Third Edition, Part 5, Addison-Wesley, 2003.

Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., 1979.

Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, 1983.

Kleinberg and Tardos, Algorithm Design, 2005.

Cupillari, The Nuts and Bolts of Proofs, PWS Publishing, 1993.

Polya, How to Solve It, Princeton University Press, 1945.

Problem Sets

"No Collaboration" means work entirely on your own. Try to do the problems without consulting source material (books, papers, the internet), but if you do use such a source, cite it.

"Collaboration allowed" means you can discuss the problems with your classmates, but you should write your solution entirely by yourself. Cite all sources of ideas, be they classmates, books, papers, the internet, or other.