| Lec. | Date | Topics | Reading | Homework and handouts |
|---|
| 1 | Tu, Aug 26 | Introduction, finite automata | Chapters 0-1.1 | General Course Information, post a RECOGNIZABLE photo of your face on Angel |
| 2 | Th, Aug 28 | Formal definition of finite automata, regular operations, regular expressions, closure under union | Chapters 1.1-1.3 | HW 1 out; optional: play with JFLAP
|
| 3 | Tu, Sep 2 | Nondeterminism, closure properties | Chapters 1.2-1.3 |
|
| 4 | Th, Sep 4 | Equivalence of DFAs and regular expresssions, pumping lemma for regular languages | Chapters 1.3-1.4 | HW1 due, HW 2 out
|
| 5 | Tu, Sep 9 | Context-free languages, context-free grammars | Chapter 2.1 |
|
| 6 | Th, Sep 11 | Pushdown automata, equivalence of CFGs and PDAs | Chapter 2.2 | HW2 due, HW 3 out
|
| 7 | Tu, Sep 16 | Designing PDAs. Pumping lemma for CFLs | Chapters 2.2-2.3 |
|
| 8 | Th, Sep 18 | Turing Machines. TM variants. | Chapters 3.1-3.2 | HW3 due, HW 4 out
|
| 9 | Tu, Sep 23 | Enumerators. Church-Turing Thesis. | Chapters 3.2-3.3 |
|
| 10 | Th, Sep 25 | Decidable languages. Review. | Chapter 4.1 | HW4 due; exam practice problems handed out
|
| 11 | Tu, Sep 30 | Finish decidable languages. Review. | Chapter 4.1 | Practice exam 1 solutions handed out
|
| Wed, Oct 1 | Exam 8:15-10:15pm in 260 Willard | Chapters 0-4.1 |
|
| 12 | Th, Oct 2 | Universal TMs. Countable and uncountable sets. Diagonalization. Undecidability. | Chapter 4.2 | HW 5 out
|
| 12 | Tu, Oct 7 | Halting problem. A Turing-unrecognizable language. Reductions. | Chapters 4.2, 5.1 |
|
| 13 | Th, Oct 9 | Typical mistakes on exam 1. Reductions. | Chapter 5.1 | Exam 1 solutions handed out. HW5 due, HW 6 out
|
| 14 | Tu, Oct 14 | Practicing reductions. Reductions via computation histories. | Chapter 5.1 |
|
| 15 | Th, Oct 16 | Computation history method: ALL_CFG is undecidable. Mapping-reducibility. | Chapters 5.1,5.3. Optional: chapter 5.2 | HW6 due, HW 7 out
|
| 16 | Tu, Oct 21 | Mapping-reducibility. Turing-unrecognizable languages. | Chapter 5.3 |
|
| 17 | Th, Oct 23 | Recursion Theorem | Chapter 6.1 | HW7 due, HW 8 out
|
| 18 | Tu, Oct 28 | Asymptotic notation; measuring complexity | Chapter 7.1 |
|
| 19 | Th, Oct 30 | Complexity relationships among models. Class P. Review | Chapter 7.2 | HW8 due
|
| 20 | Tu, Nov 4 | Class NP. Review | Chapter 7.3 |
|
| Wed, Nov 5 | Exam 8:15-10:15pm in 260 Willard | Chapters 0-5.1, 5.3-6.1, 7.1-7.2 |
|