Computer Science 487
Theory of Computation
General Information |
- The Final Exam has now been posted. It is due 4 PM on Friday, January 18.
Lectures: MW 1:30-2:50, Room: 402
Precepts: Tue 7:30-8:20, Room: 102
Instructor: Lance Fortnow -
Tina McCoy -
410 CS Building - 258-1746
Textbook: Introduction to the Theory of Computation by
Michael Sipser. Errata
Tony Wirth -
firstname.lastname@example.org. Office Hours Tuesday and Thursday 4:45-5:45 in Room 003 (in the CS basement).
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-
Prerequisites: COS 341.