202324
Winter Term 1
General Information
Lecture Time: Mon Wed Fri,
2pm3pm
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 kpermutation, 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 
Inclass 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 
Inclass 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 
Inclass quiz #3 


27 
M 11/20 
Streaming,
the Majority problem, the BoyerMoore algorithm 
Sec 13.1,
13.2 
28 
W 11/22 
Frequency
estimation, CountMin 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 8^{th}.
·
Section
A: Wed 1011am, DMP 101. TA: Emily.
·
Section
B: Wed 910am, DMP 101. TA: Victor.
·
Section
D: Fri 11am12pm, 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, divideandconquer 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 202122 Term 2.