Mondays, Wednesdays, and Fridays 11:3012:20 CSE2 G10
Office hours: MW 12:2012:50 and W 4:005:00
Office: CSE 668 Phone 2065435114
Please send any email about the course to cse431staff@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.
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 contextfree 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 ktapes ≡ 1tape 
Chapter 3 (3.13.2)  
Wed, Oct 2  NTMs, NTM≡TM  Chapter 3 (Section 3.2)  
Fri, Oct 4  Enumerators ChurchTuring Thesis 
Chapter 3 (3.23.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 Turingrecognizable 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  CockeKasamiYounger 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 GuessVerify Polytime reductions, NPhardness 
Chapter 7 (7.3)  
Fri, Nov 8  Examples of Polytime reductions  Chapter 7 (7.4)  
Wed, Nov 13  CNFSAT reduces to IS CookLevin Theorem 
Sections 7.4, 9.3  
Fri, Nov 15  CIRCUITSAT reduces to 3SAT More NPcompleteness Examples 
Slides: NPcomplete examples  Section 7.5 
Mon, Nov 18  NPcompleteness of HamPath, HamCycle Space Complexity 
Section 8.1  
Wed, Nov 20  Space Complexity Savitch's Theorem 
Sections 8.18.3  
Fri, Nov 22  Savitch's Theorem TQBF is PSPACEcomplete 
Section 8.3  
Mon, Nov 25  TQBF is PSPACEcomplete L,NL 
Sections 8.38.4  
Wed, Nov 27  NLcompleteness NL=coNL 
NL=coNL  Sections 8.48.5 
Mon, Dec 2  
Wed, Dec 4  
Fri, Dec 6 
TA  Office hours  Room 
Robbie Weber  Thursdays 9:3010:20  Allen Center 4th floor Breakout 
Phillip Quinn  Mondays 3:304:20  Gates Center 152 
Reading Assignments:
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.
Exams:
Grading Scheme:
Homework  4555% + Extra Credit 
Midterm  1520% 
Final Exam  3035% 