CS 373: Theory of Computation

Course Calendar

Class #	Date	Lecture Topic	Materials	Assignments
Week 1
1	8/25	Motivation, mathematical preliminaries	Sipser, Ch 0	HW 0 Assigned
2	8/27	More preliminaries	Sipser, Sec 1.1
Week 2
3	9/1	DFAs	Sipser, Sec 1.1	HW 0 Due in class
4	9/3	Closure theorems, NFAs	Sipser, Sec 1.2
Week 3
5	9/8	NFA-DFA equivalence; proving closure thms	Sipser, Sec 1.2
6	9/10	Regular expressions	Sipser, Sec 1.3
Week 4
7	9/15	Reg. expr., GNFAs, equivalence	Sipser, Sec 1.3
8	9/17	Nonregular languages, pumping lemma	Sipser, Sec 1.4	Hw 1 Due
Week 5
9	9/22	Using the pumping lemma	Sipser, Sec 1.4
10	9/24	Substitution, homomorphism, equivalence classes	handout
Week 6
11	9/29	equivalence classes; DFA minization	handout
12	10/1	Myhill-Nerode Theorem	handout	HW 2 Due
Week 7
13	10/6	Context free grammars and languages	Sipser 2.1
14	10/8	Chomsky normal form	Sipser 2.1
Week 8
15	10/13	Pushdown automata (PDAs)	Sipser 2.2
16	10/15	PDA-CFL equivalence	Sipser 2.2
Week 9
17	10/20	Pumping lemma for CFLs; non-CFLs	Sipser 2.3
18	10/22	Recursive automata	Notes	HW 3 Due
Week 10
19	10/27	CFL closure props	Handout
20	10/29	CYK algorithm, Turing machines	Sipser 3.1
Week 11
21	11/3	recognizable, decidable langs, TM examples	Sipser 3.1
22	11/5	TM variants, Church-Turing thesis	Sipser 3.2
Week 12
23	11/10	enumerators, Church-Turing thesis	Sipser 3.3
24	11/12	Decidability, halting problem	Sipser 4.1,4,2
Week 13
25	11/17	reducibility	Sipser 5.1
26	11/19	Post's correspondence problem, mapping reducibility	Sipser 5.2,5.3
Week 14
27	12/1	Complexity theory, P, NP	Sipser 7.1-7.3
28	12/3	NP-completeness	Sipser 7.4
Week 15
29	12/1	Mystery topic	???

Note: The recursive automata notes above were written by Madhusudan Parthasarathy and Sariel Har-Peled.