201617
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F16
Lecture Time: Monday,
Wednesday, Friday, 8:00am9:00am
Lecture Room: DMP 310
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office hours: Monday,
2:303:30pm in ICCS x851
TAs:
·
Bader Alahmad,
bader@ece.ubc.ca
o Office Hours: Friday 11am12pm, ICCS x151
·
Devon Graham, drgraham@cs.ubc.ca
o Office Hours: Wednesday 12pm, ICCS x151
·
Chris Liaw,
cvliaw@cs.ubc.ca
o Office Hours: Tuesday 11am12pm, Table 4 in DLC
(ICCS x150)
Final Exam
Monday
December 19^{th}^{ }January 8^{th}, 12pm2:30pm in CHBE 101.
Assignments
Here is the assignment policy.

Handout 
Due 
Handback 
Link 
TA Grader 
0 
W 9/7 
M 9/12 
W 9/14 
Chris 

1 
M 9/12 
M 9/19 
F 9/23 
Bader 

2 
M 9/19 
M 9/26 
F 9/30 
Devon 

3 
M 9/26 
W 10/5 
M
10/10 
Chris 

4 
W 10/5 
Sa 10/15 
Th 10/20 
Bader 

5 
W
10/19 
W 10/26 
W 11/2 
Devon 

6 
F
10/28 
F 11/4 
M 11/7 
Chris 

7 
F 11/4 
Tu 11/15 
Su
11/20 
Bader 

8 
W
11/16 
W 11/23 
Tu 11/29 
Devon 

9 
F
11/25 
F 12/2 
M 12/5 
Chris 

Practice Problems

Handout 
Link 
Topics 
P0 
F 9/23 
Basic set
theory 

P1 
W 9/14 
Regular
languages 

P2 
Tu 9/27 
Contextfree
languages 

P3 
W 10/5 
Turing machines
and Decidability 

P4 
F
10/28 
P, NP,
NPcompleteness 

P5 
Th 11/10 
coNP 

P6 
M
11/14 
RP, BPP 
Lectures

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

1 
W 9/7 
What is computation? Start of finite automata 
Section
1.1 
2 
F 9/9 
Definition
of finite automata 
Section
1.1 
3 
M 9/12 
Nondeterministic
finite automata 
Section
1.2 
4 
W 9/14 
Regular
expressions 
Section
1.3 
5 
F 9/16 
The
pumping lemma 
Section
1.4 
6 
M 9/19 
Proving
languages are not regular 
Section
1.4 
7 
W 9/21 
Push down
automata 
Section
2.2 
8 
F 9/23 
Context free
grammars 
Section
2.1 
9 
M 9/26 
Parse
trees, Converting CFGs to PDAs 
Section
2.1 & 2.2 
10 
W 9/28 
Turing
machines 
Section
3.1 & 3.3 
11 
F 9/30 
Turing
machines 
Section
3.1 & 3.3 
12 
M 10/3 
Variants
of Turing machines 
Section
3.2 
13 
W 10/5 
Hierarchy
of languages, Start of halting problem 
Section
4.1 
14 
F 10/7 
The
halting problem 
Section
4.2 
M 10/10 
No class:
Thanksgiving 

15 
W 10/12 
Reductions 
Section
5.1 
16 
F 10/14 
More
reductions 
Section
5.1 
17 
M 10/17 
Midterm
Exam 

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

27 
W 11/9 
RP, coRP, BPP, ZPP 
Section
10.2, AroraBarak
7 
F 11/11 
No class:
Remembrance Day 

28 
M 11/14 
Communication
complexity: definitions and examples 

29 
W 11/16 
Rectangles
and fooling sets 

30 
F 11/18 
Disjointness and its applications 

31 
M 11/21 
Nondeterminism
and covers 

32 
W 11/23 
Nondeterminism.
Randomized, public coin model. 

33 
F 11/25 
Equality
in the public coin model. 

34 
M 11/28 
Equality
in the private coin model. Hash functions. 

35 
W 11/30 
GTE in private
coin model. 

36 
F 12/2 
Quantum
pseudotelepathy 

Midterm Exam
Monday
October 17^{th}, inclass from 8am8:50am.
· Material covered: Lectures 116.
· Not covered: GNFAs, Mapping
Reductions, Pumping Lemma for CFLs, …
Piazza
I
will use Piazza for all announcements, and you should use it for your own
questions and answers about course material. Posting questions to Piazza is a
better choice than sending email to the instructor or TAs individually, since
all of us are monitoring the group – plus, your classmates may have useful
answers! You may choose whether to post questions and answers anonymously or
using your own name. If you are asking a question that would reveal too much of
a homework solution, then please make sure to post it as a private question so
that your classmates cannot see it, only the instructors.
Bonus marks: will be given to major contributors to Piazza discussions.
· 1% will be given to selected individuals based on the amount of contributions by asking questions, answering questions whether correct or not.
· 2%
will be given to selected individuals based on the amount of quality
contributions, endorsed questions and answers, etc.
Course Links
Previous versions of this course
· Fall 2008, Prof. Greenstreet
Related courses at UBC
· CPSC 506 “Complexity of
Computation”, Fall 2016 (Prof. Condon)
· CPSC 506
“Complexity of Computation”, Fall 2010 (Prof. Condon)
· CPSC 506
“Complexity of Computation”, Fall 2005 (Prof. Condon)
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