2014-15
Winter Term 2
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/W15
Lecture Time: Mondays &
Wednesdays, 11:00am-12:30pm
Lecture Room: ICCS 206
Instructor: Prof. Nicholas
Harvey, X851, nickhar@cs.ubc.ca
Office
Hours: Wednesdays 1-2:30pm, X851
TA: Bader Al-Ahmed, bader@ece.ubc.ca
Assignments
·
Assignment 4 Due Wednesday April 1st, in class.
Projects (New!)
Piazza
Lectures
|
|
Date |
Topics |
Notes |
|
1 |
M 1/5 |
Introduction,
Equality Testing |
|
|
2 |
W 1/7 |
Max Cut,
Markov Inequality, Amplification |
|
|
3 |
M 1/12 |
Chernoff
Bound, Balls and bins, Congestion minimization |
|
|
4 |
W 1/14 |
Congestion
minimization, Negative binomial distribution, QuickSort |
|
|
5 |
M 1/19 |
SkipNet |
|
|
6 |
W 1/21 |
Consistent
hashing, Leader election |
|
|
7 |
M 1/26 |
Johnson-Lindenstrauss
Dimensionality Reduction |
|
|
8 |
W 1/28 |
Fast
Johnson-Lindenstrauss Transform |
|
|
9 |
M 2/2 |
Streaming
Algorithms, Nearest Neighbors in High Dimensions |
|
|
10 |
W 2/4 |
Minimum Cuts by the Contraction Algorithm |
|
|
11 |
W 2/11 |
Graph Sparsifiers |
|
|
Midterm
break |
|
||
|
12 |
W 2/25 |
Derandomization:
Conditional Expectations, Pessimistic Estimators |
|
|
13 |
F 2/27 |
Pairwise
and k-wise Independence |
|
|
14 |
M 3/2 |
Streaming
Algorithms for the L2-norm |
|
|
15 |
W 3/4 |
Streaming
Algorithms for the Distinct Elements Problem |
|
|
16 |
M 3/9 |
Guest
lecture by Joel Friedman: Expanders and Superconcentrators |
|
|
17 |
W 3/11 |
Guest
lecture by Joel Friedman: Polynomial Identity Testing |
|
|
18 |
W 3/18 |
The
Lovasz Local Lemma |
|
|
19 |
W 3/25 |
An
Algorithmic Local Lemma |
|
|
20 |
M 3/30 |
Guest
lecture by David Kirkpatrick: Randomized Geometric Algorithms |
|
|
21 |
W 4/1 |
Guest
lecture by Mark Schmidt: Randomized Descent Methods |
|
|
Easter
Monday |
|
||
|
22 |
W 4/8 |
An
Algorithmic Local Lemma with Resampling Oracles |
Miscellaneous Notes
Notes on convexity inequalities
Past offerings of this course
·
U Waterloo CO 750, Winter 2011
Similar classes at other universities
·
Anna Karlin’s “Randomized
Algorithms and Probabilistic Analysis” at U Washington
·
Lap Chi Lau’s “Randomness and
Computation” at CUHK
·
Avrim Blum and Anupam Gupta’s “Randomized
Algorithms” at CMU