CPS 240: Computational Complexity

Department of Computer Science

Duke University

John H. Reif
   Spring Semester, 2007

John H. Reif

         A. Hollis Edens Professor of Computer Science

         D223 LSRC Building

         E-mail: reif AT cs.duke.edu

         Phone: 919-660-6568



     Lecture Times: 
               Mon, Wednesday Friday, 1:00 PM-2:30 PM   (Room LSRC D243)
     Reif Office Hours:  
        Wed, 11:00-12:30   (D223)

Urmi Majumder

                        TA email:  urmim@cs.duke.edu

TA office hours:  By Appointment

Required Class Text Books: ([AB] and [G] used by permission)


There are no formal prerequisites for the course, except mathematical maturity.  However, it would help to have a working knowledge of Turing Machines, NP-Completeness, and Reductions, at the level of an undergraduate algorithms class.

Topics: see above Schedule


(Tentative) There will be 4 homeworks (5% each, 20% total), a quiz on reductions (10%), a midterm exam (10%), an end-term Final Exam (25%), and a Final Project  (30%) for the course.  Also attendance and class interaction will provide an additional 5% of the total grade.


·      Homework4: Assigned: ??  Due: ??

Homework Rules:

·      Be sure to provide enough details to convince me, but try to keep your answers to at most one or two pages.

·      It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.

·      It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.

·      There is no credit given for homework past their due date.

Final Project:

·      The final project is a short (at most 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in complexity theory.

·      The topic is of your choice, and the instructor will provide guidance on relevant literature.

·      Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.