CSE 431: Introduction to the Theory of Computation

Winter, 2022

Paul Beame

Lectures MWF 11:30-12:20. For the first week of the term, as with almost all UW courses, this course will be online: Zoom link.
We have a new classroom starting January 10: MGH 058. The lectures will be in person on the whiteboard but will also be recorded and live over Zoom for those who prefer to be remote at this time.
Office hours: MW 12:20-12:50 and W 3:00-3:50
Office: CSE 668, Phone 206-543-5114, or on Zoom

Email list:
email list: cse431a_wi22     [archives]

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

Discussion board:
We will use the Ed discussion board for this class. You will need to sign up by accepting the invitation that we send. Use this board to discuss the content of the course. That includes everything except the solutions to current homework or anything about current exams. Feel free to discuss any confusion over topics discussed in class. It is also acceptable to ask for clarifications about the statement of current 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.

If you are sick or have potentially been exposed to COVID-19, stay home. You will not be penalized for missing class while trying to keep our community safe. See more here.

Review Reading:

  • Review Sipser text: Chapter 0
  • Review Sipser text: Chapter 1
  • If you did not take CSE 311 and have not seen finite state machines, you should skim Chapter 1 of Sipser's text to get a sense of the material covered there.


Date Topic Materials Reading (Sipser)
Mon, Jan 3 Introduction.
Prehistory of computing
Infinity & Computation
Chapter 3 (first part 3.3)
Wed, Jan 5 Turing Machines Notes
Turing & Post Handout
Chapter 3 (3.1)
Fri, Jan 7 Turing Machines and Examples Notes Chapter 3 (3.1)
Mon, Jan 10 Detailed TM example
k-tapes ≡ 1-tape
Notes Chapter 3 (3.1-3.2)
Wed, Jan 12 NTMs, NTM≡TM, Enumerators≡Recognizers Notes Chapter 3 (3.2)
Fri, Jan 14 Church-Turing Thesis
Decidable problems about machines
Notes Chapter 3 (3.3)
Chapter 4 (4.1)
Wed, Jan 19 Decision problems about grammars
A_TM, Universal TM
Notes Chapter 4 (4.1-4.2)
Fri, Jan 20 Undecidability of A_TM
Undecidability of other problems
Notes Chapter 4 (4.2)
Chapter 5 (5.1)
Mon, Jan 24 Mapping reductions Notes Chapter 5 (5.3)
Rice's Theorem
Rice's Theorem (Alternate Proof)
Chapter 5 (5.3,5.1)
Fri, Jan 28 Undecidability via computation histories Notes
Chapter 5 (5.1)
Mon, Jan 31 Godel Incompleteness
Turing reductions
Notes Chapter 6 (6.2 part, 6.3)
Wed, Feb 2 CFGs: Simulation by PDAs
Chomsky Normal Form
Chomsky Conversion
Chapter 2 (2.1, 2.2 - part)
Fri, Feb 4 Pumping Lemma for CFLs
Time Complexity, P & NP
Chapter 2 (2.3)
Chapter 7 (7.1-2)
Mon, Feb 7 P, Every CFL is in P Notes
CKY Algorithm
Chapter 7 (7.2)
Wed, Feb 9 NP & Verifiers, Examples
Polynomial-time reductions
Notes Chapter 7 (7.3, part 7.4)
Mon, Feb 14 NP-hardness, NP-completeness
Statement of Cook-Levin Theorem
Boolean Circuits
Notes Chapter 7 (part 7.4)
Chapter 9 (9.3)
Wed, Feb 16 Cook-Levin Theorem proof
CIRCUIT-SAT reduces to 3SAT
Notes Sections 7.4, 9.3
Fri, Feb 18
Other NP-completeness Proofs
Slides: NP-complete examples
Section 7.5
Wed, Feb 23 More NP-completeness
Space Complexity
Section 8.1
Fri, Feb 25 Savitch's Theorem
Sections 8.1-8.3
Mon, Feb 28 TQBF is PSPACE-complete Notes
Section 8.3
Wed, Mar 2 PH, L, NL, PATH is NL-complete Notes
Section 8.3
Fri, Mar 4 Composition of logspace reductions
Sections 8.4-8.5
Mon, Mar 7 Time and Space Hierarchy Theorems Notes
Section 9.1-9.2

TA Office hours Room
Michael Whitmeyer T 3:00-3:50
Th 9:00-9:50
CSE 220    Zoom
CSE 218   Zoom


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

Exams: Assuming that classes will be in person later in the term, we will have in-person exams.

  • Midterm exam:
    Friday, February 11 in class. Closed book and closed notes. It will cover the material we have discussed through last Friday, Jan 28 (which does not include the material from Chapter 6 of Sipser's text) as well as everything covered on (non-extra credit) homework so far. There will be a review session on Zoom on Wednesday Feb 9 starting at 4:30 p.m. Please bring your questions to ask. Here is a sample midterm from a prior year and a set of solutions.
  • 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 March 16. 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 Zoom on Sunday March 13 starting at 4:00 pm (remember that we switch an hour ahead to daylight savings time on Sunday morning). Please bring your questions! There are solutions to some of the old final exam questions.

Grading Scheme:
The grading scheme below is subject to change depending on our ability to have in-person exams this term.

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.