| Week | Topics covered | Notes from Class, and Announcements | Material, Homework, Assignments | |
|---|---|---|---|---|
| Week 1: Jan 7-9 | Course Administrivia; What is a computer; brief overview of the course | |||
| Week 2: Jan 14-16 | Finite Automata: DFAs and NFAs. Regular operations on languages | |||
| Week 3: Jan 21-23 | Closure of RL under ⋅, ∪, *. Introducing regular expressions. | |||
| Week 4: Jan 28-30 | Pumping Lemma to prove that a language is not regular. Using closure theorems to help prove a language is not regular. | |||
| Week 5: Feb6 (Snowday Feb 4) | Introduction to Context Free Languages: Context-free Grammars. Ambiguous grammars. | |||
| Week 6: Feb 11-13 |
CFG: Proving that a given grammar generates a particular language.
Intro to PDAs |
|||
| Week 7: Feb 18-20 | Study Days | |||
| Week 8: Feb 25-27 |
Tue: Proving a language is not Context-Free Thu: Midterm 1 |
|||
| Week 9: Mar 4-6 | Countably infinite sets; Uncountability. Intro to Turing Machines | |||
| Week 10: Mar 11-13 | Turing Machines, cont'd. | |||
| Week 11: Mar 18-20 | TMs: non-determinism, Universal TM, Enumerator TM, Simulating a real computer. | |||
| Week 12: Mar 25-27 | Tue: Proving languages are undecidable or unrecognizable||||
| Week 13: Apr 1-3 |
Tue: April 1 Complexity cont'd. |
|||
| Week 14: Apr 8-10 |
|
|||
| Exam Week: Apr 14-18 | ||||