Date Week # Lecture #s Description Files/HW/Links
| 12/14-12/18 | 16 - 46
- Final Exams
- Final Exams
| 12/7 | 15 - 45
- 44
- 43
- Reading Day
- Review
- NP-complete and problems
- No Class
-
-
| 11/30 | 14 - 42
- 41
- 40
- problems
- PSPACE NPSPACE, L, NL, relationships
- PvNP
-
-
-
| 11/23 | 13 - 39
- 38
- 37
- Thanksgiving Break
- Thanksgiving Break
- P vs. NP
-
- No Class
- No Class
| 11/16 | 12 - 36
- 35
- 34
- Complexity
- Space
- Review
-
-
-
| 11/9 | 11 - 33
- 32
- 31
- Exam 3
- Reducibility/Review
- Reducibility Problems/Rice's Thm
-
-
- C15: 1a,c, 3, 7
| 11/2 | 10 - 30
- 29
- 28
- Reducibility
- Advising Day
- Recursive, Recursively Enumerable, TMs, Decidability, etc
-
- No Class
-
| 10/26 | 9 - 27
- 26
- 25
- Halting Problem
- Countable
- Countable
-
- C14: 1, 3, 6
-
| 10/19 | 8 - 24
- 23
- 22
- Decidable Languages
- Decidable Languages
- Turing Machines/Decidable vs. Recognizable
- C13: 1, 2, 3, 5, 8, 17
-
- C12: 2, 3.a, 7, 13, 15, 18, 19
| 10/12 | 7 - 21
- 20
- 19
- Fall Break
- Exam
- Turing Machines
- No Class
-
-
| 10/5 | 6 - 18
- 17
- 16
- Pumping Lemma
- Pumping Lemma
- CFG Properties
-
- C9.1, 9.3, 9.5, 9.9, 9.10, 9.15
- C8.1, 8.10, 8.11
| 9/28 | 5 - 15
- 14
- 13
- CNF, CFGs, HW
- CNF
- PDAs, CFGs, CNF
-
- C7: 7.2, 7.3, 7.6, 7.18 (look at the rest)
- C6: 6.2, 6.5, 6.10, 6.11, 6.17 (look at the rest)
| 9/21 | 4 - 12
- 11
- 10
- PDAs
- Exam #1
- Review / Context Free Grammars/Languages
-
-
-
| 9/14 | 3 - 9
- 8
- 7
- Quiz, Applications
- Closure Properties
- Pumping Lemma
- Chapter 4 Hand In: 1, 2, 3, 5, 8, 11, 12, 13, 14
- In C4: Think About: 4, 6, 7, 9, 10, 15, 16, 17
-
| 9/7 | 2 - 6
- 5
- 4
- Quiz, Pumping Lemma
- Conversions,Regular Languages
- Conversions (RE->NFA<->DFA->RE)
- Chapter 3: all problems except #3 and 16
-
-
| 8/31 | 1 - 3
- 2
- 1
- Quiz, Nondeterminism
- Regular Expressions
- Automata, Finite, Regular Expressions
- Chapter2 problems 1-5, 6 (REs only), 7-12, 13(hard),14-17,18(e.c)
- All of chapter 1
- Syllabus
| |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | | | |