CS 365 Models of Computation

Winter 2010

Lectures and Readings

Below is a tentative schedule of the lectures along with associated readings (pages from the text). The schedule of topics to be covered may change slightly as the course progresses.

Date	Topic	Reading
January 5	Course overview; countable and uncountable sets; alphabets, strings, and languages	3–16, 174–177
January 7	Regular languages; DFAs, NFAs, and their equivalence	31–62
January 12	Regular expressions; closure properties of regular languages	63–76
January 14	The pumping lemma for regular languages; the Myhill-Nerode theorem	77–82
January 19	Context-free grammars; ambiguity; pushdown automata	99–106, 109–122
January 21	Normal forms for CFGs; closure properties of CFGs; pumping lemma for CFGs	106–109, 123–127
January 26	The Turing machine model; variants of Turing machines	137–150
January 28	Midterm exam #1
February 2	Specifications of DTMs; the Church-Turing thesis; encoding schemes	154–159
February 4	Decidable and Turing-recognizable languages; NTMs	150–154
February 9	Decidable languages about regular and context-free languages; diagonalization and a non-Turing-recognizable language	165–182
February 11	The recursion theorem; Rice's theorem	217–224
February 16 February 18	Reading week
February 23	Mapping reductions	187–192
February 25	Turing reductions; arithmetic hierarchy; busy beaver function	232–233
March 2	Time- and space-bounded computation; time and space hierarchy theorems	247–256, 303–305, 336–343
March 4	Midterm exam #2
March 9	Boolean circuits and their relationship to Turing machines	351–360
March 11	P and NP; the Cook-Levin theorem	256–283
March 16	PSPACE; QBF is PSPACE-complete	308–314
March 18	Savitch's theorem; the Immerman-Szelepcsényi theorem	305–307, 320–328
March 23	Randomized computation; RP and BPP; the Schwartz-Zippel lemma and polynomial identity testing	368–370, 375–380
March 25	Interactive proof systems	387–392
March 30	IP = PSPACE	392–399