2016-17
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F16
Lecture Time: Monday,
Wednesday, Friday, 8:00am-9:00am
Lecture Room: DMP 310
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office hours: Monday,
2:30-3:30pm in ICCS x851
TAs:
·
Bader Alahmad,
bader@ece.ubc.ca
o Office Hours: Friday 11am-12pm, ICCS x151
·
Devon Graham, drgraham@cs.ubc.ca
o Office Hours: Wednesday 1-2pm, ICCS x151
·
Chris Liaw,
cvliaw@cs.ubc.ca
o Office Hours: Tuesday 11am-12pm, Table 4 in DLC
(ICCS x150)
Final Exam
Monday
December 19th January 8th, 12pm-2: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 |
Context-free
languages |
|
|
P3 |
W 10/5 |
Turing machines
and Decidability |
|
|
P4 |
F
10/28 |
P, NP,
NP-completeness |
|
|
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,
NP-hardness and NP-completeness |
Section
7.4 |
|
22 |
F 10/28 |
Cook-Levin
Theorem |
Section
7.4 |
|
23 |
M 10/31 |
NP-completeness
of Clique |
Section
7.5 |
|
24 |
W 11/2 |
NP-completeness
of Vertex Cover |
Section
7.5 |
|
25 |
F 11/4 |
NP-completeness
of Hamiltonian Path |
Section
7.5 |
|
26 |
M 11/7 |
coNP |
|
|
27 |
W 11/9 |
RP, coRP, BPP, ZPP |
Section
10.2, Arora-Barak
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
pseudo-telepathy |
|
Midterm Exam
Monday
October 17th, in-class from 8am-8:50am.
· Material covered: Lectures 1-16.
· 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