| Class #
| Date
| Lecture Topic
| Reading
| Assignments
| Resources, and Additional Readings
|
| Week 1 |
| 1 | 1/12 | Course Overview, Preliminaries
| Sipser Sec 0.1, 0.2, 0.3. 0.4 |
| |
| 2 | 1/14 |
Finite Automata
| Sec. 1.1 |
|
|
| Week 2
|
| 3 | 1/19 |
Regular languages and operations
| Sec. 1.1 |
| 4 | 1/21 |
Nondeterministic finite automaton
| Sec. 1.2 |
| Week 3
|
| 5 | 1/26 |
Equivalence of Deterministic and Nondeterministic FA. Closure under the regular operations.
|
Sec 1.2 |
|
|
| 6 | 1/28 |
Regular expressions. Equivalence of regular expressions with Finite
Automata
| Sec 1.3 |
|
|
| Week 4
|
| 7 | 2/2 | Pumping Lemma for regular
languages. Summary
| Sec 1.4 |
|
|
| 8 | 2/4 | Introduction to Context Free Grammars
and Languages
| Sec 2.1 |
|
|
| Week 5
|
| 9 | 2/9 | Context Free Grammars (cont). Chomsky Normal Form and Chomsky Hierarchy
| Sec 2.1 |
|
| 10 | 2/11 | Pumping Lemma for Context-Free languages
| Sec. 2.3 |
|
|
| Week 6
|
| 11 | 2/16 | Pushdown automata. Equivalence
of CFG and PDA
|
Sec 2.2 |
| 12 | 2/18 |
Into to Turing Machines and Examples
| Sec 3.1 |
| Week 7
|
| 13 | 2/23 |
Church Turing Thesis. Multitape Turing Machine | Sec 3.2 |
|
|
| 14 | 2/25 | Nondeterministic Turing Machines, enumerators
| Sec 3.2 |
|
|
| Week 8
|
| 15 | 3/2 |
Decidability and Decidable Problems
for Regular Languages |
Sec 4.1 |
|
|
| 16 | 3/4 | First Midterm
|
|
|
|
| Week 9
|
| 17 | 3/9 | Decidable problems
for Context Free Languages. Universal Turing Machine. Diagonalization
| Sec. 4.2 |
|
|
| 18 | 3/11 |
Method. Languages Not-Turing Recognizable. Halting Problem Undecidability |
Sec. 4.2 |
|
|
| Week 10
|
| 19 | 3/16 |
Reducibility. Undecidable Problems from Language Theory
|
Sec 5.1 |
|
| 20 | 3/18 |
Mapping Reducibility. Post Correspondance Problem.
| Sec. 5.2, Sec 5.3 |
|
|
| Week 11
|
| 21 | 3/23 |
Undecidability of the PCP. Linear Bounded Automata |
Sec 5.2 |
|
| 22 | 3/25 | Mapping Reducibility. Time Complexity, Big-O Notation
| Sec. 7.1 |
|
|
| Week 12
|
| 23 | 3/30 |
Complexity Class P
| Sec. 7.2 |
|
|
| 24 | 4/1 |
Second Midterm
|
7.3 |
|
|
| Week 13
|
| 25 | 4/6 |
Complexity Class NP
| 7.3 |
|
|
| 26 | 4/8
|
NP-Completeness. Cook-Levin Theorem
|
7.4 |
|
|
| Week 14
|
| 27 | 4/13 |
Other NP-complete problems
|
7.5 |
| 28 | 4/15 | Other NP-complete problems
| Sec 7.5 |
|
| Week 15
|
| 29 | 4/21 | Final Exam Week
| |
|
|
| 29 | 4/23 | Final Exam Week
| |
|
|