Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Robert Tarjan

Spring 2011



COURSE DESCRIPTION

Description: 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, some knowledge of elementary discrete mathematics, and mathematical problem-solving skills. We shall 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 (polynominal-time) computations and infeasible computations. This will include discussion of the notorious P=NP? question.

Prerequisites: COS 226 and COS 340 or permission of the instructor

Lectures: MW 11:00-12:20, Room: FC 006

Precept 1: F 11:00-11:50, Room: CS Building 302
Precept 2: F 1:30-2:20, Room: CS Building 302

Recommendations: ATTEND CLASS. There is no required text for this course and I will be developing course material as the course proceeds. You may miss ideas if you do not attend, and you may find the posted materials perplexing. Give yourself plenty of time to do the problem sets. Search on the web for additional information on the topics presented.


ADMINISTRATIVE INFORMATION

Instructor: Robert Tarjan
Office: 324 CS Building, 258-4797
Office Hours: MW 1-3 and by arrangement
ret AT cs ...
prof.tarjan AT gmail DOT com

Teaching Assistants
Huy Nguyen
Office: 416 CS Building, 258-6304
Office Hours: Thursday 10-12
hlnguyen AT cs ...

Yuri Pritykin
Office: 417 CS Building, 258-6324
Office Hours: Tuesday 1-3
pritykin AT cs ...

Administrative Assistant: Mitra Kelly
Office: 323 CS Building, 258-4562
mkelly AT cs...

Undergraduate Coordinator: Colleen Kenny-McGinley
Office: 210 CS Building - 258-1746
ckenny AT cs ...


USEFUL LINKS

Previous semester(s):
Spring 2010 and previous spring semesters.

COS 226 Fall 2010 and previous semesters.

COS 340 Fall 2010 and previous fall semesters.


RECOMMENDED TEXT

CLRS: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, Addison-Wesley, 2009. Much of the material I shall cover is covered (differently) in this book. Although CLRS was required in previous years, it is not required this year; I will post material on all the topics I discuss. Nevertheless, reading CLRS is a way to gain additional understanding. I shall cite chapters and sections related to class presentations, and may take some problems from this book.


USEFUL SOURCES

R. Sedgewick and K. Wayne, Algorithms, (Preliminary) Fourth Edition, Addison-Wesley, Fall, 2010, and previous editions, in particular R. Sedgewick, Algorithms in C, Third Edition, Parts 1-4, and Part 5, Addison-Wesley, 2002. (on reserve in the Engineering Library for COS 226)

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.