| Lec. | Date | Topics and lecture notes | Reading | Homework and handouts |
|---|
| 1 | Tu, Aug 25 | Introduction, finite automata (pdf) | Chapters 0-1.1 | General Course Information, HW0 out; play with JFLAP |
| 2 | Tu, Aug 27 | Regular operations, nondeterminism (pdf) | Chapters 1.2-1.3 | HW0 due, HW1 out
|
| 3 | Th, Sep 1 | Equivalence of NFAs and DFAs (pdf) | Chapters 1.1-1.3 |
|
| 4 | Th, Sep 3 | Equivalence of DFAs and regular expressions | Chapter 1.3 | HW1 due, HW2 out
|
| 5 | Tu, Sep 8 | Pumping lemma for regular languages |
Chapter 1.4 |
|
| 6 | Th, Sep 9 | Gontext-free languages, context-free grammars | Chapter 2.1 | HW2 due, HW3 out
|
| 7 | Tu, Sep 15 | Pushdown automata, designing PDAs | Chapter 2.2 |
|
| 8 | Th, Sep 17 | Equivalence of CFGs and PDAs, designing CFGs and PDAs | Chapter 2.2 | HW3 due, HW4 out
|
| 9 | Tu, Sep 22 | Designing CFGs and PDAs. Pumping lemma for CFLs. | Chapter 2.3 |
|
| 10 | Th, Sep 24 | Turing Machines. TM variants. | Chapters 3.1-3.2 | HW4 due; exam practice problems handed out
|
| 11 | Tu, Sep 29 | Enumerators. Church-Turing Thesis. | Chapters 3.2-3.3 | Practice exam solutions handed out
|
| Wed, Sep 30 | Exam 8:15-10:15pm in 112 Walker
| Chapters 0-3.1 |
|
| 12 | Th, Oct 1 | Decidable languages | Chapter 4.1 | HW5 out
|
| 13 | Tu, Oct 6 | Universal TMs. Countable and uncountable sets. Diagonalization. Undecidability. | Chapter 4.2 |
|
| 14 | Th, Oct 8 | Halting problem. A Turing-unrecognizable language. Reductions. | Chapters 4.2, 5.1 | HW5 due, HW6 out
|
| 15 | Tu, Oct 13 | Typical mistakes on exam 1. Reductions. | Chapter 5.1 | Exam 1 solutions handed out.
|
| 16 | Th, Oct 15 | Practicing reductions. Mapping-reducibility. | Chapters 5.1,5.3 | HW6 due, HW7 out
|
| 17 | Tu, Oct 20 | Mapping-reducibility. Turing-unrecognizable languages. | Chapter 5.3. |
|
| 18 | Th, Oct 22 | Mapping-reducibility. Computation history method. | Chapter 5.1. Optional: chapter 5.2 | HW7 due, HW8 out
|
| 19 | Tu, Oct 27 | Computation history method: ALL_CFG is undecidable. Recursion Theorem | Chapter 6.1 |
|
| 20 | Th, Oct 29 | Recursion Theorem | Chapter 6.1 | HW8 due
|
| Fri, Oct 30 | | | Programming Assignment due
|
| 21 | Tu, Nov 3 | Review. Problems from the practice midterm. | |
|
| Wed, Nov 4 | Exam 8:15-10:15pm in in 112 Walker | Chapters 0-5.1, 5.3-6.1 |
|
| 22 | Th, Nov 5 | Measuring complexity. Complexity relationships among models. Class P. | Chapters 7.1, 7.2. Review asymptotic notation | HW9 out
|
| 23 | Tu, Nov 10 | Dynamic programming. Nondeterministic complexity classes. Class NP. | Chapters 7.1-7.3 |
|