Princeton University
Computer Science Dept.

Computer Science 487
Theory of Computation

Richard J. Lipton

Fall 1999

General Information | Assignments | Solutions | Handouts | Final Exam | What's New?

Course Summary

Formal models of computation: finite automata and Turing machines. Universality Theoremand 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. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and computer security. Prerequisites: COS 341.

Administrative Information

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

Professor: Richard J. Lipton - 311 CS Building - 258-4646

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

Teaching Assistants: