Week # Lecture #s Descriptions
Handouts/Homework
| 13 | - 28
- 27
- Final Review
- P, NP, P-SPACE, NP-SPACE
- Final Review
-
| 14 | - xx
- 26
- NO CLASS
- Exam Review, The class P and NP
-
-
| 13 | - 25
- 24
- Exam #3
- Review
- Exam #3
- 15.1a,c, 15.3, 15.7, Exam Review
| 12 | - 23
- 22
- 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 | - 21
- 20
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 | - 19
- 18
- Some decidable problems and proofs
- Turing machines and variations
-
-
| 9 | - 17
- 16
- Exam #2
- Review
- Exam #2
- Exam Review
| 8 | - xx
- 15
- Break
- Church's Thesis, HW Review
- Break
-
| 7 | - 14
- 13
- Turing Machine, Halting, Nondeterminism, Multiple Tapes
- Pumping Lemma
-
- Chapter 9: 1-6,8-10,12,13,15a,16,17,20
| 6 | - 12
- 11
- 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 | - 10
- 9
- Exam #1
- Review/PDA Intro
-
- ALL Chapter 7 Problems (skip 7.7), Due Thursday 10/2
| 4 | - 8
- 7
- Context-Free Grammars
- Pumping Lemma, Closure Properties for Proofs
- All Chapter 6 problems Due Tuesday 9/30 (first T after Exam #1)
-
| 3 | - 6
- 5
- Applications: Bots, Elevators, Automatic Doors
- Pumping Lemma, Closure Properties
-
- Chapter 4 Homework: All (except 4.6b and 4.6c)
| 2 | - 4
- 3
- Regular Languages, Pumping Lemma
- Conversions ( RE->NFA<->DFA->RE )
- Chapter 3: all problems. (except #3 and #16)
-
| 1 | - 2
- 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.
| |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | | | | | | | | | | | | | | | |