| Lecture | Date | Section/Pages | Topic | ||
|---|---|---|---|---|---|
| Introduction to the Theory of Computation | |||||
| 1 | Wed, Aug 24 | Introduction | |||
| 2 | Fri, Aug 26 | 1.1 | Mathematical Preliminaries | ||
| 3 | Mon, Aug 29 | 1.2 | Languages and Grammars | ||
| Finite Automata | |||||
| 4 | Wed, Aug 31 | 2.1 | Deterministic Finite Automata | ||
| 5 | Fri, Sep 2 | 2.1 | DFA Examples | ||
| 6 | Mon, Sep 5 | 2.2 | Nondeterministic Finite Automata | ||
| 7 | Wed, Sep 7 | 2.3 | Converting NFAs to DFAs | ||
| 8 | Fri, Sep 9 | 2.3 | NFAs to DFAs Examples | ||
| 9 | Mon, Sep 12 | 2.4 | Minimizing DFAs | ||
| Regular Languages and Regular Grammars | |||||
| 10 | Wed, Sep 14 | 3.1 | Regular Expressions | ||
| 11 | Fri, Sep 16 | 3.2 | Regular Expressions and DFAs | ||
| 12 | Mon, Sep 19 | 3.3 | Regular Grammars | ||
| Properties of Regular Languages | |||||
| 13 | Wed, Sep 21 | 4.1 | Closure Properties of Regular Languages | ||
| Fri, Sep 23 | Test 1 | ||||
| 14 | Mon, Sep 26 | 4.2 | Decision Problems for Regular Languages | ||
| 15 | Wed, Sep 28 | 4.3 | Nonregular Languages | ||
| Context-Free Languages | |||||
| 16 | Fri, Sep 30 | 5.1 - 5.2 | Context-Free Grammars | ||
| Simplification of Grammars and Normal Forms | |||||
| 17 | Mon, Oct 3 | 6.1 | Transforming Grammars | ||
| 18 | Wed, Oct 5 | 6.2 | Chomsky Normal Form | ||
| 19 | Fri, Oct 7 | 6.3 | The CYK Parsing Algorithm | ||
| 20 | Mon, Oct 10 | ||||
| Pushdown Automata | |||||
| 21 | Wed, Oct 12 | 7.1 | Pushdown Automata | ||
| 22 | Fri, Oct 14 | 7.2 | Equivalence of CFGs and PDAs (Part 1) | ||
| Mon, Oct 17 | Fall Break | ||||
| 23 | Wed, Oct 19 | 7.2 | Equivalence of CFGs and PDAs (Part 2) | ||
| Fri, Oct 21 | Test 2 | ||||
| Properties of Context-Free Languages | |||||
| 24 | Mon, Oct 24 | 8.1 - 8.2 | Properties of Context-Free Languages | ||
| Turing Machines | |||||
| 25 | Wed, Oct 26 | 9.1 | Turing Machines | ||
| 26 | Fri, Oct 28 | 9.2 | Turing Machines Examples | ||
| 27 | Mon, Oct 31 | 9.2 | More Turing Machine Examples | ||
| Other Models of Turing Machines | |||||
| 28 | Wed, Nov 2 | 10.1 - 10.2 | Enhanced Turing Machines | ||
| 29 | Fri, Nov 4 | 10.2 | Nondeterministic Turing Machines | ||
| 30 | Mon, Nov 7 | 10.3 | Universal Turing Machines | ||
| A Hierarchy of Formal Languages | |||||
| 31 | Wed, Nov 9 | 11.1 | Recursive Languages | ||
| 32 | Fri, Nov 11 | 11.1 | Enumerability | ||
| Limits of Algorithmic Computation | |||||
| 33 | Mon, Nov 14 | 12.1 | The Halting Problem | ||
| 34 | Wed, Nov 16 | 12.2 | Decidability | ||
| Fri, Nov 18 | Test 3 | ||||
| An Overview of Computational Complexity | |||||
| 35 | Mon, Nov 21 | 14.1 - 14.2 | Complexity | ||
| Wed, Nov 23 | Thanksgiving Break | ||||
| Fri, Nov 25 | Thanksgiving Break | ||||
| 36 | Mon, Nov 28 | 14.3 - 14.5 | The Classes P and NP | ||
| 37 | Wed, Nov 30 | 14.5 | Nondeterministic Programming in C | ||
| 38 | Fri, Dec 2 | 14.6 | Polynomial-Time Reductions | ||
| 39 | Mon, Dec 5 | 14.7 | NP-Completeness | ||
| Fri, Dec 9 | Final Exam (2:00 - 5:00) | ||||