ANNOUNCEMENTS
READING
The required text for this course is:
C.H. Papadimitriou. Computational
Complexity. This book is available on-line and at the
Columbia University bookstore.
This is an excellent introduction
to complexity theory. However, much of the material from the
the second half of the course is not covered in this book,
so it is crucial that you attend lectures.
The following books may also be useful. In addition to these
books, additional
references for advanced topics may be given later in the course.
M.J. Sipser. Introduction to the Theory of Computation.
This is a more introductory book than Papadimitriou; it has very
clear explanations but doesn't cover very much of the material we'll be
doing in this course.
M. R. Garey & D. S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-completeness.
The classic work on NP-completeness.
D. Z. Du and K. Ko. Theory of Computational Complexity.
An advanced book with lots of details about many topics.
J..E. Hopcroft and J.D. Ullman. Introduction to Automata Theory,
Languages, and Computation. Somewhat terse, but a good reference for
much of the material we'll be covering early in the course.
Your problem sets must be turned in as LaTeX documents. If you're unfamiliar with
LaTeX, click here
for an introduction. All problem sets must be submitted in an email to
Andrew Wan
by 5:00pm of the due date or they will be considered late.
Be sure that your LaTeX source code compiles correctly before you send it;
you will be penalized if your code does not compile.
Please submit both
the LaTeX source code (the file that ends with .tex) and the .ps file.