201314
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F13
Lecture Time: Monday,
Wednesday, Friday, 8:00am9:00am
Lecture Room: DMP
301
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office hours: Friday 121pm
in X851
TA: Sharan Vaswani, sharanv@cs.ubc.ca
·
Office hours: Monday 23pm
in Demco Learning Center
Piazza
We
will use Piazza for course discussions, etc. Here is the signup link.
Assignments
Assignment 0 due Wednesday September 11^{th}. Solutions.
Assignment 1 due Friday September 20^{th}. Solutions.
Assignment 2 due Monday September 30^{th}. Solutions.
Assignment 3 due Wednesday October 9^{th}. Solutions.
Assignment 4 due Friday October 25^{th}. Solutions.
Assignment 5 due Monday November 4^{th}. Solutions.
Assignment 6 due Friday November 15^{th}. Solutions.
Assignment 7 due Wednesday November 27^{th}. Solutions.
Lectures

Date 
Topics 
Readings 
Review 
Sets, functions,
graphs, strings, logic, proofs, induction 
Chapter 0 

1 
W 9/4 
What is computation? Start of finite automata 
Section
1.1 
2 
F 9/6 
Definition
of finite automata 
Section
1.1 
3 
M 9/9 
Nondeterministic
finite automata 
Section 1.2 
4 
W 9/11 
Regular
expressions 
Section
1.3 
5 
F 9/13 
The
pumping lemma 
Section
1.4 
6 
M 9/16 
Proving
languages are not regular 
Section
1.4 
7 
F 9/20 
Push down
automata 
Section
2.2 
8 
M 9/23 
Context
free grammars 
Section
2.1 
9 
W 9/25 
Parse
trees, Converting CFGs to PDAs 
Section
2.1 & 2.2 
10 
F 9/27 
Turing
machines 
Section
3.1 & 3.3 
11 
M 9/30 
Turing
machines 
Section
3.1 & 3.3 
12 
W 10/2 
Variants
of Turing machines 
Section
3.2 
13 
F 10/4 
Hierarchy
of languages, Start of halting problem 
Section
4.1 
14 
M 10/7 
The
halting problem 
Section
4.2 
15 
W 10/9 
Reductions 
Section
5.1 
16 
F 10/11 
Selfreplication 
Section
6.1 
17 
W 10/16 
Midterm
Exam 

18 
F 10/18 
Definition
of P, EXP 
Section
7.1, 7.2 
19 
M 10/21 
Time
hierarchy theorem 
Section
9.1 
20 
W 10/23 
Definition
of NP 
Section
7.3 
21 
F 10/25 
Reductions,
NPhardness and NPcompleteness 
Section
7.4 
22 
M 10/28 
CookLevin
Theorem 
Section
7.4 
23 
W 10/30 
NPcompleteness
of 3SAT and Clique 
Section
7.5 
24 
F 11/1 
NPcompleteness
of Vertex Cover and Hamilton Path 
Section
7.5 
25 
M 11/4 
coNP 

26 
W 11/6 
RP, coRP, BPP, ZPP 
Section
10.2, AroraBarak 7 
27 
F 11/8 
Error
reduction in BPP. Circuits for BPP algorithms. 

28 
W 11/13 
Communication
complexity: definitions and examples 

29 
F 11/15 
Rectangles
and fooling sets 

30 
M 11/18 
Disjointness and its applications 

31 
W 11/20 
Nondeterminism and covers 

32 
F 11/22 
Relating
determinism and nondeterminism 

33 
M 11/25 
Randomized
communication complexity 

34 
W 11/27 
Universal
hashing and the Equality function 

35 
F 11/29 
Quantum
pseudotelepathy 
Midterm Exam
Wednesday
October 16^{th}, inclass from 8am8:50am. Solutions.
·
Material
covered: Lectures 116.
·
Last year’s CPSC 421 midterm
·
Practice 3, Solutions 3.
We did not discuss ambiguous grammars or noncontextfree languages.
·
Practice 4.
We did not discuss noncontextfree languages.
·
Practice
5. We did not discuss equivalence relations on DFA states.
Final Exam
Thursday
December 12th, 8:3011:00am in DMP 110
·
Material
covered: Much more emphasis on the material after the midterm;
little emphasis on automata. But, no
quantum stuff on final.
·
Last year’s CPSC 421 final.
Solutions.
o
Not covered this year: Question 1.3, 1.8, 2(c), 5.
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).
Course Links
Previous versions of this course
·
Fall
2008, Prof. Greenstreet
Related courses at UBC
·
CPSC 506 “Complexity
of Computation”, Fall 2012
·
CPSC
506 “Complexity of Computation”, Fall 2010
·
CPSC 506
“Complexity of Computation”, Fall 2005
Computability theory at other universities
·
Caltech’s
“Decidability and Tractability” by Chris Umans
Communication complexity at other universities
·
UCLA's "Communication
Complexity" by Alexander Sherstov
·
Aarhus
University’s “Communication Complexity” by Joshua Brody
·
Toronto's
"Foundations of Communication Complexity" by Toniann
Pitassi