| 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 |
Equivalence of DFAs & NFAs |
|
|
HW2 |
HW1 |
| Thu 02/11 |
Regular Expressions |
|
1.3 |
|
|
| Tue 02/16 |
Equivalence of Regular Expressions |
|
|
HW3 |
HW2 |
| Thu 02/18 |
Regular Language Pumping Lemma |
|
1.4 |
|
|
| Tue 02/23 |
Context-free Grammars (CFG) |
|
2.1 |
HW4 |
HW3 |
| Thu 02/25 |
Context-free Grammars (CFG) |
Quiz 1 |
|
|
|
| Tue 03/02 |
Chomsky Normal Form |
|
|
HW5 |
HW4 |
| Thu 03/04 |
Pushdown Automata (PDA) |
|
2.2 |
|
|
| Tue 03/09 |
PDAs for CFGs |
|
|
HW6 |
HW5 |
| Thu 03/11 |
CFGs for PDAs |
Quiz 2 |
|
|
|
| Tue 03/16 |
Spring Break |
| Thu 03/18 |
Spring Break |
| Tue 03/23 |
Context-Free Pumping Lemma |
|
2.3 |
HW7 |
HW6 |
| Thu 03/25 |
Turing Machines |
|
3.1 |
|
|
| Tue 03/30 |
Turing Machines |
|
3.2 |
HW8 |
HW7 |
| Thu 04/01 |
Regular Language Decision Properties |
Quiz 3 |
4.1 |
|
|
| Tue 04/06 |
Context-free Decision Properties |
|
|
HW9 |
HW8 |
| Thu 04/08 |
The Halting Problem |
|
4.2 |
|
|
| Tue 04/13 |
Undecidability |
|
5.1 |
HW10 |
HW9 |
| Thu 04/15 |
Undecidability |
Quiz 4 |
5.2 |
|
|
| Tue 04/20 |
Reductions |
|
5.3 |
HW11 |
HW10 |
| Thu 04/22 |
P vs NP |
|
7.1 – 7.3 |
|
|
| Tue 04/27 |
NP-completeness |
|
7.4 |
HW12 |
HW11 |
| Thu 04/29 |
NP-completeness |
Quiz 5 |
7.5 |
|
|
| Tue 05/04 |
Advanced Topic TBA |
|
|
HW13 |
HW12 |
| Thu 05/06 |
Advanced Topic TBA |
|
|
|
|
| Tue 05/11 |
Advanced Topic TBA |
|
|
|
HW13 |
| Thu 05/13 |
Advanced Topic TBA |
|
|
|
|
| Tue 05/18 |
Final Exam 10:30am – 12:30pm |
to Spring 2010 CMSC 451h Homepage