MCS-265 materials, Spring 2004


Helpful information
Instructor: David Wolfe (click here for office hour information)
Errata for Sipser, Introduction to the Theory of Computation.
Directions for printing .ps files
Scott Aaronson's Complexity Zoo

Handouts:
Syllabus
Top-down induction
Proof that Integer Linear Programming is NP-complete
Hamilton cycle is NP-complete

Homeworks: Some of these have working pdf versions too; try changing the .ps to .pdf.
Set 0
Set 1 and solution
Set 2 and solution
Set 3 and solution
Set 4 and solution
Set 5 and solution
Set 6 and solution
Set 7 and solution
Set 8 and solution
Set 9

Exams: (tentative schedule)
Oral exam on Thursday, February 25
Exam 2 on Thursday, March 18
Exam 3 on Thursday, April 29
Exam 4 on Tuesday, May 25 at 10:30.