Chapter pointers refer to the course textbook, M. Sipser, Introduction to the Theory of Computation. For additional reading material, homework assignments, etc., see course webpage. Reading assignments for future lectures are tentative, and they are provided in case you want to read ahead. Links to lecture notes that have not been covered yet may be broken, or point to older versions of the notes that require editing. Lecture notes will be updated as we move on with the course.
| Date | Topic | Reading/Notes |
|---|---|---|
| Mon, Jan 5 | Introduction | Ch. 0, running haskell |
| Wed, Jan 7 | DFAs | Ch. 1.1, notes on DFA/NFA |
| Fri, Jan 9 | Computations | Ch. 1.1, DFAs in haskell |
| Mon, Jan 12 | Closure properties | Ch. 1.2 NFAs in haskell |
| Wed, Jan 14 | NFAs | Ch. 1.2 |
| Fri, Jan 16 | Regular Operations | Ch. 1.3 |
| Mon, Jan 19 | MLK Day: No class | |
| Wed, Jan 21 | Regular Expressions | Ch. 1.3 |
| Fri, Jan 23 | Non Regular Languages | Ch. 1.4, notes on Diagonalization |
| Mon, Jan 26 | Midterm 1 (in class) | |
| Wed, Jan 28 | Pumping Lemma | Ch. 1.4 (Finish chapter 1) |
| Fri, Jan 30 | Finite State Transducers | notes on FST |
| Mon, Feb 2 | More on FSTs | notes on NFST |
| Wed, Feb 4 | Context Free Grammars | Ch. 2.1 |
| Fri, Feb 6 | Context Free Grammars | Ch. 2.1 |
| Mon, Feb 9 | Push Down Automata | Ch. 2.2 |
| Wed, Feb 11 | Push Down Automata | |
| Fri, Feb 13 | Non Context Free Languages | Ch. 2.3 |
| Mon, Feb 16 | Presidents' Day: No class | |
| Wed, Feb 18 | Non Context Free Languages | Ch. 2.3 |
| Fri, Feb 20 | Midterm 2 (in class) | |
| Mon, Feb 23 | Turing Machines | Ch. 3.1 |
| Wed, Feb 25 | Variants of Turing Machins | Ch. 3.2 |
| Fri, Feb 27 | Church Turing Thesis | Ch. 3.3 |
| Mon, Mar 2 | Undecidability | Ch. 4.2 |
| Wed, Mar 4 | Decidable Languages | Ch. 4.1 |
| Fri, Mar 6 | Mapping Reducibility | Ch. 5.3 |
| Mon, Mar 9 | Undecidable Problems | Ch. 5.1 |
| Wed, Mar 11 | More undecidable Problems | 5.2 |
| Fri, Mar 13 | Wrap Up | Ch 1-5 |
| Fri, Mar 20 | Final Exam (8:00a-10:50a) |