|
Princeton University
|
Computer Science
487
|
|
Directory
General Information | Assignments | Handouts 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 340/341 or equivalent math background.
Administrative Information
Lectures: Tu-Thur 3-4:20, Room: 105. Precepts: Roughly every other
week (time/place TBA)
Professor: Sanjeev
Arora - 307
CS Building - 258-3869 arora@cs.princeton.edu
Office hrs: M 3-4pm, Tue 2-3pm or by appointment.
Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746 doleary@cs.princeton.edu
Teaching Assistant: Aditya Bhaskara,
ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD ACROBAT READER HERE.
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; the later lectures will use portions of Computational Complexity: A Modern Approach by Arora and Barak.
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 open-book.
There might also be a small project to do at the end of the semester.
READINGS
From the Sipser text we covered Chapters 1-4 completely. Then Sections 5.1, 5.3, and 6.2 (but not Theorem 6.17 which uses Section 6.1). Then we covered Chapters 7, 8 in full. (Chapter 4 of Arora-Barak also describes the basic results on space complexity.)For the lecture on hierarchy theorems and limits of diagonalization read Arora-Barak Sections 3.1, 3.2, 3.5. (The other sections may be interesting to read for advanced students.)
For Polynomial Hierarchy, Arora-Barak Sections 5.1, 5.2.
For Circuits and Karp-Lipton Theorem, Arora-Barak Sections 6.1, 6.2.
For cryptography, Arora-Barak Sections 9.1, 9.2. The interactive proof concept is discussed in Chapter 8 but the example in class is all you are expected to understand.
For quantum computing, Arora-Barak Sections 10.1, 10.2 (but not 10.2.1), the Hadamard operation (p 183) and Section 10.5 (Simon's algorithm)
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.