**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 1^{st}.

·
Final
exam: Wednesday April 26^{th}, 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.