CPS 240: COMPUTATIONAL COMPLEXITY
CPS 240 : Computational Complexity
Instructor
Name: Pankaj K.
Agarwal
Office: D207 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
-
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A.
Marchetti-Spaccamela, and M. Protasi,
Complexity and Approximation , Springer-Verlag, Heidelberg,
1999.
-
J. Balcazar, J. Diaz, J. Gabarro,
Structural Complexity I, Springer-Verlag, Heidelberg,
1988.
-
J. Balcazar, J. Diaz, J. Gabarro,
Structural Complexity II, Springer-Verlag, Heidelberg,
1988.
-
M. Davis, R. Sigal, and E. Weyuker,
Computability, complexity, and languages,
Academic Press, Boston, 1994.
-
D.-Z. Du and K.-I Ko,
Theory of Computational Complexity,
Wiley Interscience, New York, 2000.
-
M. Garey and D. Johnson,
Computers and Intractability: A Guide to the
Theory of NP-Completeness, Freeman and Company,
New York, 1979.
- J. Hopcroft and J. Ullman,
Introduction to Automata Theory, Languages and
Computation,
Addison Wesley, Reading, MA, 1974.
- H. Rogers,
Theory of Recursive Functions and Effective
Computability,
The MIT Press, Cambridge, MA, 1988.
Assignments
Agarwal's Home Page
Pankaj Kumar Agarwal
January 8, 1999