December 2: Here are some suggested exercises to help study for test.
Please note date of Midterm 3: it will be in class, December 7, 2009. There will not be a final exam.
Course news will be posted here as needed. Please check frequently (don't forget to refresh), especially right before assignments and tests.
September 8, 2009:
Room change: Course location has been changed again by the
Registrar's office to Accolade East 012, as announceed in class.
Office hours: after class Wednesday in classroom or in CSEB 3052c (by appointment.)
Email questions about fairly specific problems are welcome.
Important note concerning late enrollment:
Late enrollment in this course is not appropriate
unless the student has been attending classes since the beginning lectures,
and has also been keeping up with the readings and assignments.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern
Approach, Cambridge University Press, 2009.
The main focus of the course is the material from part 1 of the
the Arora/Barak (AB) text.
Familiarity with definitions and other material from automata theory
(such as that gained in CSE 2001) is needed.
CSE 2001, CSE 3101, general fourth-year CSE prerequisites.
This course is an introduction to the theory of computational complexity. It is intended to give a detailed understanding of the basic concepts of models of computation, computability, and complexity theory. Topics chosen for study include: Turing machine variants and Random Access Machines, the Church-Turing thesis, limits to computation, Turing-recognizable and decidable languages, complexity of resources such as Time and Space, reducibility, simulation, complexity classes, hierarchy theorems, the relationships between P, NP and other classes, NP-completeness, completeness for P, PSPACE and other classes, provable intractability and interactive proof systems. We will also discuss probabilistic computation and applications to parallel computing and/or cryptography if time permits.
Students attend and participate in the twice-weekly classes, read assigned material from the text in advance of corresponding lectures and prepare individual, well-written answers for assignments and/or exercises. There will be approximately three written assignments. This component counts for 30% of the final grade. There will be two ninety minute in-class tests counting for 25% each, and one final in-class test, counting for 20% of the final grade. These tests are currently scheduled in class on October 19, November 11, and December 7. N.B. If you cannot attend these midterms, you should not enroll in the course. I will provide notice in class and here well in advance of any necessary changes to these dates.
(Please note that there are no special provisions
for making up late exercises,
assignments or missed classes or tests.
Without sufficient medical documentation that you were
both medically unable to perform the required tasks and
unable to contact the instructor throughout the period prior
to the scheduled date, missed material is assigned a score of zero.
If problems arise in meeting a deadline, please contact the instructor by email
well in advance. )
You should avoid plagiarism and fully cite all resources used in
preparing your solutions to exercises and assignments.
You are allowed to discuss problems with others in the class, but do not
make written notes. Prepare your written solution to problems on
your own and do not share it with others. Properly acknowledge all
sources of help and ideas.
Please also read over the department and faculty policies concerning this.
Handing in solutions found to be based on the work of others,,
or on internet or other external resources
leads to serious repercussions.
Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.
Assignment due dates will be announced modified here later. I expect Assignment 1 to be due October 7.
Readings for background: (Please go over this material in the first
two or three weeks of term, if not before.)
Arora&Barak (AB): Ch 0, Appendix A.1
Lecture 1 (Sept 9): AB: Intro, 0, A1, 1.1, 1.2, 1.3
Lecture 2 (Sept 14): AB: 1.3, 1.4, Supplemental
Lecture 3 (Sept 16): AB: 1.5, 1.6
Lecture 4 (Sept 21): AB 1.6, 1.7
Lecture 5 (Sept 23): AB: 2.1, 2.2
Lecture 6 (Sept 28): AB:, 2.3
Lecture 7 (Sept 30): AB: 2.4
Lecture 8 (Oct 5): AB: 2.4 plus supplemental
Lecture 9 (Oct 7): AB: 2.5, 2.6, 2.7
Reading Week (Oct 12-16) - no lectures
TEST #1 - Monday, Oct 19
-->
Some recommended exercises from the text here .