Course news will be posted here as needed. Please check frequently (don't forget to refresh), especially right before assignment due dates and tests.
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.
Michael Sipser, Introduction to the Theory of Computation, Second Edition, Thomson Course Technology 2006.
A list of Errata for the Sipser book can be
found here.
The main focus of the course is the material from part 3 of the
the Sipser text, plus material from section 5.3.
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 several 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 18, November 15, and December 8.
N.B. If you cannot attend these midterm tests, you should not enroll in the course.
I will provide notice in class and here well in advance of any necessary
changes to the test and assigment 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 entirely 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. References are to chapters and sections in the Sipser text book.
Assignment due dates will be announced modified here later.
Readings for background: (Please review this material in the first
week of term, if not before.)
Chapters 3 and 4.
Lecture 1 (Sept 13): Intro and Ch. 3
Lecture 2 (Sept 15): 3 and 4
Lecture 3 (Sept 20): 5.3
Lecture 4 (Sept 22): 5.3
Lecture 9 (Oct 20):
-->
Some recommended exercises from the text here .