CPS 240 : Computational Complexity

Instructor

Name: Pankaj K. Agarwal
Office: D214A LSRC Bldg
Phone: 660-6540
E-mail:pankaj@cs.duke.edu

Prerequisite

CPS 140 or equivalent.

Students

Grading Policy

• 4 Homeworks; weight 20%
• One midterm; weight 20%
• Final: weight 40%

Text Book

• C.H. Papadimitriou, Computational Complexity, Addison Wesley, Reading, MA, 1993.

Reference Books

1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation , Springer-Verlag, Heidelberg, 1999.
   
2. J. Balcazar, J. Diaz, J. Gabarro, Structural Complexity I, Springer-Verlag, Heidelberg, 1988.
   
3. J. Balcazar, J. Diaz, J. Gabarro, Structural Complexity II, Springer-Verlag, Heidelberg, 1988.
   
4. D.-Z. Du and K.-I Ko, Theory of Computational Complexity, Wiley Interscience, New York, 2000.
   
5. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman and Company, New York, 1979.
   
6. J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, Reading, MA, 2001.
   
7. H. Rogers, Theory of Recursive Functions and Effective Computability, The MIT Press, Cambridge, MA, 1988.

Course Synopsis

Assignments

• Assignment 1 Due date: Feb 11, 2003
• Assignment 2 Due date: Feb 25, 2003
• Assignment 3 Due date: March 17, 2003
• Assignment 4 Due date: April 23, 2003
• Final Exam Due date: April 30, 2003

Summary of Lectures