| Lec. | Date | Tentative Syllabus | Reading | Handouts/Homework
|
|---|
| 1 |
Tu, Sep 3 |
Introduction, finite automata, regular languages
(pdf) |
Chapters 0-1.1 |
General Course Information,
Collaboration and Honesty Policy,
HW0 out;
play with JFLAP and Automata Tutor |
| 2 |
Th, Sep 5 |
Operations on languages, regular operations, DFAs and NFAs
(pdf) |
Chapters 1.1-1.2 |
On Friday: HW0 due, HW1 out |
| 3 |
Tu, Sep 10 |
Equivalence of DFAs and NFAs, closure of the class of regular languages under regular operations
(pdf)
|
Chapters 1.1-1.2 |
| 4 |
Th, Sep 12 |
Equivalence of DFAs, NFAs and regular expressions
(pdf)
|
Chapters 1.1-1.3 |
On Friday: HW1 due, HW2 out |
| 5 |
Tu, Sep 17 |
Pumping lemma for regular languages. Proving that a language is not regular.
(pdf)
|
Chapter 1.4 |
|
| 6 |
Th, Sep 19 |
Pushdown automata. Context-free grammars.
(pdf)
|
Chapters 2.1-2.2 |
On Friday: HW2 due, HW3 out
|
| 7 |
Tu, Sep 24 |
Pumping lemma for CFLs.
(pdf)
|
Chapters 2.3 |
|
| 8 |
Th, Sep 26 |
Equivalence of CFGs and PDAs. Turing Machines
(pdf) |
Chapters 2.1-2.3, 3.1 |
HW3 due (on Friday), practice midterm is distributed in class |
| 9 |
Tu, Oct 1 |
Review and Jeopardy! |
Chapters 0-2.3 |
Practice midterm solutions are distributed in class |
| 10 |
Th, Oct 3 |
Midterm Exam 1 |
Chapters 0-2.3 |
On Friday: HW4 out |
| 11 |
Tu, Oct 8 |
Turing machines. TM variants.
(pdf) |
Chapters 3.1-3.3 |
Play with TM simulator |
| 12 |
Th, Oct 10 |
Church-Turing Thesis. Universal TM. Decidable languages.
(pdf) |
Chapter 3.3-4.1 |
On Friday: HW4 due, HW5 out |
| 13 |
Th, Oct 17 |
Decidable languages. Designing deciders.
(pdf) |
Chapter 4.1 |
On Friday: HW5 due, HW6 out |
| 14 |
Tu, Oct 22 |
Countable and uncountable sets.
Diagonalization. Existence of Turing-unrecognizable languages. A_TM is undecidable.
(pdf) |
Chapter 4.2 |
|
| 15 |
Th, Oct 24 |
Complement of A_TM is unrecognizable. Reductions.
(pdf) |
Chapters 4.2-5.1 |
On Friday: HW6 due, HW7 out |
| 16 |
Tu, Oct 29 |
Reductions. Mapping reductions.
(pdf) |
Chapters 5.1, 5.3 |
| 17 |
Th, Oct 31 |
Computation history method.
(pdf) |
Chapters 5.1,5.3, 6.1. |
HW7 due (on Friday), practice problems for midterm 2 are distributed in class |
| 18 |
Tu, Nov 5 |
Review and Jeopardy! |
Chapters 0-2.3,3.1-5.1, 5.3-6.1 |
Practice midterm 2 solutions are distributed in class |
| 19 |
Th, Nov 7 |
Midterm Exam 2 |
Chapters 0-2.3,3.1-5.1, 5.3 |
On Friday: HW8 out |
| 20 |
Tu, Nov 12 |
Recursion Theorem. Time complexity. Asymptotic notation.
(pdf) |
Chapters 6.3-7.1 |
Exam 2 solutions are distributed in class, programming assignment out |
| 21 |
Th, Nov 14 |
Relationships between models. Class P.
(pdf) |
Chapters 7.1-7.2 |
On Friday: HW8 due, HW9 out |
| 22 |
Tu, Nov 19 |
Class NP. P vs. NP question. (pdf) |
Chapters 7.3 |
|
| 23 |
Th, Nov 21 |
Polynomial-time reductions. NP-completeness. (pdf) |
Chapters 7.4-7.5 |
On Friday: HW9 and extra credit programming assignment due, HW10 out |
| 24 |
Tu, Nov 26 |
Cook-Levin Theorem. Examples of NP-complete problems. (pdf) |
Chapters 7.4-7.5 |
|
| 25 |
Tu, Dec 3 |
Space complexity. Savitch's Theorem. PSPACE. PSPACE-completeness. (pdf) |
Chapters 8.1-8.3 |
|
| 26 |
Th, Dec 5 |
PSPACE-completeness. Time and space hierarchy theorems. (pdf) |
Chapters 8.3, 9.1 |
HW10 due (on Friday); final exam preparation handout distributed in class |
| 27 |
Tu, Dec 10 |
Review and Jeopardy! |
|
|
|
Tu, Dec 17 |
Final Exam, 3:00pm-5:00pm CGS 311 |
