2025-26
Winter Term 2
General Information
Lecture Time: Mon Wed Fri, 3pm-4pm
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
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/W26/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 |
M 1/5 |
Introduction, background. Testing if a vector is zero. |
Sec 1.1 |
|
2 |
W 1/7 |
Decision problems, RP, coRP, BPP,
Amplification |
Sec 1.2 & 1.3 |
|
3 |
F 1/9 |
Generating random integers |
Sec 2.1 |
|
4 |
M 1/12 |
Rejection sampling, Geometric RVs, Generating a biased bit |
Sec 2.1, 2.2 |
|
5 |
W 1/14 |
Sampling categorical distributions, and continuous RVs. Von
Neumann’s algorithm. |
Sec 2.3, 2.4 |
|
6 |
F 1/16 Drop
without W |
Sampling a k-permutation, Durstenfeld’s
algorithm |
Sec 3.1 |
|
7 |
M 1/19 |
Sampling: With, Without replacement, Bernoulli. Partitioning. |
Sec 3.2, 3.3 |
|
8 |
W 1/21 |
Expectation: Decomposition into indicators, Polling |
Sec 4.1, 4.2, 4.3 |
|
9 |
F 1/23 |
Expectation: Polling without replacement |
Sec 4.3, 5.1 |
|
10 |
M 1/26 |
Recursion: Faster sampling from a categorical distribution |
Sec 5.1.1 |
|
W 1/28 |
In-class quiz #1 |
|
|
|
11 |
F 1/30 |
Recursion: QuickSelect |
Sec 5.2 |
|
12 |
M 2/2 |
Recursion: QuickSort |
Sec 5.3 |
|
13 |
W 2/4 |
Skip Lists: Definition, Search Algorithm |
Sec 6.1, 6.2 |
|
14 |
F 2/6 |
Skip Lists: Analysis of Search, Delete, Insert |
Sec 6.3, 6.4, 6.5 |
|
15 |
M 2/9 |
Balls and Bins: Birthday Paradox, Number of empty bins |
Sec 7.1, 7.2, 7.3 |
|
16 |
W 2/11 |
Balls and Bins: Avoiding empty servers, Better
of two choices |
Sec 7.4 |
|
17 |
F 2/13 |
Balls and Bins: Load on heaviest bin |
Sec 7.5, 7.6 |
|
|
|
Midterm Break |
|
|
18 |
M 2/23 |
Ludicrous load balancing, Markov’s inequality |
Sec 8.1, 8.2, 8.3 |
|
W 2/25 |
In-class quiz #2 |
|
|
|
19 |
F 2/27 |
Concentration, Chernoff bound |
Sec 9.1, 9.2 |
|
20 |
M 3/2 |
Hoeffding bound, Chernoff vs Hoeffding |
Sec 9.2, 9.3, 9.4 |
|
21 |
W 3/4 |
Ratio of loads in load balancing, Distinguishing Coins |
Sec 10.1, 11.1 |
|
22 |
F 3/6 |
The median estimator |
Sec 9.5 |
|
23 |
M 3/9 |
Various hash functions, Set Similarity |
Sec 12.1, 12.2 |
|
24 |
W 3/11 |
Basic MinHash |
Sec 12.2 |
|
25 |
F 3/13 |
Improved MinHash, Basic Bloom Filters |
Sec 12.4 |
|
26 |
M 3/16 |
Bloom Filters |
Sec 12.4 |
|
W 3/18 |
In-class quiz #3 |
|
|
|
27 |
F 3/20 |
Streaming, the Majority problem, the Boyer-Moore algorithm |
Sec 13.1, 13.2 |
|
28 |
M 3/23 |
Frequency estimation, Count-Min Sketch |
Sec 13.4 |
|
29 |
W 3/25 |
Distinct elements problem |
Sec 13.7 |
|
30 |
F 3/27 |
Distinct elements problem |
Sec 13.7 |
|
31 |
M 3/30 |
Strongly universal hashing, linear hashing |
Sec 14.1 |
|
32 |
W 4/1 |
Proof for linear hashing, Application to the Counting Filter |
Sec
14.1, 15.2 |
|
|
|
Easter Break |
|
|
33 |
W 4/8 |
Perfect hashing |
Sec 15.4 |
|
34 |
F 4/10 |
HyperLogLog |
|
Assignments
|
|
Date handed out |
Date due (at 11:59PM) |
|
1 |
M 1/5 |
1/14 |
|
2 |
W 1/14 |
1/22 |
|
3 |
F 2/2 |
2/10 |
|
4 |
M 3/9 |
3/17 |
|
5 |
F 3/27 |
4/8 |
The aim is that grading happens within 4
days.
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 2025-26 Term 1.