Princeton University Computer Science Department

Computer Science 487 Theory of Computation Andrew Yao

Fall 2003

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.

Announcements

Midterm Exam: November 5 (Wednesday) in class

(Take-Home) Final Exam: Problems to be posted here on January 9, 2004

Solutions to Final Exam

Administrative Information

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

Precepts: Thursdays 7:30-8:20 pm, Room: 102

Professor: Andrew Yao - 321 CS Building - 258-5182 yao@cs.princeton.edu

Undergraduate Coordinator: Tina McCoy - 410 CS Building - 258-1746 tmmccoy@cs.princeton.edu

Teaching Assistants: Paul Chang - 001A CS Building - 258-6862 pmchang@cs.princeton.edu