2013-14
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F13
Lecture Time: Monday,
Wednesday, Friday, 8:00am-9:00am
Lecture Room: DMP
301
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
·
Office hours: Friday 12-1pm
in X851
TA: Sharan Vaswani, sharanv@cs.ubc.ca
·
Office hours: Monday 2-3pm
in Demco Learning Center
Piazza
We
will use Piazza for course discussions, etc. Here is the signup link.
Assignments
Assignment 0 due Wednesday September 11th. Solutions.
Assignment 1 due Friday September 20th. Solutions.
Assignment 2 due Monday September 30th. Solutions.
Assignment 3 due Wednesday October 9th. Solutions.
Assignment 4 due Friday October 25th. Solutions.
Assignment 5 due Monday November 4th. Solutions.
Assignment 6 due Friday November 15th. Solutions.
Assignment 7 due Wednesday November 27th. Solutions.
Lectures
|
|
Date |
Topics |
Readings |
|
Review |
Sets, functions,
graphs, strings, logic, proofs, induction |
Chapter 0 |
|
|
1 |
W 9/4 |
What is computation? Start of finite automata |
Section
1.1 |
|
2 |
F 9/6 |
Definition
of finite automata |
Section
1.1 |
|
3 |
M 9/9 |
Nondeterministic
finite automata |
Section 1.2 |
|
4 |
W 9/11 |
Regular
expressions |
Section
1.3 |
|
5 |
F 9/13 |
The
pumping lemma |
Section
1.4 |
|
6 |
M 9/16 |
Proving
languages are not regular |
Section
1.4 |
|
7 |
F 9/20 |
Push down
automata |
Section
2.2 |
|
8 |
M 9/23 |
Context
free grammars |
Section
2.1 |
|
9 |
W 9/25 |
Parse
trees, Converting CFGs to PDAs |
Section
2.1 & 2.2 |
|
10 |
F 9/27 |
Turing
machines |
Section
3.1 & 3.3 |
|
11 |
M 9/30 |
Turing
machines |
Section
3.1 & 3.3 |
|
12 |
W 10/2 |
Variants
of Turing machines |
Section
3.2 |
|
13 |
F 10/4 |
Hierarchy
of languages, Start of halting problem |
Section
4.1 |
|
14 |
M 10/7 |
The
halting problem |
Section
4.2 |
|
15 |
W 10/9 |
Reductions |
Section
5.1 |
|
16 |
F 10/11 |
Self-replication |
Section
6.1 |
|
17 |
W 10/16 |
Midterm
Exam |
|
|
18 |
F 10/18 |
Definition
of P, EXP |
Section
7.1, 7.2 |
|
19 |
M 10/21 |
Time
hierarchy theorem |
Section
9.1 |
|
20 |
W 10/23 |
Definition
of NP |
Section
7.3 |
|
21 |
F 10/25 |
Reductions,
NP-hardness and NP-completeness |
Section
7.4 |
|
22 |
M 10/28 |
Cook-Levin
Theorem |
Section
7.4 |
|
23 |
W 10/30 |
NP-completeness
of 3SAT and Clique |
Section
7.5 |
|
24 |
F 11/1 |
NP-completeness
of Vertex Cover and Hamilton Path |
Section
7.5 |
|
25 |
M 11/4 |
coNP |
|
|
26 |
W 11/6 |
RP, coRP, BPP, ZPP |
Section
10.2, Arora-Barak 7 |
|
27 |
F 11/8 |
Error
reduction in BPP. Circuits for BPP algorithms. |
|
|
28 |
W 11/13 |
Communication
complexity: definitions and examples |
|
|
29 |
F 11/15 |
Rectangles
and fooling sets |
|
|
30 |
M 11/18 |
Disjointness and its applications |
|
|
31 |
W 11/20 |
Nondeterminism and covers |
|
|
32 |
F 11/22 |
Relating
determinism and nondeterminism |
|
|
33 |
M 11/25 |
Randomized
communication complexity |
|
|
34 |
W 11/27 |
Universal
hashing and the Equality function |
|
|
35 |
F 11/29 |
Quantum
pseudo-telepathy |
Midterm Exam
Wednesday
October 16th, in-class from 8am-8:50am. Solutions.
·
Material
covered: Lectures 1-16.
·
Last year’s CPSC 421 midterm
·
Practice 3, Solutions 3.
We did not discuss ambiguous grammars or non-context-free languages.
·
Practice 4.
We did not discuss non-context-free languages.
·
Practice
5. We did not discuss equivalence relations on DFA states.
Final Exam
Thursday
December 12th, 8:30-11:00am in DMP 110
·
Material
covered: Much more emphasis on the material after the midterm;
little emphasis on automata. But, no
quantum stuff on final.
·
Last year’s CPSC 421 final.
Solutions.
o
Not covered this year: Question 1.3, 1.8, 2(c), 5.
o
Solution 1b is wrong.
o
Question 10 is not relevant. We did not define
“strongly NP-complete”.
o
Unlike our final, this one has no questions at all
about NP.
o
Question 1-3: We did not discuss the Myhill-Nerode theorem.
o
Question 7: We did not discuss Subset-Sum (but it is
in the textbook Section 7.5).
Course Links
Previous versions of this course
·
Fall
2008, Prof. Greenstreet
Related courses at UBC
·
CPSC 506 “Complexity
of Computation”, Fall 2012
·
CPSC
506 “Complexity of Computation”, Fall 2010
·
CPSC 506
“Complexity of Computation”, Fall 2005
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