CPSC 436R: Introduction to Randomized Algorithms

2022-23 Winter Term 2

General Information

Lecture Time: Mon Wed Fri, 11am-12pm
Location:
DMP 110

Instructor:

TAs:

·        Emily Gong, gongz@student.ubc.ca

·        Michael Liu, mfliu@cs.ubc.ca

·

All course activities will take place on Piazza, not on Canvas.

Syllabus

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.