Week # | Lecture #s | Descriptions
| Handouts/Homework
|
13 | |
- Final Review
- P, NP, P-SPACE, NP-SPACE
| |
14 | |
- NO CLASS
- Exam Review, The class P and NP
| |
13 | | |
- Exam #3
- 15.1a,c, 15.3, 15.7, Exam Review
| |
12 | |
- Reducibility
- No class - Ramsey out sick
|
- 13.1, 13.2, 13.3, 13.5, 13.17 and 14.1, 14.3, 14.6
- No class - Ramsey out sick
|
11 | |
n- Countable Sets, Diagonalization, Halting Problem
- Librarian's Paradox, Recursive and Recursively Enumerable
|
- Test Submission, Chapter 12: 12.2, 12.3a, 12.13, 12.15, 12.18, 12.19
- Chapter 11, 11.1, 11.2, 11.3, 11.5-11.9 (describe algorithms),11.10, 11.11, 11.13a-c, 11.14a-c, 11.15, 11.17
|
10 | |
- Some decidable problems and proofs
- Turing machines and variations
| |
9 | | | |
8 | |
- Break
- Church's Thesis, HW Review
| |
7 | |
- Turing Machine, Halting, Nondeterminism, Multiple Tapes
- Pumping Lemma
|
-
- Chapter 9: 1-6,8-10,12,13,15a,16,17,20
|
6 | |
- Chomsky's Normal Form, Pumping Lemma
- Chomsky's Hierarchy, CFG->PDA
|
-
- Chapter 8: 1-4,8,10-12 (#6 for EC, but #5 may help)
|
5 | | |
-
- ALL Chapter 7 Problems (skip 7.7), Due Thursday 10/2
|
4 | |
- Context-Free Grammars
- Pumping Lemma, Closure Properties for Proofs
|
- All Chapter 6 problems Due Tuesday 9/30 (first T after Exam #1)
-
|
3 | |
- Applications: Bots, Elevators, Automatic Doors
- Pumping Lemma, Closure Properties
|
-
- Chapter 4 Homework: All (except 4.6b and 4.6c)
|
2 | |
- Regular Languages, Pumping Lemma
- Conversions ( RE->NFA<->DFA->RE )
|
- Chapter 3: all problems. (except #3 and #16)
-
|
1 | |
- Nondeterminism
- Finite Automata, Regular Expressions
|
- C2 1-5, 6 (REs only), 7-12, 13 (hard), 14-17, 18 (e.c.)
- Syllabus - All Chapter 1 Problems.
|