2022-23
Winter Term 2
General Information
Lecture Time: Mon Wed Fri,
11am-12pm
Location: DMP 110
Instructor: Prof. Nicholas
Harvey, X851,
nickhar@cs.ubc.ca
TAs:
·
Emily Gong, gongz@student.ubc.ca
·
Michael Liu, mfliu@cs.ubc.ca
·
Victor Sanches Portella, victorsp@cs.ubc.ca
All course activities will take place on Piazza,
not on Canvas.
Syllabus
https://www.cs.ubc.ca/~nickhar/W23/Syllabus.html
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 spend time catching
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.
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.
List of topics
Basic Probabilistic Tools
·
How
to sample various random variables and random objects
·
Linearity
of Expectation
·
Balls
and Bins, and its numerous applications
Sorting and Searching
·
QuickSort, QuickSelect
Concentration Bounds
·
Markov
Bound, Chernoff Bound, Hoeffding Bound
·
Applications
in Statistics: AB Testing, CDF Estimation
Graph algorithms
·
Maximum
Cut, Minimum cut
Data structures
·
Skip
Lists, Bloom Filters, Set Similarity, Near Neighbors
Hashing
·
Universal
hash functions, Fingerprinting, Perfect hashing
Big-data algorithms
·
Heavy
Hitters, Count-Min Sketch, Distinct Element Estimation & HyperLogLog
Privacy and Secrecy
· Randomized response
·
Securely
computing the average
Exams
·
Midterm:
In-class, Wednesday March 1st.
·
Final
exam: Wednesday April 26th, 12-2:30pm
Resources
·
Textbook Draft: N. Harvey “A first course on
randomized algorithms”.
Other courses
CPSC 536N “Randomized Algorithms”,
taught in 2021-22 Term 2.