Week # Lecture #s Description
15 | |
- Exam: Wednesday or Friday 4:00-6:00 Dunn 106
14 | - 40
- 41
- FINAL REVIEW
- #3 Review
13 | - 39
- 38
- 37
- Exam #3
- Review #3
- SPACE
12 | - 36
- 35
- 34
- The class NP
- The class P
- Algorithm Analysis
11 | - 33
- 32
- 31
- Reducibility proofs
- Reducibility
- Tightest Classfications
10 | - 30
- 29
- 28
- Tightest Classification
- ADVISING DAY
- Venn, ATM, Halting Problem, an unrecognizable laguage
9 | - 27
- 26
- 25
- ACFG and ECFG - recognizable
- Decidable problems (dealing wit A,E, and regular languages)
- Decidable, Recognizable
8 | - 24
- 23
- 22
- Review
- Exam #2
- Turing Machines
7 | - 21
- 20
- 19
- Chapter 2 Review
- Chapter 2 problems: 2.18, 2.26, 2.31, 2.33, 2.38, 2.39
- CFG pumping lemma problems: 2.30
6 | - 18
- 17
- 16
- CFGs written as PDAs problems: 2.2, 2.11, 2.12
- PDAs continued. (minor proofs: 2.15, 2.16)
- PDAs, problems: 2.5, 2.7, 2.10
5 | - 15
- 14
- 13
- Chomsky's Normal Form, problems: 2.14
- CFGs problems: 2.8, 2.9, 2.13
- CFGs problems: 2.1, 2.3, 2.4
4 | - 12
- 11
- 10
- Exam #1
- Snow Day
- Context Free Languages
3 | - 9
- 8
- 7
- Review Problems
- more pumping lemma, Chapter 1, PROBLEMS:1.31,1.36,1.39,1.41, 1.46, 1.48,1.53-1.55
- GNFA->reg exp example, pumping lemma 1.16-1.23, 1.28-1.30
2 | - 6
- 5
- 4
- regular expressions, proof reg = NFA, GNFA, NFA->GNFA->reg exp
- NFA construction proofs, regular expressions 1.12-1.15
- NFA, proofs problems: 1.7-1.11,1.16,1.17
1 | - 3
- 2
- 1
- DFA, NFA, operations C1 problems 1.4,1.5,1.6,
- Regular Languages, Finite Automata - Chapter 1 problems: 1.1, 1.2, 1.3
- Sets - Chapter 0
- Syllabus
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | | | |