CPS 240 : Computational Complexity


Name: Pankaj K. Agarwal
Office: D207 LSRC Bldg
Phone: 660-6540


CPS 140 or equivalent.


Grading Policy

Text Book

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. M. Davis, R. Sigal, and E. Weyuker, Computability, complexity, and languages, Academic Press, Boston, 1994.
  5. D.-Z. Du and K.-I Ko, Theory of Computational Complexity, Wiley Interscience, New York, 2000.
  6. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman and Company, New York, 1979.
  7. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, Reading, MA, 1974.
  8. H. Rogers, Theory of Recursive Functions and Effective Computability, The MIT Press, Cambridge, MA, 1988.

Course Synopsis


Summary of Lectures

Agarwal's Home Page

Pankaj Kumar Agarwal
January 8, 1999