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

  Sign-up Instructions
Homework Assignments
  Assignment 1
  Assignment 2
  Assignment 3
  Assignment 4
  Assignment 5
  Assignment 6
  Assignment 7
  Assignment 8
Reading Assignments
  Chapter 8
  Section 9.3
  Chapter 7
  Chapter 5, 6.3
  Sections 5.1,5.3
  Chapter 4
  Chapter 3
  Turing and Post Handout
  Review Chapters 0-2
  Sample Midterm
  Sample Final
Interesting Links
  Turing's full paper
  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 9:30-10:20    Loew 216


  • Paul Beame
  • Office: CSE 668 Phone 206-543-5114
  • Office Hours: Mondays and Wednesdays 10:20-10:50. Wednesdays 3:00-3:50.

Teaching Assistants

  • Widad Machmouchi
  • Office Hours: Thursdays 12:00-1:00 CSE 220 and 2:30-3:20 CSE 216


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.


Homework 45-55%, midterm 15-20%, final 30-35%, 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:30-10: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: © 1993-2009, Department of Computer Science and Engineering, University of Washington.