Princeton University
Computer Science Department

Computer Science 487
Theory of Computation

Lance Fortnow

Fall 2001

General Information | Assignments


Administrative Information

Lectures: MW 1:30-2:50, Room: 402

Precepts: Tue 7:30-8:20, Room: 102

Instructor: Lance Fortnow -

Undergraduate Coordinator: Tina McCoy - 410 CS Building - 258-1746

Textbook: Introduction to the Theory of Computation by Michael Sipser. Errata

Teaching Assistant: Tony Wirth - 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.