
Computer Science 487
Theory of Computation
Amit Sahai 
Fall 2002 
Directory
General Information
Course Summary
Formal models of computation: finite automata and Turing machines.
Universality Theoremand the ChurchTurning Thesis. Computability Theory
("What can or cannot be computed?") and Complexity Theory ("How
efficient can a certain computation be?"). NPcompleteness and PSPACE
completeness. An introduction to complexity issues in application areas such
as robotics, graphics, compilers, and computer security.
Prerequisites: COS 341.
Administrative Information
Lectures: MW 1:302:50 PM, Room: 105 CS
Precepts: Th 7:008:00 PM, Room: 102 CS
TA Office Hours: M 4:305:30, Room: 223 CS
Professor: Amit Sahai 
406 CS Building  2580255
sahai@cs.princeton.edu
Undergraduate Coordinator:
Tina McCoy 
410 CS Building  2581746
tmmccoy@cs.princeton.edu
Teaching Assistant:
Manoj Prabhakaran 
223 CS Building  2580254
mp@cs.princeton.edu
Handouts:
0. Course Announcement
1. Assignment 1
2. Assignment 2
3. Assignment 3
4. Assignment 4
5. Assignment 5
6. Midterm Exam
7. Assignment 6
8. Assignment 7
9. Assignment 8
10. Assignment 9
11. Final Exam
Work done to develop this course was partly supported by the National
Science Foundation Award 0205594, and a Sloan Foundation Fellowship.