



Location
Mondays, Wednesdays, and Fridays 10:3011:20 Mary Gates Hall 228
Instructor
 Paul Beame
 Office: CSE 668 Phone 2065435114
 Office Hours: MWF 11:2011:50, and W 2:002:50
Teaching Assistant
 Vincent Liew
 Office Hours: Wednesdays 3:004:00 CSE 220, Thursdays 2:003:00 CSE 021
Textbook
Michael Sipser,
Introduction to the Theory of Computation.
Any of the first, international, second or third editions will work.
Earlier editions are less than one quarter the cost of the third edition online.
Although the numbering of almost everything in the first and
international editions are
different from the others, the content is mostly unchanged except for
some corrections and new and solved problems in each subsequent edition.
The third edition has an extra section 2.4 on deterministic contextfree languages that we won't cover anyway.
See errata links from Sipser's book page for lists of errors and corrections.
Mailing List
Course annoucements will be made on the class mailing list, cse431a_sp17.
Grading
Homework 4555%, midterm 1520%, final 3035%, give or take. Extra Credit.
See the homework policy
Midterm Exam Friday May 5 in class. A sample midterm gives some idea of the content that it will cover. There will be a review session on May 4 at 5:00 in room CSE 305.
Final Exam The final exam will be at the time listed in the
official exam
schedule which is 8:3010:20 pm, Monday June 5.
Here is an old final exam from a prior quarter.
There will be a review session on Sunday June 4 at 1:00 p.m. in CSE 403.
Catalog Description
Models of computation, computable and noncomputable functions, space and
time complexity, tractable and intractable functions. Prerequisite: CSE 312.
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: © 19932017, Allen School of Computer Science
and Engineering, University of Washington.
