The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 431: Introduction to Theory of Computation, Spring 2012
  CSE Home   CSE 431 Home  About Us    Search    Contact Info 

Homework Assignments
  Homework 1
  Homework 2
  Homework 3
  Homework 4
  Homework 5
  Homework 6
  Homework 7
  Homework 8
  Homework 8 Sols
Reading Assignments
  NP-Completeness Examples
  Read Chapter 8
  Read Sections 9.3 and 7.4-7.5
  Read Sections 7.1-7.3
  CKY Algorithm
  Chomsky Normal Form
  Read Chapter 5
  Read Chapter 4
  Read Chapter 3
  Turing and Post Handout
  Slides on NFAs
  Read Chapter 1
  Review Chapter 0
  Background Survey
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


Mondays, Wednesdays, and Fridays 1:30-2:20    EEB 045


  • Paul Beame
  • Office: CSE 668 Phone 206-543-5114
  • Office Hours: Mondays 2:30-3:00, Wednesdays 2:30-3:00, and TBA

Teaching Assistants

  • Steven Rutherford: Office hour: Thursdays 12:00-1:00 CSE 216
  • Dan Gnanapragasam: Office hour: Thursdays 2:00-3:00 CSE 216


    Michael Sipser, Introduction to the Theory of Computation. Either the first or second editions will work, and the first edition is less than half the cost of the second edition online. 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. Th

Background Survey

With the transition between new and old curricula at the 300-level it is possible that different students will have slightly different background for the material in this course. Please take the survey linked at the left of this page so I can better understand your background.

Mailing List

There is a class mailing list, cse431.


Homework 45-55%, midterm 15-20%, final 30-35%, give or take. Extra Credit. See the homework policy

Midterm Exam

Friday May 4 in class. Here is a sample midterm. There will be a review session Thursday May 3 at 4:30 pm in CSE 203.

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 4. Here is sample old final.

Catalog Description

Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 312 or 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-2012, Department of Computer Science and Engineering, University of Washington.