| Lec. | Date | Syllabus | Reading | Handouts/Homework
|
|---|
| 1 |
Tu, Jan 12 |
Introduction, finite automata
(pdf) |
Chapters 0-1.1 |
General Course Information,
Collaboration and Honesty Policy,
HW0 out;
play with JFLAP and Automa Tatutor |
| 2 |
Th, Jan 14 |
Operations on languages, regular operations, DFAs and NFAs
(pdf) |
Chapters 1.1-1.2 |
HW0 due, HW1 out |
| 3 |
Tu, Jan 19 |
Equivalence of DFAs and NFAs, closure of the class of regular languages under regular operations
(pdf) |
Chapters 1.1-1.2 |
| 4 |
Th, Jan 21 |
Closure of the class of regular languages under regular operations. Equivalence of DFAs, NFAs and regular expressions (pdf) |
Chapters 1.1-1.3 |
HW1 due, HW2 out |
| 5 |
Tu, Jan 26 |
Converting NFAs to regular expressions. Pumping lemma for regular languages (pdf) |
Chapter 1.4 |
|
| 6 |
Th, Jan 28 |
Proving that a language is not regular. Pushdown automata. (pdf) |
Chapters 1.4,2.2 |
HW2 due, HW3 out |
| 7 |
Tu, Feb 2 |
Context-free grammars. Designing CFGs and PDAs. Equivalence of CFGs and PDAs (pdf) |
Chapters 2.1-2.2 |
|
| 8 |
Th, Feb 4 |
Converting from PDAs to CFGs. Pumping lemma for CFLs (pdf) |
Chapters 2.2-2.3 |
HW3 due, HW4 out |
| 9 |
Tu, Feb 9 |
Pumping lemma for CFLs. Proving a CFGs generates a given language. (pdf) |
Chapters 2.1-2.3 |
|
| 10 |
Th, Feb 11 |
Review. Turing machines. (pdf) |
Chapter 3.1 |
HW4 due; practice midterm is distributed in class |
| 11 |
Tu, Feb 16 |
Review and Jeopardy! |
Chapters 0-3.1 |
Practice midterm solutions are distributed in class |
|
Wed, Feb 17 |
Exam 8:15-10:15pm in 101 Chambers |
| 12 |
Th, Feb 18 |
Turing machines. Turing machine variants (pdf) |
Chapters 3.1 -3.2 |
HW5 out |
| 13 |
Tu, Feb 23 |
TM variants. Church-Turing Thesis. (pdf) |
Chapters 3.2 -4.1 |
|
| 14 |
Th, Feb 25 |
Universal TM. Decidable languages. (pdf) |
Chapter 4.1 |
HW5 due, HW6 out, graded exams and exam solutions are distributed in class |
| 15 |
Tu, Mar 1 |
Decidable languages. Countable and uncountable sets.
Diagonalization. (pdf) |
Chapter 4.2 |
|
| 16 |
Th, Mar 3 |
Existence of Turing-unrecognizable languages. A_TM is undecidable. (pdf) |
Chapters 4.2 |
HW6 due, HW7 out |
| 17 |
Tu, Mar 15 |
Complement of A_TM is unrecognizable. Reductions. (pdf) |
Chapter 5.1 |
| 18 |
Th, Mar 17 |
Reductions. Mapping reductions. (pdf) |
Chapters 5.1,5.3. |
HW7 due, HW8 |
| 19 |
Tu, Mar 22 |
Mapping reductions. Computation history method. (pdf) |
Chapters 5.1, 5.3 |
| 20 |
Th, Mar 24 |
Review. Computation history method. Recursion theorem. (pdf) |
Chapter 6.1. |
HW8 due, practice problems for exam 2 are distributed in class |
| 21 |
Tu, Mar 29 |
Review (mostly on the board) (pdf) |
Chapters 0-2.3,3.1-5.1, 5.3-6.1 |
Practice midterm 2 solutions are distributed in class |
|
Wed, Mar 30 |
Exam 8:15-10:15pm in 101 Chambers |
| 22 |
Th, Mar 31 |
Finish Recursion Theorem. Time complexity. Review of asymptotic notation. Relationships between deterministic models. (pdf) |
Chapter 7.1 |
Exam 2 solutions are distributed in class, HW9 out |
| 23 |
Tu, Apr 5 |
Relationships between deterministic and nondeterministic models. Class P. (pdf) |
Chapters 7.1-7.2 |
|
| 24 |
Th, Apr 7 |
Class NP. Nondeterministic complexity classes. P vs. NP question. (pdf) |
Chapter 7.3 |
HW9 due, HW10 out, graded exams are distributed in class |
| 25 |
Tu, Apr 12 |
Polynomial-time reductions (pdf) |
Chapters 7.4-7.5 |
| 26 |
Th, Apr 14 |
Polynomial-time reductions. NP-completeness. Cook-Levin Theorem. (pdf) |
Chapters 7.4-7.5 |
HW10 due, HW11 out |
| 27 |
Tu, Apr 19 |
Examples of NP-complete problems. (pdf) |
Chapters 7.4-7.5 |
|
| 28 |
Th, Apr 21 |
Space complexity. Savitch's Theorem. PSPACE (pdf) |
Chapters 8.1-8.2 |
HW11 due, HW12 and EXTRA CREDIT programming assignment out |
| 29 |
Tu, Apr 26 |
PSPACE-completeness. Time and space hierarchy theorems (pdf) |
Chapters 8.3, 9.1 |
|
| 30 |
Th, Apr 28 |
Review (pdf) and ``Jeopardy!'' |
Chapter 9.1 |
HW12 due, Final exam preparation handout out |
|
Tu, May 3 |
Final Exam 2:30-4:20pm in 022 DEIKE |
