CSE 431: Introduction to the Theory of Computation

Fall, 2019

Paul Beame

Mondays, Wednesdays, and Fridays 11:30-12:20 CSE2 G10
Office hours: MW 12:20-12:50 and W 4:00-5:00
Office: CSE 668 Phone 206-543-5114

Email and discussion:
email list: cse431a_au19     [archives]

Please send any e-mail about the course to cse431-staff@cs.

Discussion Board (log in with your UW netid)

Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. It is also acceptable to ask for clarifications about the statement of homework problems, but not about their solutions.

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 is 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 from Sipser's book page for lists of errors and corrections.


Date Topic Materials Reading (Sipser)
Wed, Sept 25 Some History Before Turing Chapter 3
(first part of 3.3)
Fri, Sept 27 Turing Machines Turing & Post Handout
Chapter 3 (Section 3.1)
Mon, Sept 30 TM examples
k-tapes ≡ 1-tape
Chapter 3 (3.1-3.2)
Wed, Oct 2 NTMs, NTM≡TM Chapter 3 (Section 3.2)
Fri, Oct 4 Enumerators
Church-Turing Thesis
Chapter 3 (3.2-3.3)
Mon, Oct 7 Decision problems about machines and grammars Chomsky Normal Form Chapter 4 (4.1)
Chomsky Normal Form
Wed, Oct 9 A_TM is Turing-recognizable
but not decidable
Chapter 4 (4.2)
Fri, Oct 11 More undecidable problems Chapter 5 (5.1)
Mon, Oct 14 Mapping reductions Chapter 5 (5.3)
Wed, Oct 16 Rice's Theorem Rice's Theorem
Fri, Oct 18 More mapping reductions
Linear bounded automata
Chapter 5 (5.3, 5.1)
Mon, Oct 21 Undecidability via computation histories Chapter 5 (5.1)
Wed, Oct 23 Turing reductions
Godel Incompleteness
Chapter 6 (6.3, 6.2 - part)
Fri, Oct 25 CFGs: Pumping Lemma
Simulation by PDAs
Parsing Chapter 2 (2.3, 2.2 - part)
Mon, Oct 28 Time Complexity, P & NP Chapter 7 (7.1)
Wed, Oct 30 P, Every CFL is in P Cocke-Kasami-Younger Algorithm
Colorful example
Chapter 7 (7.2)
Fri, Nov 1 NP, Examples Chapter 7 (7.3)
Mon, Nov 4 MIDTERM exam
Wed, Nov 6 NP with Guess-Verify
Polytime reductions, NP-hardness
Chapter 7 (7.3)
Fri, Nov 8 Examples of Polytime reductions Chapter 7 (7.4)
Wed, Nov 13 CNFSAT reduces to IS
Cook-Levin Theorem
Sections 7.4, 9.3
Fri, Nov 15 CIRCUIT-SAT reduces to 3SAT
More NP-completeness Examples
Slides: NP-complete examples Section 7.5
Mon, Nov 18 NP-completeness of HamPath, HamCycle
Space Complexity
Section 8.1
Wed, Nov 20 Space Complexity
Savitch's Theorem
Sections 8.1-8.3
Fri, Nov 22 Savitch's Theorem
TQBF is PSPACE-complete
Section 8.3
Mon, Nov 25 TQBF is PSPACE-complete
Sections 8.3-8.4
Wed, Nov 27 NL-completeness
NL=coNL Sections 8.4-8.5
Mon, Dec 2
Wed, Dec 4
Fri, Dec 6

TA Office hours Room
Robbie Weber Thursdays 9:30-10:20 Allen Center 4th floor Breakout
Phillip Quinn Mondays 3:30-4:20 Gates Center 152

Reading Assignments:

  • Review Sipser text: Chapter 0
  • Review Sipser text: Chapter 1
  • Turing and Post Handout
  • Read Sipser text: Chapter 3
  • Read Sipser text: Chapter 4
  • Read Sipser text: Chapter 5
  • Read Sipser text: Chapter 7
  • Read Sipser text: Section 9.3
  • Read Sipser text: Chapter 8
  • Read Sipser text: Chapter 9.1


Before starting on homework, please review our homework policy Submission is online via Canvas. Extra credit problem solutions need to be uploaded separately from the regular problems.


  • Midterm exam:
    Monday, November 4 in class. Closed book and closed notes. It will cover the material we have discussed from Chapters 3-5 of Sipser's text.
    Here is a sample midterm.
    Solutions to sample midterm.
    There will a review session on Sunday November 3rd, at 4:15 pm in ECE 037 (formerly EEB 037).

  • Final exam:
    The final exam will be in our regular classroom at the time listed in the official exam schedule which is 2:30-4:20 pm, Wednesday December 11. The final exam will be closed book and closed notes; its coverage will be comprehensive. Here is an old final exam from a prior quarter. There will be a review session on Monday, Dec 9 5:30-7:00 pm in room CSE 305. Please bring your questions! Here are some solutions to the sample final.

Grading Scheme:

Homework 45-55% + Extra Credit
Midterm 15-20%
Final Exam 30-35%
Further reading
Please refer to university policies regarding disability accommodations or religious accommodations.
Catalog Description
Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 312.