| Sessions | Suggested View Date | Chapter | Topics | Homework |
|---|---|---|---|---|
| 1-3 | Jan. 23 | 1 |
Introduction to the
course. Review sets, graphs, and trees. Basic proof techniques (induction, contradiction, construction). The basic concepts: langauges, grammars, automata. | Assignment #1: Due Fri. Jan. 30 Page 47: 1, 2, 15, 17; Page 54: 4, 8, 12; Answer Key |
| 4-6 | Jan. 30 | 2 |
Deterministic Finite
Automata, Langagues and DFAs, Regular Langauges
Nondeterministic Finite Automata Equivilences | Assignment #2: Due Fri. Feb. 6 Page 62: 3, 7, 11 Page 75: 1, 4, 16a, 16b; Answer Key |
| 7-8 | Feb. 06 | 3 |
Regular langauges
and regular grammers Regular expressions Equivilences | |
| 9-10 | Feb. 13 | 3 and 4 |
Regular langauges
and regular grammers Regular expressions Equivilences Closure properties | Assignment #3: Due Fri. Feb. 20 Section 3.2: 4a, 4b, 4c, 8a, 8b, 10a; Section 3.3: 1, 2, 6. Answer Key |
| 11-13 | Feb. 20 | 4 |
Closure properties Non-regular languages, pumping lemma. Palindromes. | Assignment #4: Due Fri Feb. 27, Section 4.1: 7, 12, 13 Section 4.3: 4a, 4b, 14, 15a, 15b, 24, 26. Answer Key part A Answer Key part B |
| 14-15 | Feb. 27 | 4 |
Context-free languages Context-free grammars Derivations and derivations trees Parsing and ambiguity | |
| 16-17 | March 06 | 5 |
Context-free languages Context-free grammars Derivations and derivations trees Parsing and ambiguity |
First Midterm Assignment #5: Due Fri March 13, Section 7.1: 3a, 4a, 4f, 4g, 5; Section 7.2: 1, 5, 7. Answer Key (includes 3 problems that were not assigned). |
| 18-20 | March 13 | 6 |
Pushdown automata Nondetermistic and deterministic pushdown automata Pushdown automata and context-free languages. | Assignment #6: Due Friday April 10th: Page Section 8.1: 1, 7c, 8b, 8c, 10; Section 8.2 7, 12, 17 Answer Key |
| 21-23 | March 27 | 7 | Properties of context-free languages: pumping lemma, closure properties, decision algorithms. | |
| 24-26 | April 03 | 9 | Turing Machines |
Assignment #7: Due Friday, April 17th, Section 9.2: 3b, 5a, 8; Section 10.1: 7.
Answer Key (includes several problems that were not assigned.
Turing machines: tapes, read/write, deterministic, Turing's Thesis |
| 27-28 | April 10 | 10 |
Minor Variations of Turing Machines | Suggested Review Questions (do not turn in, answers are in the back of the text): Section 7.1: 4f, 11; Section 7.2: 4, 11; Section 8.1 3; Section 8.2: 1, 5; Section9.1: 2, 7a, 7b; Section 9.2 3a, 5c; Section 10.1 4ab, 9 |
| 29-31 | April 17 | 10 | More Turing machine variations | |
| 32-34 | April 24 | 11 | Recursive and recusively enumerable languages. Unsolvable problems. | Assignment Due Fri May 01 Section 11.1 3, 5, 6, 8 Answer key |
| 35-36 | May 01 | |||
| 37-38 | May 08 | 11 | Recursive and recusively enumerable languages. Unsolvable problems. | Practice assignment (do not turn in): Section 11.4: 1; Section 12.1: 7; pg 311: 3; pg 351: 5; pg 359 8. |
| 16 | 12/8-12/13 | 12 | Limits of Algorithmic Computation | |
| 17 | 12/15-12/19 | Final exam week. Final: Monday Dec. 15th, 12:30-2:30. |