John H. Reif
Spring Semester, 2007
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
Times:
Lecture Times: Mon,
Wednesday Friday, 1:00 PM-2:30 PM (Room LSRC D243)
Reif Office
Hours:
Wed, 11:00-12:30 (D223)
TA: Urmi Majumder
TA email:
urmim@cs.duke.edu
TA
office hours: By Appointment
Required Class
Text Books: ([AB] and [G] used by permission)
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:
· 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.