|
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.