CPSC 436R: Introduction to Randomized Algorithms

2021-22 Winter Term 1

General Information

Lecture Time: Monday, Wednesday, Friday, 2:00pm-3:00pm
DMP 110

Instructor: Prof. Nicholas Harvey, X851, nickhar@cs.ubc.ca

TAs: Arsh Jhaj

Piazza: http://piazza.com/ubc.ca/winterterm12021/cpsc436r


Policies related to COVID-19 (as of Sept 3rd)

·        All lectures will be held in-person in DMP 110, unless the department directs otherwise.

·        All lectures will be recorded, and videos will be provided afterwards.

·        All office hours will be held on Zoom.

·        Health

o   Everyone is required to do a COVID-19 self assessment before coming to class each day. Coming to class while sick is a violation of the student code of conduct, and you will be asked to leave. You can do a self-assessment for COVID-19 symptoms here: https://bc.thrive.health/covid19/en

o   If you’re sick, it’s important that you stay home – no matter what you think you may be sick with (e.g., cold, flu, other). If you think you might have COVID-19 symptoms and/or have tested positive for COVID-19 and/or are required to quarantine, stay home!

·        Masks

o   Masks are mandatory, in accordance with the Public Health Officer’s orders.

o   Please do not eat in class. If you need to drink water/coffee/tea/etc., please keep your mask on between sips.

o   Some people cannot wear masks, for various valid reasons: anxiety, respiratory issues, etc. These policies are contradictory, and there is no easy resolution.

·        Seating arrangements

o   Please pick one area of the classroom and sit in the same area every time.

·        Vaccines

o   Vaccines are available to you, free (and possibly even on-campus). The higher the rate of vaccination in our community overall, the lower the chance of spreading this virus. You are an important part of the UBC community. Please arrange to get vaccinated if you have not already done so.

·        Ventilation

o   DMP 110 has MERV13 filters.



·        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, events, expectation, standard distributions, independence from STAT 200, STAT 203, STAT 241, STAT 251, STAT 302, MATH 302, MATH 318, or BIOL 300.


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.


Tentative list of topics (will likely be tweaked)

Basic Probabilistic Tools

·        Linearity of Expectation, Chernoff Bound, Pairwise Independence

·        Balls and Bins, and its numerous applications

Sorting and Searching

·        QuickSort, QuickSelect

Approximation Algorithms

·        Max Cut, Max 3SAT

Graph algorithms

·        Minimum cut

Data structures

·        Skip Lists, Bloom Filters, Set Similarity


·        Universal hash functions, Fingerprinting, Perfect hashing

Big-data algorithms

·        Heavy Hitters, Count-Min Sketch, Distinct Element Estimation (HyperLogLog)

Privacy and Secrecy

·        Securely computing the average

·        Randomized response



There will be one midterm, on Monday October 18th, 7-8:30pm. If necessary, an online version will be available. Details TBD.



·        Textbooks

o   N. Harvey A first course on randomized algorithms”. A book draft.

Other courses

CPSC 536N “Randomized Algorithms”, being taught in 2021-22 Term 2.