202223
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F22
Lecture Time: Tuesday
Thursday, 12:30pm2:00pm
Lecture Room: UBC
Life Building 2302
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office Hours: Monday 121pm,
ICCS x851
TAs:
·
Ryan Liu
o Office hours: Wednesday 34pm
·
Hassan Mallahzadeh
o Office hours: Thursdays 9:3010:30am
·
Markus de Medeiros
o Office hours: Tuesdays 11am12pm
Assignments

Handout 
Due 
Link 
TA Grader 
1 
Th 9/8 
Tu 9/13 
Hassan 

2 
Tu 9/13 
Tu 9/20 
Markus 

3 
Tu 9/20 
Tu 9/27 
Ryan 

4 
Tu
9/27 
Tu 10/4 
Hassan 

5 
Tu
10/4 
Th 10/13 
Markus 

6 
Tu
10/25 
Tu 11/1 
Ryan 

7 
Th
11/3 
Tu 11/15 
Hassan 

8 
Tu
11/15 
Th 11/24 
Markus 

9 
Th
11/24 
Tu 12/6 
Ryan 
Exams
·
Midterm:
Tuesday October 18^{th}, in class.
·
Final: Thursday December 15^{th}, 12:00pm,
IBLC 182.
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

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

1 
Th 9/8 
What is
computation? Definition of languages 
Section
1.1 
2 
Tu
9/13 
Finite
automata 
Section
1.2 
3 
Th
9/15 
Converting
NFADFA, Regular languages & expressions 
Section
1.3, 1.4 
4 
Tu
9/20 
Nonregular
languages, Pumping lemma 
Section
1.4 
5 
Th
9/22 
Push down
automata, Context free grammars 
Section
2.2 
6 
Tu
9/27 
Parse
trees, Converting CFGs to PDAs 
Section
2.1 
7 
Th
9/29 
Intro to
computability, Turing machines 
Section
3.1, 3.3 
8 
Tu
10/4 
Decidable
& Recognizable Languages, Configurations, Multitape
Turing machines 
Section
3.2 
9 
Th
10/6 
Nondeterministic
TMs; Converting NTM to DTM 
Section
3.2 
10 
Tu
10/11 
Encodings,
Universal Turing Machine, Countable Sets 
Section
4.2 
11 
Th
10/13 
Undecidability
of A_TM 
Section
4.2 

Tu
10/18 
Midterm
Exam 

12 
Th
10/20 
Reductions 
Section
5.1 
13 
Tu
10/25 
Definition
of P, EXP, Time hierarchy theorem 
Section
7.1, 7.2, 9.1 
14 
Th
10/27 
Definitions
of NP, Verifiers 
Section
7.3 
15 
Tu
11/1 
Polytime
Reductions, SAT, NPhardness and NPcompleteness 
Section
7.3 
16 
Th
11/3 
NPcompleteness
of Clique and Vertex Cover 
Section
7.5 
17 
Tu
11/8 
CookLevin
Theorem 
Section
7.4 

Th
11/10 
Midterm
Break, no class 

18 
Tu
11/15 
coNP, coNPhardness, NOSAT 

19 
Th
11/17 
RP, coRP, BPP 
Section
10.2 
20 
Tu
11/22 
Communication
complexity: definitions and examples 

21 
Th
11/24 
Protocol
trees, Deterministic communication complexity, 

22 
Tu
11/29 
Tight
analysis of EQ, Fooling sets 

23 
Th
12/1 
Disjointness, Reduction to Network Monitoring 

24 
Tu
12/6 
Nondeterministic
Communication Complexity. Nondeterminism and Covers 
Piazza
Piazza signup link: http://piazza.com/ubc.ca/winterterm12022/cpsc421
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.
Behaviour
Our classroom is a positive
space. If you are harassed or made
to feel uncomfortable, please bring it to the attention of the instructor
immediately. If it is the instructor who is the cause, please immediately bring
it to the attention of your academic advisor or the department’s associate head
for undergraduate affairs.
Course Links
Previous versions of this course
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