Assignment 2 is here.
Course news will be posted here as needed. Please check frequently (don't forget to refresh), especially right before assignments and tests.
Office hours: after class Monday at 7 p.m., 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.
Michael Sipser, Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, 2005.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern
Approach, Part 1, 2007.
(Book Draft, will be available on-line or through class handouts.)
The main focus of the course is the material from part 1 of the
the Arora/Barak (AB) text, much of which is also covered in
chapters 3, 4, 5.3 and 7 through 10 of the Sipser book.
Familiarity with definitions and other material from automata theory
(such as that gained in CSE 2001) is needed.
CSE 2001, CSE 3101, general 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 1, November 5, and December 3. I will provide notice in class and here well in advance of any necessary changes.
(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 and listed here as the term progresses.
Assignment due dates may be modified here later.
Readings for background: (Please go over this material in the first two or three weeks of term, if not before.)
Sipser: Chapter 0, 1.2 up to p. 55, 3.1, Appendix A
Arora&Barak (Arora): - Appendix A1, A2.
Lecture 1 (Sept 5): Arora: 0, A1, A2 and Sipser: 3
Lecture 2 (Sept 10): Arora: 1.1-1.2 and Sipser: 3
Lecture 3 (Sept 12): Arora: 1.3-1.4 and Sipser: 5.1 (up to bottom of page 192)
-->
A set of recommended exercises from the texts will be provided in class.