2021-22
Winter Term 1
General Information
Lecture Time: Monday,
Wednesday, Friday, 2:00pm-3:00pm
Location: 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.
https://www2.gov.bc.ca/gov/content/covid-19/info/restrictions
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.
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,
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
Hashing
·
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
Midterm
There will be one midterm,
on Monday October 18th, 7-8:30pm. If necessary, an online version
will be available. Details TBD.
Resources
·
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.