2018-19
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F18-421
Lecture Time: Monday,
Wednesday, Friday, 3:00pm-4:00pm
Lecture Room: DMP 110
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office Hours: Thursday 2-3pm in ICCS x851
TAs:
·
Sikander Randhawa, sikander_94@alumni.ubc.ca
o Office Hours: Tuesday 10-11am, Table 6 in DLC (ICCS
x150)
·
Curtis Fox, curtis.fox@alumni.ubc.ca
o Office Hours: Monday 1-2pm, Table 6 in DLC (ICCS x150)
·
⬆ Substituted On November 8th:
o
Chris Liaw, cvliaw@cs.ubc.ca
o
Office Hours:
Friday 10-11am, Table 5 in DLC (ICCS x150)
·
⬇ Substituted Off November 8th:
o
Shane Sims, ssims@cs.ubc.ca
o
Office Hours:
Friday 10-11am, Table 5 in DLC (ICCS x150)
Assignments
Here is the assignment policy.
Here is the latex template as tex file, and as an Overleaf project.
|
|
Handout |
Due |
Handback |
Link |
TA Grader |
|
0 |
W 9/5 |
M 9/10 |
F 9/14 |
Shane |
|
|
1 |
W 9/12 |
W 9/19 |
M 9/24 |
Curtis |
|
|
2 |
Th 9/20 |
F 9/28 |
F 10/5 |
Sikander |
|
|
3 |
F 9/28 |
F 10/5 |
F
10/12 |
Shane |
|
|
4 |
F
10/19 |
F 10/26 |
Su
11/04 |
Curtis |
|
|
5 |
F
10/26 |
F 11/2 |
Mo
11/12 |
Sikander |
|
|
6 |
Su
11/04 |
M 11/12 |
? |
Chris |
|
|
7 |
F
11/09 |
M 11/19 |
Th
11/28 |
Curtis |
|
|
8 |
W 11/21 |
F 11/30 |
|
Sikander |
Practice Problems
|
|
Link |
Topics |
|
P0 |
Basic set
theory |
|
|
P1 |
Regular
languages |
|
|
P2 |
Context-free
languages |
|
|
P3 |
Turing
machines and Decidability |
|
|
P4 |
P, NP,
NP-completeness |
|
|
P5 |
coNP |
|
|
P6 |
RP, BPP |
Lectures (may be slightly revised as the term unfolds)
|
|
Date |
Topics |
Readings |
|
Review |
Sets,
functions, graphs, strings, logic, proofs, induction |
Chapter 0 |
|
|
1 |
W 9/5 |
What is computation? Start of finite automata |
Section
1.1 |
|
2 |
F 9/7 |
Definition
of finite automata |
Section
1.1 |
|
3 |
M 9/10 |
Nondeterministic
finite automata |
Section
1.2 |
|
4 |
W 9/12 |
Converting
NFA-DFA, Operations on regular languages |
Section
1.2, 1.3 |
|
5 |
F 9/14 |
Regular
expressions, Non-regular languages |
Section
1.3, 1.4 |
|
6 |
M 9/17 |
Pumping
lemma: Proving languages are not regular |
Section
1.4 |
|
7 |
W 9/19 |
Push down
automata |
Section
2.2 |
|
8 |
F 9/21 |
Context
free grammars |
Section
2.1 |
|
9 |
M 9/24 |
Parse
trees, Converting CFGs to PDAs |
Section
2.1 & 2.2 |
|
10 |
W 9/26 |
Intro to
computability |
Section
3.1 & 3.3 |
|
11 |
F 9/28 |
Turing
machines |
Section
3.1 & 3.3 |
|
12 |
M 10/1 |
Decidable
& Recognizable Languages, Configurations, Variants of Turing machines |
Section
3.2 |
|
13 |
W 10/3 |
Examples
of Multitape and Nondeterministic TMs |
Section
3.2 |
|
14 |
F 10/5 |
Converting
NTM to DTM |
Section
3.2 |
|
M 10/8 |
No class:
Thanksgiving |
||
|
15 |
W 10/10 |
Encodings,
Universal Turing Machine, Countable Sets |
Section
4.2 |
|
16 |
F 10/12 |
Undecidability
of A_TM |
Section
4.2 |
|
M 10/15 |
Midterm
Exam |
||
|
17 |
W 10/17 |
Reductions |
Section
5.1 |
|
18 |
F 10/19 |
More
reductions |
Section
5.1 |
|
19 |
M 10/22 |
Definition
of P, EXP |
Section
7.1, 7.2 |
|
20 |
W 10/24 |
Time
hierarchy theorem, Definition of NP |
Section
9.1, 7.3 |
|
21 |
F 10/26 |
Polytime
Reductions, 2 Definitions of NP, SAT |
Section
7.3 |
|
22 |
M 10/29 |
NP-hardness
and NP-completeness |
Section
7.3 |
|
23 |
W 10/31 |
NP-completeness
of Clique |
Section
7.5 |
|
24 |
F 11/2 |
NP-completeness
of Vertex Cover |
Section
7.5 |
|
25 |
M 11/5 |
Cook-Levin
Theorem |
Section
7.4 |
|
26 |
W 11/7 |
coNP |
|
|
27 |
F 11/9 |
RP, coRP,
BPP |
Section
10.2, Arora-Barak
7 |
|
|
M 11/12 |
No class:
Remembrance Day |
|
|
28 |
W 11/14 |
Communication
complexity: definitions and examples |
|
|
29 |
F 11/16 |
Protocol
trees, Deterministic communication complexity, |
|
|
30 |
M 11/19 |
Tight
analysis of EQ, Fooling sets |
|
|
31 |
W 11/21 |
Disjointness,
Reduction to Network Monitoring |
|
|
32 |
F 11/23 |
Nondeterministic
Communication Complexity |
|
|
33 |
M 11/26 |
Reduction
from Equality |
|
|
34 |
W 11/28 |
Nondeterminism
and Covers |
|
|
35 |
F 11/30 |
A proof
that “P != NP” and “P = NP intersect coNP” |
Midterm Exam
In-class,
Monday October 15th.
·
Material
covered: Lectures 1-16.
·
Not
covered: GNFAs, Mapping Reductions, Pumping Lemma for CFLs, …
Piazza
Piazza signup link: https://piazza.com/ubc.ca/winterterm12018/cpsc421/home
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)
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