General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F12
Lecture Time: Monday,
Wednesday, Friday, 8:00am9:00am
Lecture Room: DMP
301
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
TA: Samira Samadi, samirasa@cs.ubc.ca.
Textbook
M. Sipser,
Introduction
to the Theory of Computation. 3^{rd} edition preferred, 2^{nd}
edition also OK.
Assignments
For
501 students only
Lectures

Date 
Topics 
Readings
3^{rd} Ed 
Readings
2^{nd} Ed 
Review 
Sets,
functions, graphs, strings, logic, proofs, induction 
Pages
327 
Pages
325 

1 
W 9/5 
What is
computation? Start of finite automata 
Pages 13 
Pages 13 
2 
F 9/7 
Finite
automata, regular languages, nondeterminism 
Pages
3154 
Pages
3154 
3 
M 9/10 
Nondeterministic
finite automata 
Pages
4762 
Pages
4767 
4 
W 9/12 
Regular
expressions 
Pages
6369 
Pages
6369 
5 
F 9/14 
Regular
expressions, Start of nonregular languages 
Pages
6976 
Pages
6976 
6 
M 9/17 
The
pumping lemma 
Pages
7782 
Pages
7782 
7 
W 9/19 
Pushdown
automata 
Pages
111114 
Pages
109112 
8 
F 9/21 
Contextfree
grammars 
Pages
101110 
Pages
99108 
9 
M 9/24 
Every CFG
is recognizable by a PDA 
Pages
117120 
Pages
115118 
10 
W 9/26 
Every PDA
can be described by a CFG 
Pages
121124 
Pages
119122 
11 
F 9/28 
The
pumping lemma for CFLs 
Pages
125129 
Pages
123127 
12 
M 10/1 
The
pumping lemma for CFLs 
Pages
125129 
Pages
123127 
13 
W 10/3 
Turing
machines 
Pages 165175 
Pages
137147 
14 
F 10/5 
Formal
definition 
Pages
167178 
Pages
139150 
15 
W 10/10 
Multitape
Turing machines 
Pages
176178 
Pages
148150 
16 
F 10/12 
Nondeterministic
Turing machines 
Pages
178180 
Pages
150152 
17 
M 10/15 
Hierarchy
of languages, Statement of the Halting Problem 
Pages
193202 
Pages
165174 
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 202210 
Pages
173182 
21 
W 10/24 
Reductions 
Pages
215220 
Pages
187192 
22 
F 10/26 
Selfreplication 
Pages
245252 
Pages
217224 
23 
M 10/29 
Time
complexity, definition of P 
Pages
275289 
Pages
247261 
24 
W 10/31 
Definition
of EXP, Time hierarchy theorem 
Pages
368371 
Pages
340343 
25 
F 11/2 
NP,
NPcompleteness 
Pages
292302 
Pages
264274 
26 
M 11/5 
Reductions,
NPcompleteness 
Pages
300306 
Pages
272278 
27 
W 11/7 
CookLevin
Theorem 
Pages
304311 
Pages
276283 
28 
F 11/9 
End of
CookLevin. Vertex Cover is NPcomplete. 
Pages
309313 
Pages
281285 
29 
W 11/14 
coNP, Unsatisfiability,
NP intersect coNP, Factoring. 
n/a 
n/a 
30 
F 11/16 
Definition
of Interactive Proofs and PSPACE 
Pages
415417 
Pages
387389 
31 
M 11/19 
IP is
contained in PSPACE 
Pages
418420 
Pages
390392 
32 
W 11/21 
coNP is contained in IP 
Pages
420425 
Pages
392397 
33 
F 11/23 
coNP is contained in IP 
Pages
420425 
Pages
392397 
34 
M 11/26 
n/a 
n/a 

35 
W 11/28 
n/a 
n/a 

36 
F 11/30 
Review
(focusing on NPcompleteness) 
n/a 
n/a 
Midterm Exam
Friday
October 19^{th}, inclass (8am8:50am, DMP 301)
·
Material
covered: Lectures 116.
·
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:30pm6: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.
o
Solution 1b is wrong.
o
Question 10 is not relevant. We did not define
“strongly NPcomplete”.
o
Unlike our final, this one has no questions at all
about NP.
o
Question 13: We did not discuss the MyhillNerode theorem.
o
Question 7: We did not discuss SubsetSum (but it is
in the textbook Section 7.5).