**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:**