Princeton University

Computer Science 487


Directory
General Information  Assignments  Handouts
 Final Exam  What's New? Interesting Links
Formal models of computation: finite automata and Turing machines. Universality Theorem and 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: Sanjeev Arora  307 CS Building  2583869 arora@cs.princeton.edu Office hrs: MW 34pm or by appointment.
Undergraduate Coordinator: Tina McCoy  410 CS Building  2581746 tmmccoy@cs.princeton.edu
Teaching Assistants: Subash Khot, CS 412. khot@cs.princeton.edu Office hrs: Thu 23, Fri 1112 or by appointment.
ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD ACROBAT READER HERE.
Course information
Topics: Finite automata and regular languages. Contextfree grammars and pushdown automata. Computability theory: halting problem, computability, and Godel's incompleteness theorem. Complexity theory: time and space hierarchy theorems, polynomial time computations, P v/s NP, NPcompleteness and PSPACEcompleteness. Connections to applications areas. The textbook is Sipser's Theory of Computation; an errata list is being maintained here.
Grading: 50% of the grade will be based upon assignments, which will
be handed out every two weeks. Only 80\% of the assignment problems count towards your
grade (i.e., at the end of the semester you get a full score if you correctly answer four
out of every five problems assigned in homeworks).
There will be two takehome exams (in October and December).
The exams are openbook.
There might also be a small project to do at the end of the semester.
FINAL AVAILABLE HERE: Read
only when you’re ready to work on it.
CLARIFICATIONS: Qs 1 should include parentheses ( and ) in the language. In Qs 6, you must give a statement that is true yet unproveable. (Otherwise the question is trivial.) In Qs. 4 you can if you need toassume that you know the constants in the running time O(n^3).
Honor Code for this class
Collaborating with your classmates on assignments is OK and even encouraged. You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these other sources is strictly prohibited.