| Date | Topics (A=1-2:30pm, B=2:40-4:10pm) | Reading | Due | |||
|---|---|---|---|---|---|---|
| Mon | 07/09 | A. Introduction, Proofs | 1.1-1.7 | |||
| B. Strings, Languages, DFAs | 2.1-2.2 | |||||
| Wed | 07/11 | A. DFA-NFA Equivalence | 2.3-2.5 | |||
| B. Regular Expressions | 3.1-3.4 | |||||
| Mon | 07/16 | A. Pumping Lemma for Regular Languages | 4.1-4.2 | HW1 | ||
| B. Properties of Regular Languages | 4.3-4.4 | |||||
| Wed | 07/18 | A. Context-Free Grammars, Parse Trees | 5.1-5.4 | |||
| B. Pushdown Automata | 6.1-6.2 | |||||
| Mon | 07/23 | A. PDA-CFG Equivalence | 6.3 | HW2 | ||
| B. Deterministic PDAs | 6.4 | |||||
| Wed | 07/25 | A. Review | ||||
| B. Exam 1 | ||||||
| Mon | 07/30 | A. Normal Forms for CFG | 7.1 | HW3 | ||
| B. Pumping Lemma for CFL | 7.2 | |||||
| Wed | 08/01 | A. Properties of CFL | 7.3-7.4 | |||
| B. Turing Machines | 8.1-8.3 | |||||
| Mon | 08/06 | A. More Turing Machines | 8.4-8.6 | HW4 | ||
| B. Undecidability | 9.1-9.2 | |||||
| Wed | 08/08 | A. Reductions, Rice's Theorem | 9.3 | |||
| B. More Undecidable Problems | 9.4-9.5 | |||||
| Mon | 08/13 | A. P vs NP | 10.1 | HW5 | ||
| B. Cook's Theorem | 10.2 | |||||
| Wed | 08/15 | A. Review | ||||
| B. Exam 2 |
Back up to Summer 2001 CMSC 451 Homepage