The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE P590TU:Complexity Theory, Autumn 2003
  CSE Home  About Us    Search    Contact Info 

  Sign-up Instructions
Homework Assignments
  Assignment 8
  Assignment 7
  Assignment 6
  Assignment 5
  Assignment 4
  Assignment 3
  Assignment 2
  Assignment 1
Reading Assignments
  Sipser Chapter 10: 10.2,10.6,10.4
  Sipser Chapter 8: 8.1-8.5
  Sipser Sections 7.4 & 9.3
  Sipser Chapter 7: 7.1-7.3
  Sipser Chapter 5: 5.1 & 5.3
  Sipser Chapter 4
  Sipser Chapter 3
  Turing and Post Handout
  Emergency Text
  Sample Final Questions
Computability Links
  Craig's Halting Problem Page
  David Hilbert Bio
  Kurt Godel Bio
  Alonzo Church Bio
  Alan Turing Bio
NP-completeness Links
  Garey & Johnson
  Optimization Compendium
  Powerpoint Slides
W 6:30-9:20 p.m.    EE1 037

Office Hours Location Phone
Instructor: Paul Beame   beame@cs  
Wednesdays 4:30-5:30 and by appointment
CSE 668 206-543-5114
TA: Iannis Giotis   giotis@cs   Wednesdays 5:00-6:30 CSE 216


Grading: There will be weekly homework assignments and a final exam. Course grades will be based on roughly 2/3 on homework and 1/3 on the final exam although this could vary up to 5-7%.

Mailing List: There is a class mailing list, Follow the link in the left column on this page to sign up. Everyone is expected to be reading csep590tu e-mail to keep up-to-date on the course.

Final Exam TIME CHANGE: Two hours on the evening of Wed Dec 10, 7:00-8:50 pm. Note that this is different from the official exam schedule and has been agreed to without objection by the class.
Sample Final Questions

Suggestions or Comments? You can send comments to the instructor or TA using this anonymous feedback form

Catalog Description: Survey of the theory of computation including Turing Machines, Church's Thesis, computability, incompleteness, undecidability, complexity classes, problem reductions, Cook's theorem, NP-completeness, randomized computation, cryptography, parallel computation, and space complexity. Some emphasis will be placed on historical and philosophical aspects of the theory of computation.

Portions of the CSEP590TU Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSEP590TU Web: © 1993-2003, Department of Computer Science and Engineering, University of Washington.