This is a tentative outline of lecture topics and assignment dates for the semester. The dates and topics on this syllabus (especially for the second half of the course) are subject to change, depending on how quickly we cover the material.
Readings are from from Sipser's Introduction to the Theory of Computation, 3rd Ed.
Date | Lecture Topic | Readings | Homework Due | Homework Assigned |
---|---|---|---|---|
Wed Jan 18 |
Intro; Strings and Languages | Sec 0.2 | Homework 0 (optional) | |
Mon Jan 23 |
Deterministic Finite Automata | Sec 1.1 | ||
Wed Jan 25 |
Nondeterministic Finite Automata | Sec 1.2 | Homework 0 (optional) | Homework 1 |
Mon Jan 30 |
NFA-DFA Equivalence | Sec 1.2 | ||
Wed Feb 1 |
NFAs with Null Transitions | Sec 1.2 | ||
Mon Feb 6 |
Regular Expressions; Kleene's Theorem | Sec 1.3 | ||
Wed Feb 8 |
Finish Kleene's Theorem; Closure Properties of RLs | Sec 1.2, 1.3 | ||
Mon Feb 13 |
Proving Languages Non-Regular; Pumping Lemma | Sec 1.4 | Homework 1 | Homework 2 |
Wed Feb 15 |
Non-Uniqueness of DFAs; Myhill-Nerode Thm | |||
Mon Feb 20 |
DFA Minimization | |||
Wed Feb 22 |
Finish Up RLs | |||
Mon Feb 27 |
Introduction to Turing Machines | Sec 3.1 | ||
Wed Mar 1 |
Simulating Extensions to TMs | Sec 3.2 | Homework 2 | |
Mon Mar 6 |
Exam 1 | |||
Wed Mar 8 |
RE and Recursive Languages | Sec 4.1, 4.2 | ||
Mar 13-17 | Spring Break | |||
Mon Mar 20 |
Universal TMs and Existence of non-RE Languages | Sec 4.2 | Homework 3 | |
Wed Mar 22 |
Undecidable Problems on TMs | Sec 5.1 | ||
Mon Mar 27 |
Proving a Language Nonrecursive: Reduction Arguments | Sec 5.1 | ||
Wed Mar 29 |
The Post Correspondence Problem | Sec 5.2 | ||
Mon Apr 3 |
Time Complexity of TMs | Sec 7.1 | ||
Wed Apr 5 |
The Classes P and NP | Sec 7.2, 7.3 | Homework 3 | Homework 4 |
Mon Apr 10 |
instructor out -- no class | |||
Wed Apr 12 |
NP-Completeness: Cook's Theorem | Sec 7.4 | ||
Mon Apr 17 |
NP-Completeness: Reductions | Sec 7.4, 7.5 | ||
Wed Apr 19 |
Space Complexity | Sec 8.1 | ||
Mon Apr 24 |
The Class PSPACE | Sec 8.2 | Homework 4 | |
Wed Apr 26 |
PSPACE-Completeness | Sec 8.3 | ||
Fri May 5 6-8 PM |
Exam 2 |