Princeton University 
Computer Science 487 

Formal models of computation: finite automata and Turing machines. Universality Theoremand the ChurchTurning Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NPcompleteness and PSPACE completeness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and computer security. Prerequisites: COS 341.
Professor: Andrew Yao  321 CS Building  2585182 yao@cs.princeton.edu
Undergraduate Coordinator: Tina McCoy  410 CS Building  2581746 tmmccoy@cs.princeton.edu
Teaching Assistants: Paul Chang  001A CS Building  2586862 pmchang@cs.princeton.edu