CPSC 421 & 501: Introduction to Theory of Computing
2012-13 Winter Term 1

	Date	Topics	Readings 3^rd Ed	Readings 2^nd Ed
Review		Sets, functions, graphs, strings, logic, proofs, induction	Pages 3-27	Pages 3-25
1	W 9/5	What is computation? Start of finite automata	Pages 1-3	Pages 1-3
2	F 9/7	Finite automata, regular languages, nondeterminism	Pages 31-54	Pages 31-54
3	M 9/10	Nondeterministic finite automata	Pages 47-62	Pages 47-67
4	W 9/12	Regular expressions	Pages 63-69	Pages 63-69
5	F 9/14	Regular expressions, Start of non-regular languages	Pages 69-76	Pages 69-76
6	M 9/17	The pumping lemma	Pages 77-82	Pages 77-82
7	W 9/19	Push-down automata	Pages 111-114	Pages 109-112
8	F 9/21	Context-free grammars	Pages 101-110	Pages 99-108
9	M 9/24	Every CFG is recognizable by a PDA	Pages 117-120	Pages 115-118
10	W 9/26	Every PDA can be described by a CFG	Pages 121-124	Pages 119-122
11	F 9/28	The pumping lemma for CFLs	Pages 125-129	Pages 123-127
12	M 10/1	The pumping lemma for CFLs	Pages 125-129	Pages 123-127
13	W 10/3	Turing machines	Pages 165-175	Pages 137-147
14	F 10/5	Formal definition	Pages 167-178	Pages 139-150
15	W 10/10	Multi-tape Turing machines	Pages 176-178	Pages 148-150
16	F 10/12	Nondeterministic Turing machines	Pages 178-180	Pages 150-152
17	M 10/15	Hierarchy of languages, Statement of the Halting Problem	Pages 193-202	Pages 165-174
18	W 10/17	Midterm Review Session	n/a	n/a
19	F 10/19	Midterm	n/a	n/a
20	M 10/22	The Halting Problem is Undecidable	Pages 202-210	Pages 173-182
21	W 10/24	Reductions	Pages 215-220	Pages 187-192
22	F 10/26	Self-replication	Pages 245-252	Pages 217-224
23	M 10/29	Time complexity, definition of P	Pages 275-289	Pages 247-261
24	W 10/31	Definition of EXP, Time hierarchy theorem	Pages 368-371	Pages 340-343
25	F 11/2	NP, NP-completeness	Pages 292-302	Pages 264-274
26	M 11/5	Reductions, NP-completeness	Pages 300-306	Pages 272-278
27	W 11/7	Cook-Levin Theorem	Pages 304-311	Pages 276-283
28	F 11/9	End of Cook-Levin. Vertex Cover is NP-complete.	Pages 309-313	Pages 281-285
29	W 11/14	coNP, Unsatisfiability, NP intersect coNP, Factoring. Notes (slides 20-31)	n/a	n/a
30	F 11/16	Definition of Interactive Proofs and PSPACE	Pages 415-417	Pages 387-389
31	M 11/19	IP is contained in PSPACE	Pages 418-420	Pages 390-392
32	W 11/21	coNP is contained in IP	Pages 420-425	Pages 392-397
33	F 11/23	coNP is contained in IP	Pages 420-425	Pages 392-397
34	M 11/26	Statement of the PCP Theorem. Notes1 Notes2 (first 3 pages)	n/a	n/a
35	W 11/28	Optimal approximation of MAX3SAT Notes1 Notes2	n/a	n/a
36	F 11/30	Review (focusing on NP-completeness)	n/a	n/a

Midterm Exam

Friday October 19^th, in-class (8am-8:50am, DMP 301)

· Material covered: Lectures 1-16.

· Practice 1, Solutions 1.

· Practice 2, Solutions 2

· Practice 3, Solutions 3. We did not discuss ambiguous grammars or HALT.

· Practice 4. We did not discuss undecidable languages.

· Practice 5. We did not discuss equivalence relations on DFA states.

Final Exam

Saturday December 8^th, 3:30pm-6:00pm DMP 310

· Material covered: Much more emphasis on the material after the midterm, particularly NP; little emphasis on automata. At least one question relates at least a little bit to PCP & MAX3SAT.

· Practice 1, Solutions 1

o Solution 1b is wrong.

o Question 10 is not relevant. We did not define “strongly NP-complete”.

· Practice 2, Solutions 2

o Unlike our final, this one has no questions at all about NP.

· Practice 3

o Question 1-3: We did not discuss the Myhill-Nerode theorem.

o Question 7: We did not discuss Subset-Sum (but it is in the textbook Section 7.5).

CPSC 421 & 501: Introduction to Theory of Computing 2012-13 Winter Term 1

CPSC 421 & 501: Introduction to Theory of Computing
2012-13 Winter Term 1