2025-26
Winter Term 1
General Information
Lecture Time: Mon, Wed 11am-12:30pm
Location: SWNG
206
Instructor: Prof. Nick
Harvey, X851,
nickhar@cs.ubc.ca
TAs: Yabing Qi
Discussions
Please sign up for Piazza: https://piazza.com/ubc.ca/winterterm12025/cpsc536n
Topics
Primarily from Book 2; some from Book 1.
Possible Additional Topics
· Locality
Sensitive Hashing
· Online
Learning: Randomized Weighted Majority, Bandits
· Derandomization: Pessimistic Estimators
· Random
Matrices
· Metric
Spaces: Probabilistic Embedding into Trees
· Online
Matching
Grading
·
(40%)
Assignments
o 4 Assignments: problem
solving, theorem-proof type
·
(10%)
Class participation
o Self-introduction
o In-class responses to lecture materials
o Responses to assigned readings
o
·
(50%)
Project
o (~2%) List of topics that you are
interested in
o (~8%) Chosen topic and proposed outline
o (~40%) Final project
Lectures
|
# |
Date |
Topics |
Pre-class Reading |
Resources for Lecture Material |
|
1 |
W 9/3 |
Set Cover |
|
Book 2, Ch 20 |
|
2 |
M 9/8 |
Chernoff Bounds & Congestion Minimization |
|
Book 2, 21.1 and 22.2 |
|
3 |
W 9/10 |
Hoeffding Bound, Error Correcting Codes |
GRS
Pages 3-13 |
Book 2, 22.3 |
|
4 |
M 9/15 |
|
Proof of Chernoff Bound |
|
|
5 |
W 9/17 |
|
|
|
|
6 |
M 9/22 |
|
|
|
|
7 |
W 9/24 |
|
|
|
|
8 |
M 9/29 |
|
|
|
|
10 |
W 10/1 |
|
|
|
|
11 |
M 10/6 |
|
|
|
|
12 |
W 10/8 |
|
|
|
|
|
M 10/13 |
HOLIDAY |
|
|
|
13 |
W 10/15 |
|
|
|
|
14 |
M 10/20 |
|
|
|
|
15 |
W 10/22 |
|
|
|
|
16 |
M 10/27 |
|
|
|
|
17 |
W 10/29 |
|
|
|
|
18 |
M 11/3 |
|
|
|
|
19 |
W 11/5 |
|
|
|
|
|
M 10/10 |
MIDTERM |
|
|
|
|
W 10/12 |
BREAK |
|
|
|
20 |
M 11/17 |
|
|
|
|
21 |
W 11/19 |
|
|
|
|
22 |
M 11/24 |
|
|
|
|
23 |
W 11/26 |
|
|
|
|
24 |
M 12/1 |
|
|
|
|
25 |
W 12/3 |
|
|
|
Auditors and Undergraduates
Auditors welcome. Graduate students who wish to audit should
file a graduate
registration form with the CS front
office. Undergraduate students who wish to take the course for credit should
request permission from the instructor and file an undergraduate
registration form to the CS front
office.
Related Offerings