Princeton University
Computer Science Department

Computer Science 487
Theory of Computation

Amit Sahai

Fall 2002


Directory
General Information

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 PM, Room: 105 CS

Precepts: Th 7:00-8:00 PM, Room: 102 CS

TA Office Hours: M 4:30-5:30, Room: 223 CS

Professor: Amit Sahai - 406 CS Building - 258-0255 sahai@cs.princeton.edu

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

Teaching Assistant: Manoj Prabhakaran - 223 CS Building - 258-0254 mp@cs.princeton.edu
Handouts:

0. Course Announcement
1. Assignment 1
2. Assignment 2
3. Assignment 3
4. Assignment 4
5. Assignment 5
6. Midterm Exam
7. Assignment 6
8. Assignment 7
9. Assignment 8
10. Assignment 9
11. Final Exam


Work done to develop this course was partly supported by the National Science Foundation Award 0205594, and a Sloan Foundation Fellowship.