| Week 1 |
| 03/29 |
Introduction, Review, Languages |
Chapter 0 |
|
| 03/31 |
DFAs and Regular Languages |
Section 1.1, 1.2 |
HW 0 Assigned |
| Week 2 |
| 04/05 |
NFAs. Closure Properties of Regular Languages |
|
|
| 04/07 |
Regular Expressions |
Section 1.3 |
HW 0 Due. HW 1 Assigned |
| Week 3 |
| 04/12 |
Nonregular Languages and the Pumping Lemma |
Section 1.4 |
|
| 04/14 |
Context-Free Languages |
Sections 2.1 and 2.2 |
|
| Week 4 |
| 04/19 |
Closure Properties of CFLs. Chomsky Normal Form |
|
HW 1 Due. HW 2 Assigned |
| 04/21 |
Non-Context-Free Languages |
Section 2.3 |
|
| Week 5 |
| 04/26 |
Midterm Review |
|
|
| 04/28 |
Midterm |
|
HW 2 Due |
| Week 6 |
| 05/03 |
Turing Machines |
Section 3.1 |
|
| 05/05 |
Turing Machine Variants |
Section 3.2 |
|
| Week 7 |
| 05/10 |
Encodings of Other Objects |
Section 3.3, Section 4.1 |
HW 3 Assigned |
| 05/12 |
Undecidable Problems |
Section 4.2 |
|
| Week 8 |
| 05/17 |
Mapping Reductions and Rice's Theorem |
Section 5.1, Section 5.3 |
|
|
|
|
|
| Week 9 |
|
|
|
|
| 05/19 |
Introduction to Complexity Theory. Time Complexity. Asymptotic Notation. |
Sections 7.1-7.3 |
HW 3 Due |
| Week 10 |
| 05/24 |
Complexity Classes |
Section 7.4 |
|
|
|
|
|
| Week 11 |
| 05/31 |
Practice Final Exam |
|
|
| 06/02 |
Final exam review |
|
HW 4 Due |