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.
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.
Lectures
| 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 L,NL |
Sections 8.3-8.4 | |
| Wed, Nov 27 | NL-completeness NL=coNL |
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
Homework:
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.
- Homework 1 (Due: Saturday, October 5, 5:59 pm.)
- Homework 2 (Due: Thursday, October 10, 11:59 pm.)
- Homework 3 (Due: Thursday, October 17, 11:59 pm.)
- Homework 4 (Due: Monday, October 28, 8:59 pm.)
- Homework 5 (Due: Tuesday, November 12, 8:59 pm.)
- Homework 6 (Due: Monday, November 18, 8:59 pm.)
- Homework 7 (Due: Tuesday, November 26, 4:59 pm.)
- Homework 8 (Due: Thursday, December 5, 11:59 pm.)
Exams:
- 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
- Hilbert's 23 Problems (See, especially, problems 2 and 10.)
- David Hilbert Bio
- Kurt Gödel Bio
- Alonzo Church Bio
- Alan Turing Bio