The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 322: Introduction to Formal Models in Computer Science, Autumn 2009
  CSE Home   CSE 322 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 
  Assignment #8 Solution 
Reading Assignments
  Read Sections 3.3,4.2
  Turing and Post Handout 
  Read Section 3.1
  Read Section 2.3
  CKY Example 
  CKY Algorithm 
  Bottom-Up Parsing 
  Read Section 2.2
  Chomsky Normal Form Example 
  Chomsky Normal Form Conversion 
  Read Section 2.1
  Minimizing DFAs 
  Myhill-Nerode Theorem 
  Read Section 1.4
  Pattern Matching Using DFAs 
  NFA to Regular Expressions 
  Read Section 1.3
  Proof of Subset Construction 
  Read Section 1.2
  δ* Properties  
  Read Section 1.1
  Tape Recorder Example 
  Review Chapter 0
  Homework Policy
  Final Exam Time Change
  Catalyst Gradebook
  Midterm Topics
  Final Exam Topics
MWF 9:30-10:20    EEB 037

Office Hours Location Phone
Instructor: Paul Beame   beame at cs   MW 10:20-10:50, W 3:30-4:20 and by appointment CSE 668 543-5114
TAs: Widad Machmouchi    widad at cs   T 2:30-3:20, Th 2:30-3:20 CSE 218
Stillman Knox   stillk at cs   Th 10:30-11:20 CSE 218


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 new and solved problems. The international edition content is also OK though the problem numbers may differ from both U.S. editions. (Second edition errata: first printing. First edition errata: first printing , later printings .)

Mailing List

There is a class mailing list, cse322. Follow the link in the left column on this page to sign up. Everyone is expected to be reading cse322 e-mail to keep up-to-date on the course.


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

Midterm Exam

Friday, November 6 in class. The midterm, which will be closed book and closed notes, will cover up to end of the material on Finite Automata and Regular Languages, except for the part on minimizing DFAs. There is List of Midterm Topics. Here is a sample midterm from a previous offering I gave. Here is another sample midterm. There will be a review session Thursday, November 5 at 3:30 in EEB 125.

Final Exam:

The final exam will NOT be at the time listed in the official exam schedule. It will be Monday December 14 at 12:30-2:20.

There is a list of final exam topics as well as a sample final exam. There will be a review session Sunday December 13 at 3:00 p.m. in our regular classroom.

Suggestions or Comments? You can send comments to the instructor or TA using this anonymous feedback form

Portions of the CSE 322 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 322 Web: © 1993-2009, Department of Computer Science and Engineering, University of Washington.