2022-23
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F22
Lecture Time: Tuesday
Thursday, 12:30pm-2:00pm
Lecture Room: UBC
Life Building 2302
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office Hours: Monday 12-1pm,
ICCS x851
TAs:
·
Ryan Liu
o Office hours: Wednesday 3-4pm
·
Hassan Mallahzadeh
o Office hours: Thursdays 9:30-10:30am
·
Markus de Medeiros
o Office hours: Tuesdays 11am-12pm
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 18th, in class.
·
Final: Thursday December 15th, 12:00pm,
IBLC 182.
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
|
|
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
NFA-DFA, Regular languages & expressions |
Section
1.3, 1.4 |
|
4 |
Tu
9/20 |
Non-regular
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 |
Non-deterministic
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, NP-hardness and NP-completeness |
Section
7.3 |
|
16 |
Th
11/3 |
NP-completeness
of Clique and Vertex Cover |
Section
7.5 |
|
17 |
Tu
11/8 |
Cook-Levin
Theorem |
Section
7.4 |
|
|
Th
11/10 |
Midterm
Break, no class |
|
|
18 |
Tu
11/15 |
coNP, coNP-hardness, 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