Directory
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
rjl@cs.princeton.edu
Undergraduate Coordinator:
Tina McCoy -
410 CS Building - 258-1746
tmhill@cs.princeton.edu
Teaching Assistants:
