Princeton University
Computer Science Dept.

Computer Science 487
Theory of Computation

Sanjeev Arora

Fall 2000

General Information | Assignments | Handouts | Final Exam | What's New? |Interesting Links|


Course Summary

Formal models of computation: finite automata and Turing machines. Universality Theorem and 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, Room: 103. Precepts: Roughly every other week Thur 7-8 in Room 103.

Professor: Sanjeev Arora - 307 CS Building - 258-3869 Office hrs: MW 3-4pm or by appointment.

Undergraduate Coordinator: Tina McCoy - 410 CS Building - 258-1746

Teaching Assistants: Subash Khot, CS 412. Office hrs: Thu 2-3, Fri 11-12 or by appointment.


Course information

Topics: Finite automata and  regular languages. Context-free grammars and push-down 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, NP-completeness and PSPACE-completeness. 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 open-book.

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. Due by Tuesday Jan 16.  Give yourself 24 hours for the exam (see instructions on 1st page).

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