John H. Reif
Spring Semester, 2009
Instructor: John H. Reif
A.
Hollis Edens Professor of Computer Science
D223
LSRC Building
E-mail:
reif AT cs.duke.edu
Phone:
919-660-6568
Summary
Description of Course:
Computational
Complexity is the study of bounds on the various metrics (such as time and
space) of computations executed on abstract machine models (such as Turing
machines, Boolean circuits),, required to solve given problems, as a function
of the size of the problem input.
Detailed Description of Course Material: see Schedule
Lectures:
Lecture Times:
(See Schedule
for details)
Lecture
Location: Room North 306
Reif Office Hours:
Mon,
Wed, Fri 11:00 AM - Noon D223 LSRC Building
TA: To be determined
· TA email: To be determined
· TA office hours: To be determined
Required
Hardcopy Text Book:
[Pap]
Christos Papadimitriou. Computational Complexity. Addison-Wesley Longman, 1994. ISBN-10: 0201530821, ISBN-13:
978-0201530827. Corrections: Errata.
Additional
Digital Text Books: ([AB] and [G] used by permission)
Surveys on Computational
Complexity:
Prerequisites:
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
Grading:
(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.
Homeworks: To be prepared using LATEX (preferred) or WORD.
· 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.