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