
Computer Science 487
Theory of Computation
Lance
Fortnow 
Fall 2001 
Directory
General Information 
Assignments
Announcements
 The Final Exam has now been posted. It is due 4 PM on Friday, January 18.
Administrative Information
Lectures: MW 1:302:50, Room: 402
Precepts: Tue 7:308:20, Room: 102
Instructor: Lance Fortnow 
fortnow@cs.princeton.edu
Undergraduate Coordinator:
Tina McCoy 
410 CS Building  2581746
tmmccoy@cs.princeton.edu
Textbook: Introduction to the Theory of Computation by
Michael Sipser. Errata
Teaching Assistant:
Tony Wirth 
awirth@princeton.edu. Office Hours Tuesday and Thursday 4:455:45 in Room 003 (in the CS basement).
Course Summary
Formal models of computation ("What is a computer?"): Regular, ContextFree and Decidable languages.
The universality Theorem and 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.
Prerequisites: COS 341.