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
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: firstname.lastname@example.org
TA office hours: By Appointment
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: ??
· 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.
· 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.