201819
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F18421
Lecture Time: Monday,
Wednesday, Friday, 3:00pm4:00pm
Lecture Room: DMP 110
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office Hours: Thursday 23pm in ICCS x851
TAs:
·
Sikander Randhawa, sikander_94@alumni.ubc.ca
o Office Hours: Tuesday 1011am, Table 6 in DLC (ICCS
x150)
·
Curtis Fox, curtis.fox@alumni.ubc.ca
o Office Hours: Monday 12pm, Table 6 in DLC (ICCS x150)
·
⬆ Substituted On November 8^{th}:
o
Chris Liaw, cvliaw@cs.ubc.ca
o
Office Hours:
Friday 1011am, Table 5 in DLC (ICCS x150)
·
⬇ Substituted Off November 8^{th}:
o
Shane Sims, ssims@cs.ubc.ca
o
Office Hours:
Friday 1011am, 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 
Contextfree
languages 

P3 
Turing
machines and Decidability 

P4 
P, NP,
NPcompleteness 

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
NFADFA, Operations on regular languages 
Section
1.2, 1.3 
5 
F 9/14 
Regular
expressions, Nonregular 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 
NPhardness
and NPcompleteness 
Section
7.3 
23 
W 10/31 
NPcompleteness
of Clique 
Section
7.5 
24 
F 11/2 
NPcompleteness
of Vertex Cover 
Section
7.5 
25 
M 11/5 
CookLevin
Theorem 
Section
7.4 
26 
W 11/7 
coNP 

27 
F 11/9 
RP, coRP,
BPP 
Section
10.2, AroraBarak
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
Inclass,
Monday October 15th.
·
Material
covered: Lectures 116.
·
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