| Textbook: |
|
| Week # - Date | Topic | Reading Assignment |
M: Jan 9 - F: Jan 13 |
M: Introduction
W: Mathematical Preliminaries: Sets & Induction F: Three Basic Concepts |
M:
W: Linz Ch 1.1 F: Linz Ch 1.2 |
M: Jan 16 - F: Jan 20 |
M: no class
W: Some Applications/ Intro to DFA's F: DFA's |
M:
W: Linz Ch 1.3 - Ch 2.1 F: Linz Ch 2.1; JFLAP Ch 1.1 - 1.2 |
M: Jan 23 - F: Jan 27 |
M: NDFA's
W: Equivalence of DFA's and NDFA's F: Regular Expressions |
M: Linz Ch 2.2; JFLAP Ch 1.3
W: Linz Ch 2.3; JFLAP Ch 2.1 F: Linz Ch 3.1 |
M: Jan 30 - F: Feb 3 |
M: Regular Languages
W: Regular Grammars F: Closure Properties of Regular Grammars |
M: Linz Ch 3.2
W: Linz Ch 3.3; JFLAP Ch 3 F: Linz Ch 4.1 - Ch 4.2 |
M: Feb 6 - F: Feb 10 |
M: Pumping Lemmas
W: Review F: Test #1 |
M: Linz Ch 4.3
W: F: |
M: Feb 13 - F: Feb 17 |
M: Context Free Grammars
W: CF Grammars, Parsing and Ambiguity F: CF Grammars and Programming Languages |
M: Linz Ch 5.1; JFLAP Ch 6.1
W: Linz Ch 5.2 F: Linz Ch 5.3 |
M: Feb 20 - F: Feb 24 |
M: Methods for Transforming Grammars
W: A Top Down Parser F: Chomsky & Greibach Normal Forms |
M Linz Ch 6.1
W: F: Linz Ch 6.2 |
M: Feb 27 - F: Mar 2 |
M: CYK Algorithms
W: NPDA's F: NPDA's |
M: Linz Ch 6.3
W: Linz Ch Ch 7.1 JFLAP Ch 5 F: Linz Ch 7.1 JFLAP Ch 5 |
M: Mar 5 - F: Mar 9 |
|
relax |
M: Mar 12 - F: Mar 16 |
M: NPDA's and CF Languages
W: Deterministic PDA's F: DPDA's and DCF Lanugages |
M: Linz Ch 7.2
W: Linz Ch 7.3 F: Linz Ch 7.4 |
M: Mar 19 - F: Mar 23 |
M: Two Pumping Lemmas
W: Closure Properties of CF Languages F: Review |
M: Linz Ch 8.1
W: Linz Ch 8.2 F: |
M: Mar 26 - F: Mar 30 |
M: Test #2
W: The Standard Turing Machine F: Combining Turing Machines; Turing's Thesis |
M:
W: Linz Ch 9.1; JFLAP Ch 9.1 F: Linz Ch 9.2 - 9.3; JFLAP Ch 9.2 |
M: Apr 2 - F: Apr 6 |
M: Variations on Turing Machines
W: A Universal Turing Machine F: Good Friday - No Class |
M: Linz Ch 10.1 - 10.3
W: Linz Ch 10.4 F: |
M: Apr 9 - F: Apr 13 |
M: LBA's
W: Recursive and Recursively Enumerable Languages F: Unrestricted Grammars (MAA Meeting) |
M: Linz Ch 10.5
W: Linz Ch 11.1 F: Linz Ch 11.2 |
M: Apr 16 - F: Apr 20 |
M: Context Sensitive Grammars & Languages
W: The Chomsky Hierarchy :F: The Halting Problem |
M: Linz Ch 11.3
W: Linz Ch 11.4 F: Linz Ch 12.1 Sci. Am. Hopcroft Article |
M: Apr 23 - F: Apr 27 |
M: Review
W: Test #3 F: Computational Complexity |
M:
W: F: Linz Ch 14.1 - Ch 14.3 |
M: Apr 30 - W: May 2 |
M: Complexity Classes P and NP
W: Catch Up & Review |
M:Linz Ch 14.4 - Ch 14.6
W: |
May 8 3:30 - 6:30 PM |
Final Exam (200 pts) | Review & Study |