|
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:30-2:50, Room: 402
Precepts: Tue 7:30-8:20, Room: 102
Instructor: Lance Fortnow -
fortnow@cs.princeton.edu
Undergraduate Coordinator:
Tina McCoy -
410 CS Building - 258-1746
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:45-5:45 in Room 003 (in the CS basement).
Course Summary
Formal models of computation ("What is a computer?"): Regular, Context-Free and Decidable languages.
The universality Theorem and the Church-Turning Thesis. Computability Theory
("What can or cannot be computed?") and Complexity Theory ("How
efficient can a certain computation be?"). NP-completeness and PSPACE-
completeness.
Prerequisites: COS 341.