Princeton University

Computer Science
487/Math 487


Directory
General Information  Assignments  Handouts  Interesting
Links
Formal models of computation: finite automata and Turing machines. Universality of the model and the ChurchTurning Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). The P vs NP question and its status. NPcompleteness and PSPACE completeness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and cryptography. Introduction to some more advanced issues, such as "Why are we stuck on the P vs NP question?" "What is the power of randomness?" "What are zero knowledge proofs?" "Can quantum computers be much more powerful than current computers?" Prerequisites: COS 340/341 or equivalent math background (basically, ability to do math proofs).
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 January). The take
home exam in January can be downloaded from this page on the first day
of reading period.
The exams are openbook.
There might also be a small project to do at the end of the semester.
Professor: Sanjeev
Arora  307
CS Building  2583869 arora@cs.princeton.edu
Office hrs: MW 34pm, or by appointment.
Undergraduate Coordinator: Donna O'Leary  410 CS Building  2581746 doleary@cs.princeton.edu
Teaching Assistant: Chris Beck
ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD ACROBAT READER HERE.
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 or any other sources is strictly prohibited.