



Location
Mondays, Wednesdays, and Fridays 9:3010:20 Loew 216
Instructor
 Paul Beame
 Office: CSE 668 Phone 2065435114
 Office Hours: Mondays and Wednesdays 10:2010:50. Wednesdays 3:003:50.
Teaching Assistants
 Widad Machmouchi
 Office Hours: Thursdays 12:001:00 CSE 220 and 2:303:20 CSE 216
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 corrections and new and solved problems.
(Second edition errata: all printings. First edition errata:
first printing ,
second printing and beyond.)
There is also an international edition but the numbering of
problems in that edition is different from the other two so you should not rely on it for homework.
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 email to keep uptodate on the course.
Grading
Homework 4555%, midterm 1520%, final 3035%, give or take. Extra Credit.
See the homework policy
Midterm Exam In class, Wednesday, May 6. Closed book, Closed notes.
This will cover up to the end of the material on computability. There will
be a review session in CSE 303 on Tuesday May 5 at 4:30. Sample Midterm
Final Exam The final exam will be at the time listed in the
official exam
schedule which is 8:3010:20 am, Wednesday June 10.
The final exam will be comprehensive up to and including space complexity though it will emphasize topics in the latter half of the course.
There will be a review session on Tuesday, June 9, at 12:30 pm in room CSE 403.
Here is a sample final from a previous class.
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: © 19932009, Department of Computer Science
and Engineering, University of Washington.
