CSE P590TU:Complexity Theory, Autumn 2003

CSE Home

About Us

Search

Contact Info

Email   Archive    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 Administrative   Syllabus   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 Textbook: Michael Sipser, Intro. to the Theory of Computation, PWS Publishing, 1997. A copy is on reserve in the Engineering Library. (Book Errata: first printing , second printing .) 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, csep590tu@cs.washington.edu. 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.