CS121/CSCI E-207 Schedule

(colors indicate weeks)

"Sipser" =Introduction to the Theory of Computation, 2e

#	Day	Date	Topic	Readings	Slides	Handouts	Problem Sets
1	Th	Sept. 1	Inroduction and Overview		pdf	cs121.cls (needed for LaTeXing your problem set solutions)	PS0a (tex, pdf); PS0b (tex, pdf -- corrected 9/5)
Unit 1: Mathematical Background
2	Tu	Sept. 6	Sets, Relations, Strings, Languages	Sipser, 1–16	pdf Full proof about Fib. #s	The Greek alphabet A LaTeX tutorial Another LaTex tutorial
3	Th	Sept. 8	Proofs and DFAs	Sipser, 17–25	pdf	Latex cheat sheet Another latex cheat sheet Finding latex code for symbols
	M	Sept. 12					PS0 due PS0a soln PS0b soln
Unit 2: Finite Automata and Regular Languages
4	Tu	Sept. 13	Finite Automata	Sipser, 31–47	pdf		PS1a (tex, pdf); PS1b (tex, pdf); new cs121.cls
5	Th	Sept. 15	Nondeterministic Finite Automata, Closure properties	Sipser, 47–63	pdf
6	Tu	Sept. 20	Regular Expressions	Sipser, 63–76	pdf
7	Th	Sept. 22	Regular languages; counting	Sipser, 174–177	pdf
	Fr/M	Sept. 23/26					PS1 Due Soln1a,Soln1b PS2a (tex, pdf), PS2b (tex, pdf)
8	Tu	Sept. 27	Nonregular languages, minimization	Sipser, 77–82	pdf
Unit III: Context-Free Languages
9	Th	Sept. 29	Context-Free Grammars	Sipser, 99–109	pdf
	Fr/M	Sept. 30/Oct. 3					PS2 Due Soln2a, Soln2b PS3a (tex, pdf), PS3b (tex, pdf) Soln3a, Soln3b
10	Tu	Oct. 4	Pushdown Automata	Sipser, 109–123	pdf
11	Th	Oct. 6	Closure properties, non-CFLs	Sipser, 123–127	pdf
	Fr/M	Oct. 7/10					PS3 Due Practice Midterm Practice midterm solution
	Mon	Oct. 10	Midterm Review sections 3-4 and 4-5pm in MD G115
	Tu	Oct. 11	MIDTERM EXAMINATION on material Through CFGs but not PDAs Midterm exam Midterm Solutions (2nd Correction)
12	Th	Oct. 13	General CF recognition		pdf
	Fr/M	Oct. 14/17					PS4a (tex, pdf) PS4b (tex, pdf)
Unit IV: Computability
13	Tu	Oct. 18	Turing Machines and Simulations	Sipser, 137–147	pdf	Hilbert paper Turing paper
14	Th	Oct. 20	Alternative models, Church's Thesis	Sipser, 148–159	pdf
	Fr/M	Oct 21/24					PS4 due Soln4a, Soln4b PS5a(tex, pdf) PS5b(tex, pdf)
15	Tu	Oct. 25	Decidability, Universal machines	Sipser, 165–173	pdf
16	Th	Oct. 27	Undecidability		pdf
	Fr/M	Oct. 28/31					PS5 Due Soln5a, Soln5b PS6a (tex, pdf, state-diagram) PS6b (tex, pdf)
Unit V: Uncomputability
17	Tu	Nov. 1	Undecidability II	Sipser, 173–174 and 178–182	pdf
18	Th	Nov. 3	Undecidable Problems and Unprovable Theorems	Sipser, 187–192, 206–210	pdf
	Fr/M	Nov. 4/7					PS6 Due Soln6a, Soln6b) PS7a (tex, pdf), PS7b (tex, pdf)
Unit VI: Complexity
19	Tu	Nov. 8	Computational Complexity	Sipser, 224–231	pdf	Knuth's futile 1976 article Big Omicron and Big Omega and Big Theta
20	Th	Nov. 10	Polynomial time	Sipser, 247–263	pdf
	M	Nov. 14					PS7 Due (no late date) Soln7a, Soln7b
21	Tu	Nov. 15	NP	Sipser, 264–270	pdf		PS8a (tex, pdf), PS8b (tex, pdf)
22	Th	Nov. 17	NP-Completeness	Sipser, 271–276, 283–294	pdf
	Fr/M	Nov. 18/21
23	Tu	Nov. 22	Cook-Levin Theorem; Space, Time	Sipser, 276–283, 303–209	pdf	Cook's account of P=?NP for the Clay Millennial Prize awards	PS8 Due -- NO LATE DATE Soln8a, Soln8b PS9a (tex, pdf), PS9b (tex,pdf)
	Th	Nov. 24	THANKSGIVING DAY
24	Tu	Nov. 29	Space and other resources	Sipser, 365–411, passim	pdf
25	Th	Dec. 1	Conclusion		pdf
	Tu	Dec. 6					PS9 Due Soln9a, Soln9b
	Fr	Dec. 16	Review Section, 7-9 PM, Maxwell Dworkin G115. (will be videotaped). Section Notes: 0, 1, 2, 3, midterm, 4, 5, 6, 7, 7b, 8, 9 Old finals for practice: 2008, 2009, and 2010
	Tu	Dec. 20	FINAL EXAMINATION CS121: 2-5 PM, Emerson 210