| Date |
Topic |
Quizzes |
Reading |
Homework |
| Assign |
Due |
| Tue 01/30 |
Proofs, Strings & Languages |
|
1.1-1.5 |
HW1 |
|
| Thu 02/01 |
Deterministic Finite Automata (DFA) |
|
2.1-2.2 |
|
|
| Tue 02/06 |
Nondeterministic Finite Automata (NFA) |
|
2.3.1-2.3.4 |
HW2 |
HW1 |
| Thu 02/08 |
Equivalence of DFAs & NFAs |
|
2.3.4-2.3.6, 2.5 |
|
|
| Tue 02/13 |
Regular Expressions |
|
3.1-3.3 |
HW3 |
HW2 |
| Thu 02/15 |
Regular Language Pumping Lemma |
|
4.1 |
|
|
| Tue 02/20 |
Regular Language Closure Properties |
|
4.2 |
HW4 |
HW3 |
| Thu 02/22 |
Regular Language Decision Properties |
Quiz 1 |
4.3 |
|
|
| Tue 02/27 |
DFA Minimization |
|
4.4 |
HW5 |
HW4 |
| Thu 03/01 |
Context-free Grammars (CFG) |
|
5.1 |
|
|
| Tue 03/06 |
Parse Trees |
|
5.2 |
HW6 |
HW5 |
| Thu 03/08 |
Ambiguity |
Quiz 2 |
5.4 |
|
|
| Tue 03/13 |
Pushdown Automata (PDA) |
|
6.1-6.2 |
|
HW6 |
| Thu 03/15 |
PDAs for CFGs |
|
6.3.1 |
|
|
| Tue 03/20 |
Spring Break |
| Thu 03/22 |
Spring Break |
| Tue 03/27 |
CFGs for PDAs |
|
6.3.2 |
HW7 |
|
| Thu 03/29 |
Chomsky Normal Form |
|
7.1 |
|
|
| Tue 04/03 |
Context-free Pumping Lemma |
|
7.2 |
HW8 |
HW7 |
| Thu 04/05 |
Context-free Closure Properties |
Quiz 3 |
7.3 |
|
|
| Tue 04/10 |
Context-free Decision Properties |
|
7.4 |
HW9 |
HW8 |
| Thu 04/12 |
Turing Machines I |
|
8.1-8.2 |
|
|
| Tue 04/17 |
Turing Machines II |
|
8.3-8.4 |
HW10 |
HW9 |
| Thu 04/19 |
Turing Machines III |
Quiz 4 |
8.5-8.6 |
|
|
| Tue 04/24 |
Undecidability I |
|
9.1 |
HW11 |
HW10 |
| Thu 04/26 |
Undecidability II |
|
9.2 |
|
|
| Tue 05/01 |
Reductions |
|
9.3 |
HW12 |
HW11 |
| Thu 05/03 |
Undecidability III |
|
9.4-9.5 |
|
|
| Tue 05/08 |
P vs NP |
|
10.1 |
HW13 |
HW12 |
| Thu 05/10 |
NP-completeness I |
Quiz 5 |
10.2 |
|
|
| Tue 05/15 |
NP-completeness II |
|
10.3-10.4 |
|
HW13 |
| Thu 05/17 |
Final Exam 1:00pm - 3:00pm |
to Spring 2007 CMSC 451 Homepage