This syllabus has been superseded. Please use the current syllabus.
This syllabus has been updated to show the campus closures due to the record snow storms in February 6 – 10. The original syllabus is still available here.
| Date | Topic | Quizzes | Reading | Homework | |
|---|---|---|---|---|---|
| Assign | Due | ||||
| Thu 01/28 | Introduction | 0.1–0.4 | |||
| Tue 02/02 | Deterministic Finite Automata (DFA) | 1.1 | HW1 | ||
| Thu 02/04 | Nondeterministic Finite Automata (NFA) | 1.2 | |||
| Tue 02/09 | Campus Closed (snow) | ||||
| Thu 02/11 | Campus Closed (snow) | ||||
| Tue 02/16 | Equivalence of DFAs & NFAs | HW2 | HW1 | ||
| Thu 02/18 | Regular Expressions | 1.3 | |||
| Tue 02/23 | Equivalence of Regular Expressions | HW3 | HW2 | ||
| Thu 02/25 | Regular Language Pumping Lemma | Quiz 1 | 1.4 | ||
| Tue 03/02 | Context-free Grammars (CFG) | 2.1 | HW4 | HW3 | |
| Thu 03/04 | Context-free Grammars (CFG) | ||||
| Tue 03/09 | Chomsky Normal Form | HW5 | HW4 | ||
| Thu 03/11 | Pushdown Automata (PDA) | Quiz 2 | 2.2 | ||
| Tue 03/16 | Spring Break | ||||
| Thu 03/18 | Spring Break | ||||
| Tue 03/23 | PDAs for CFGs | HW6 | HW5 | ||
| Thu 03/25 | CFGs for PDAs | ||||
| Tue 03/30 | Context-Free Pumping Lemma | 2.3 | HW7 | HW6 | |
| Thu 04/01 | Turing Machines | Quiz 3 | 3.1 | ||
| Tue 04/06 | Turing Machines | 3.2 | HW8 | HW7 | |
| Thu 04/08 | Regular Language Decision Properties | 4.1 | |||
| Tue 04/13 | Context-free Decision Properties | HW9 | HW8 | ||
| Thu 04/15 | The Halting Problem | Quiz 4 | 4.2 | ||
| Tue 04/20 | Undecidability | 5.1 | HW10 | HW9 | |
| Thu 04/22 | Undecidability | 5.2 | |||
| Tue 04/27 | Reductions | 5.3 | HW11 | HW10 | |
| Thu 04/29 | P vs NP | Quiz 5 | 7.1–7.3 | ||
| Tue 05/04 | NP-completeness | 7.4 | HW12 | HW11 | |
| Thu 05/06 | NP-completeness | 7.5 | |||
| Tue 05/11 | Advanced Topic TBA | HW12 | |||
| Thu 05/13 | Advanced Topic TBA | ||||
| Tue 05/18 | Final Exam 10:30am – 12:30pm | ||||
to Spring 2010 CMSC 451h Homepage