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.
Textbook:
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.
Lectures
| Date | Topic | Materials | Reading (Sipser) |
| Mon, Jan 3 | Introduction. Prehistory of computing |
Notes 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 Diagonalization |
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) |
| Wed, Jan 26 | EQ_TM,REGULAR_TM Rice's Theorem |
Notes 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 |
Notes Parsing Chomsky Conversion |
Chapter 2 (2.1, 2.2 - part) |
| Fri, Feb 4 | Pumping Lemma for CFLs Time Complexity, P & NP |
Notes | 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 |
Notes Slides: NP-complete examples |
Section 7.5 |
| Wed, Feb 23 | More NP-completeness Space Complexity |
Notes | Section 8.1 |
| Fri, Feb 25 | Savitch's Theorem PSPACE-completeness |
Notes | 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 NL=coNL |
Notes NL=coNL |
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 |
Homework:
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.
- Homework 1 (Due: Thursday, January 13, 11:59 pm.)
- Homework 2 (Due: Thursday, January 20, 11:59 pm.)
- Homework 3 (Due: Thursday, January 27, 11:59 pm.)
- Homework 4 (Due: Thursday, February 3, 11:59 pm.)
- Homework 5 (Due: Thursday, February 17, 11:59 pm.)
- Homework 6 (Due: Thursday, February 24, 11:59 pm.)
- Homework 7 (Due: Thursday, March 3, 11:59 pm.)
- Homework 8 (Due: Thursday, March 10, 11:59 pm.)
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
- Hilbert's 23 Problems (See, especially, problems 2 and 10.)
- David Hilbert Bio
- Kurt Gödel Bio
- Alonzo Church Bio
- Alan Turing Bio
- Extensive material on advanced topics in computational complexity is available in Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. A page containing a draft of the book is available here: