The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 431: Introduction to Theory of Computation, Spring 2015
  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 Solutions
Reading Assignments
  More NP-completeness examples
  Read Section 9.3 and Sections 7.4-7.5
  Read Sections 7.1-7.3
  Cocke, Kasami, Younger 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
  Homework Policy
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 2:30-3:20    Johnson 026


  • Paul Beame
  • Office: CSE 668 Phone 206-543-5114
  • Office Hours: MWF 3:20-4 and by arrangement.

Teaching Assistant

  • Xin Yang
  • Office Hours: Tuesdays 2:30-3:30, CSE 220. Thursdays 2:00-3:00, CSE 220.


    Michael Sipser, Introduction to the Theory of Computation. Any of the first, international, second or third editions will work. Earlier editions are less than half 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 context-free languages that we won't cover anyway. See errata links on book page for lists of errors and corrections.

Mailing List

Course annoucements will be made on the class mailing list, cse431a_sp15.


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

Midterm Exam

Friday May 8 in class. Here is a sample midterm. There will be a review session Thursday May 7 at 5:30 pm in CSE 403.

Final Exam

The final exam will be at the time listed in the official exam schedule which is 2:30-4:20 pm, Tuesday June 9. Here is a sample old final. There will be a review session Monday, June 8 at 4:30 pm in room 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: © 1993-2015, Department of Computer Science and Engineering, University of Washington.