CPSC 436R: Introduction to Randomized Algorithms
2023-24
Winter Term 1
General Information
Lecture Time: Mon Wed Fri,
2pm-3pm
Location: DMP 301
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
TAs:
·
Emily Gong, gongz@student.ubc.ca
·
Victor Sanches Portella, victorsp@cs.ubc.ca
·
Yennis Ye, yxyapp18@student.ubc.ca
|
Nick |
Emily |
Victor |
Yennis |
|
|
|
|
|
Summary description
The
study of randomness in computation and in the design of algorithms. Topics
include probabilistic tools, expectation bounds, balls and bins, concentration bounds,
streaming algorithms, graph algorithms, data structures, hashing, and privacy.
Syllabus
https://www.cs.ubc.ca/~nickhar/F23/Syllabus.html
Lectures (topics may be slightly revised as the term unfolds)
The textbook
is basically a transcript of the lectures!
|
|
Date |
Topics |
Textbook |
|
1 |
W 9/6 |
Introduction,
background. Testing if a vector is zero. |
Sec 1.1 |
|
2 |
F 9/8 |
Decision
problems, RP, coRP, BPP, Amplification |
Sec 1.2
& 1.3 |
|
3 |
M 9/11 |
Generating
random integers |
Sec 2.1 |
|
4 |
W 9/13 |
Rejection
sampling, Geometric RVs, Generating a biased bit |
Sec 2.1,
2.2 |
|
5 |
F 9/15 |
Sampling
categorical distributions, and continuous RVs. Von Neumann’s algorithm. |
Sec 2.3,
2.4 |
|
6 |
M 9/18 Drop without W |
Sampling
a k-permutation, Durstenfeld’s algorithm |
Sec 3.1 |
|
7 |
W 9/20 |
Sampling:
With, Without replacement, Bernoulli. Partitioning. |
Sec 3.2,
3.3 |
|
8 |
F 9/22 |
Expectation:
Decomposition into indicators, Polling |
Sec 4.1,
4.2, 4.3 |
|
9 |
M 9/25 |
Expectation:
Polling without replacement |
Sec 4.3,
5.1 |
|
10 |
W 9/27 |
Recursion:
Faster sampling from a categorical distribution |
Sec 5.1.1 |
|
F 9/29 |
In-class quiz #1 |
|
|
|
M 10/2 |
No class:
National Day for Truth and Reconciliation |
|
|
|
11 |
W 10/4 |
Recursion:
QuickSelect |
Sec 5.2 |
|
12 |
F 10/6 |
Recursion:
QuickSort |
Sec 5.3 |
|
M 10/9 |
No class:
Thanksgiving |
|
|
|
13 |
W 10/11 |
Skip
Lists: Definition, Search Algorithm |
Sec 6.1,
6.2 |
|
14 |
Th 10/12 |
Skip
Lists: Analysis of Search, Delete, Insert |
Sec 6.3,
6.4, 6.5 |
|
15 |
F 10/13 |
Balls and
Bins: Birthday Paradox, Number of empty bins |
Sec 7.1,
7.2, 7.3 |
|
16 |
M 10/16 |
Balls and
Bins: Avoiding empty servers, Better of two choices |
Sec 7.4 |
|
17 |
W 10/18 |
Balls and
Bins: Load on heaviest bin |
Sec 7.5,
7.6 |
|
18 |
F 10/20 |
Ludicrous
load balancing, Markov’s inequality |
Sec 8.1,
8.2, 8.3 |
|
M 10/23 |
In-class quiz #2 |
|
|
|
19 |
W 10/25 |
Concentration,
Chernoff bound |
Sec 9.1,
9.2 |
|
20 |
F 10/27 |
Hoeffding bound, Chernoff vs Hoeffding |
Sec 9.2,
9.3, 9.4 |
|
21 |
M 10/30 |
Ratio of
loads in load balancing, Distinguishing Coins |
Sec 10.1,
11.1 |
|
22 |
W 11/1 |
The
median estimator |
Sec 9.5 |
|
23 |
F 11/3 |
Various
hash functions, Set Similarity |
Sec 12.1,
12.2 |
|
24 |
M 11/6 |
Basic MinHash |
Sec 12.2 |
|
25 |
W 11/8 |
Improved MinHash, Basic Bloom Filters |
Sec 12.4 |
|
26 |
F 11/10 |
Bloom
Filters |
Sec 12.4 |
|
|
M 11/13 |
No class:
Remembrance Day |
|
|
W 11/15 |
No class:
Midterm Break |
|
|
|
F 11/17 |
In-class quiz #3 |
|
|
|
27 |
M 11/20 |
Streaming,
the Majority problem, the Boyer-Moore algorithm |
Sec 13.1,
13.2 |
|
28 |
W 11/22 |
Frequency
estimation, Count-Min Sketch |
Sec 13.4 |
|
29 |
F 11/24 |
Distinct
elements problem |
Sec 13.7 |
|
30 |
M 11/27 |
Distinct elements
problem |
Sec 13.7 |
|
31 |
W 11/29 |
Strongly
universal hashing, linear hashing |
Sec 14.1 |
|
32 |
F 12/1 |
Proof for
linear hashing, Application to the Counting Filter |
Sec
14.1, 15.2 |
|
33 |
M 12/4 |
Perfect
hashing |
Sec 15.4 |
|
34 |
W 12/6 |
HyperLogLog |
|
Assignments
|
|
Date
handed out |
Date due (at 11:59PM) |
Date
graded by |
|
1 |
W 9/6 |
F 9/15 |
Tu 9/19 |
|
2 |
F 9/15 |
Sa 9/23 |
W 9/27 |
|
3 |
F 10/6 |
Sa 10/14 |
Th 10/19 |
|
4 |
F 11/3 |
Sa 11/11 |
W 11/15 |
|
5 |
M 11/27 |
Mo 12/4 |
F 12/8 |
Tutorial Sections
No tutorials on Sept 6th
or Sept 8th.
·
Section
A: Wed 10-11am, DMP 101. TA: Emily.
·
Section
B: Wed 9-10am, DMP 101. TA: Victor.
·
Section
D: Fri 11am-12pm, ICCS X350. TA: Yennis.
Prerequisites
·
logic,
proofs, summations, binary representation and modular arithmetic from CPSC 121
·
data
structures, sorting and searching, asymptotic notation, trees and graphs from
CPSC 221
·
algorithm
analysis, divide-and-conquer algorithms, graph searching algorithms, and
asymptotic notation from CPSC 320
·
probability
o
Ideal: MATH 302 or STAT 302
o
Also good: MATH 318
o
Rudimentary: previous students
have succeeded with this background, but you may need to extra effort to catch
up.
§ STAT 200: this does not emphasize rigor and only has a brief
coverage of probability.
§ STAT 251: this more probability than STAT 200, but still focuses on
calculations in applied scenarios.
o
Above and beyond: MATH 418. A deeper
understanding of probability is always useful, and this is what MATH 418
provides. However, that course covers fundamentals at a very abstract level,
whereas CPSC 436R focuses on algorithmic applications which do not require that
level of abstraction.
Resources
· Textbook
Draft: N. Harvey “A first course on
randomized algorithms”.
Other courses
CPSC 536N “Randomized Algorithms”,
taught in 2021-22 Term 2.