Lec.  Date  Syllabus  Reading  Handouts/Homework


1 
Tu, Jan 12 
Introduction, finite automata
(pdf) 
Chapters 01.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.11.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.11.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.11.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 
Contextfree grammars. Designing CFGs and PDAs. Equivalence of CFGs and PDAs (pdf) 
Chapters 2.12.2 

8 
Th, Feb 4 
Converting from PDAs to CFGs. Pumping lemma for CFLs (pdf) 
Chapters 2.22.3 
HW3 due, HW4 out 
9 
Tu, Feb 9 
Pumping lemma for CFLs. Proving a CFGs generates a given language. (pdf) 
Chapters 2.12.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 03.1 
Practice midterm solutions are distributed in class 

Wed, Feb 17 
Exam 8:1510: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. ChurchTuring 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 Turingunrecognizable 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 02.3,3.15.1, 5.36.1 
Practice midterm 2 solutions are distributed in class 

Wed, Mar 30 
Exam 8:1510: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.17.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 
Polynomialtime reductions (pdf) 
Chapters 7.47.5 
26 
Th, Apr 14 
Polynomialtime reductions. NPcompleteness. CookLevin Theorem. (pdf) 
Chapters 7.47.5 
HW10 due, HW11 out 
27 
Tu, Apr 19 
Examples of NPcomplete problems. (pdf) 
Chapters 7.47.5 

28 
Th, Apr 21 
Space complexity. Savitch's Theorem. PSPACE (pdf) 
Chapters 8.18.2 
HW11 due, HW12 and EXTRA CREDIT programming assignment out 
29 
Tu, Apr 26 
PSPACEcompleteness. 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:304:20pm in 022 DEIKE 