CSE 431: Introduction to Theory of Computation, Spring 2006

CSE Home

CSE 431 Home

About Us

Search

Contact Info

Email   Archive    Sign-up Instructions Homework Assignments   Assignment #1   Assignment #2   Assignment #3   Assignment #4   Assignment #5   Assignment #6   Assignment #7   Assignment #8   Assignment #8 Solutions Reading Assignments   Sections 8.3-8.5, 9.1   Sections 7.5-8.2   NP reductions   Sections 7.4 and 9.3   Sections 7.1-7.3   Sections 5.2 & 6.3   Sections 5.1 & 5.3   Chapter 4   Chapter 3   Turing and Post Handout   Review Chapters 0-2 Administrative   Sample Midterm   Sample Final Interesting Links   Craig's Halting Problem Page   Davis' The Universal Computer   Hilbert's 23 Problems   David Hilbert Bio   Kurt Godel Bio   Alonzo Church Bio   Alan Turing Bio

Location Mondays, Wednesdays, and Fridays 1:30-2:20    MGH 231 Instructor Paul Beame Office: CSE 668 Phone 206-543-5114 Office Hours: Tuesdays 2:30-3:20, Thursdays 11:00-11:50, or by appointment. Teaching Assistants Ioannis Giotis and Matt Cary Office Hours: Room CSE 220, Wednesdays 3:00-4:00, Thursdays 1:00-2:00, Textbook Michael Sipser, Introduction to the Theory of Computation. Either the first or second editions will work. Although the numbering of almost everything in the two editions is different, the content is mostly unchanged except that the second edition contains some new and solved problems. (Second edition errata: first printing. First edition errata: first printing , second printing . Almost all printings of the 1st edition will not have these errors) Mailing List There is a class mailing list, cse431. Follow the link in the left column on this page to sign up. Everyone is expected to be reading cse431 e-mail to keep up-to-date on the course. Grading Homework 45-55%, midterm 15-20%, final 30-35%, give or take. Extra Credit. Midterm Exam In class Friday, May 5. Here is a sample midterm. Final Exam The final exam will be at the time listed in the official exam schedule which is 2:30-4:20 pm, Monday June 5. The final exam will cover chapters 3, 4, 5, and 7 of Sipser's text as well sections 6.3, 8.1-8.4 and 9.3. A sample final is available. There will be a review session on Sunday, June 4 at 3:30 pm in EE1-037 Catalog Description Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 322. Portions of the CSE 431 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 431 Web: © 1993-2006, Department of Computer Science and Engineering, University of Washington.