Lec.  Date  Tentative Syllabus  Reading  Handouts/Homework


1 
Tu, Sep 3 
Introduction, finite automata, regular languages
(pdf) 
Chapters 01.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.11.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.11.2 
4 
Th, Sep 12 
Equivalence of DFAs, NFAs and regular expressions
(pdf)

Chapters 1.11.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. Contextfree grammars.
(pdf)

Chapters 2.12.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.12.3, 3.1 
HW3 due (on Friday), practice midterm is distributed in class 
9 
Tu, Oct 1 
Review and Jeopardy! 
Chapters 02.3 
Practice midterm solutions are distributed in class 
10 
Th, Oct 3 
Midterm Exam 1 
Chapters 02.3 
On Friday: HW4 out 
11 
Tu, Oct 8 
Turing machines. TM variants.
(pdf) 
Chapters 3.13.3 
Play with TM simulator 
12 
Th, Oct 10 
ChurchTuring Thesis. Universal TM. Decidable languages.
(pdf) 
Chapter 3.34.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 Turingunrecognizable languages. A_TM is undecidable.
(pdf) 
Chapter 4.2 

15 
Th, Oct 24 
Complement of A_TM is unrecognizable. Reductions.
(pdf) 
Chapters 4.25.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 02.3,3.15.1, 5.36.1 
Practice midterm 2 solutions are distributed in class 
19 
Th, Nov 7 
Midterm Exam 2 
Chapters 02.3,3.15.1, 5.3 
On Friday: HW8 out 
20 
Tu, Nov 12 
Recursion Theorem. Time complexity. Asymptotic notation.
(pdf) 
Chapters 6.37.1 
Exam 2 solutions are distributed in class, programming assignment out 
21 
Th, Nov 14 
Relationships between models. Class P.
(pdf) 
Chapters 7.17.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 
Polynomialtime reductions. NPcompleteness. (pdf) 
Chapters 7.47.5 
On Friday: HW9 and extra credit programming assignment due, HW10 out 
24 
Tu, Nov 26 
CookLevin Theorem. Examples of NPcomplete problems. (pdf) 
Chapters 7.47.5 

25 
Tu, Dec 3 
Space complexity. Savitch's Theorem. PSPACE. PSPACEcompleteness. (pdf) 
Chapters 8.18.3 

26 
Th, Dec 5 
PSPACEcompleteness. 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:00pm5:00pm CGS 311 