Lecture #1
Thu 16/01
|
Introduction to the course • Admin and logistics
|
|
Sign up on Ed Discussions
|
Lecture #2
Fri 17/01
|
Polynomials and perfect matchings • Probability spaces, events
|
- Section 1.1, 1.2 - Course notes
|
|
Lecture #3
Tue 21/01
|
DeMillo-Lipton-Schwartz-Zippel lemma • One-sided error algorithms and amplifying the success probability • Freivald's algorithm
|
- Sections 1.2, 1.3 - Course notes
|
|
Lecture #4
Wed 22/01
|
Mincut in graphs - Karger's algorithm
|
- Section 1.4 - Course notes
|
|
Lecture #5
Thu 23/01
|
Karger and Stein's improvement for mincut • The maxcut problem
|
- Sections 1.4, 2.1 - Course notes
|
Karger and Stein's paper
|
Lecture #6
Fri 24/01
|
Randomized algorithm for maxcut • Random variables and their properties - expectation, independence • Properties of the randomized algorithm for maxcut
|
- Section 2.1 - Course notes
|
|
Lecture #7
Tue 28/01
|
Maxcut - pairwise independence • Conditional expectations and derandomization
|
- Section 2.1 - Course notes
|
|
Lecture #8
Wed 29/01
|
Bernoulli, binomial, and geometric random variables and their properties
|
- Section 2.3 - Course notes
|
|
Lecture #9
Thu 30/01
|
Coupon collector problem - calculation of expectation • Randomized quicksort and its analysis
|
- Sections 2.2, 2.3.3 - Course notes
- Sections 2.4.1, 2.5 - [MU]
|
|
Lecture #10
Fri 31/01
|
Markov's inequality - analyzing quicksort using Markov's inequality • Statement of Chebyshev's inequality
|
- Section 3.1 - Course notes
|
PS1 released
|
Lecture #11
Tue 04/02
|
Chebyshev's inequality • Probability amplification using pairwise independent bits
|
- Section 3.2 - Course notes
|
|
Lecture #12
Wed 05/02
|
Chernoff-Hoefding bounds and applications • Outline of the proof
|
- Section 3.3 - Course notes
|
|
Lecture #13
Thu 06/02
|
Balls and bins - birthday problem, maximum load
|
- Section 4.1 - Course notes
- Sections 5.1, 5.2.1 - [MU]
|
|
Lecture #14
Fri 07/02
|
Balls and bins - maximum load and Poisson approximation
|
- Sections 4.2, 4.3 - Course notes
|
|
Lecture #15
Tue 11/02
|
Bloom filters
|
- Section 4.4 - Course notes
|
|
Lecture #16
Wed 12/02
|
Universal hash families and their properties - number of collisions, maximum load
|
- Section 5.1 - Course notes
|
|
Lecture #17
Thu 13/02
|
Explicit construction of 2-universal hash families • Near-universal hash families
|
- Section 5.1 - Course notes
|
Additional notes - Section 3.1 here
|
Lecture #18
Thu 14/02
|
Near-universal hash families - constructions • Perfect hashing - FKS algorithm
|
- Section 5.2 - Course notes
|
Additional notes - Section 3.1 here
|
Tutorial #1
Tue 18/02
|
Discussion of Problem set 1
|
|
|
Lecture #19
Wed 19/02
|
Open addressing - uniform probing
|
- Class notes and additional references on Ed
|
PS2 released
|
Lecture #20
Thu 20/02
|
Open addressing - linear probing
|
- Section 5.4 - Course notes
|
|
Lecture #21
Fri 21/02
|
Open addressing - linear probing (contd) • Cuckoo hashing
|
- Section 5.4 - Course notes
|
|
Lecture #22
Tue 25/02
|
Cuckoo hashing - algorithm and analysis
|
- Section 5.5 - Course notes
|
|
Lecture #23
Wed 26/02
|
Cuckoo hashing - analysis using random graphs (outline) • Locality-sensitive hashing
|
- Section 5.5 - Course notes
- Section 12.2 - Nick Harvey's book
|
|
Lecture #24
Thu 27/02
|
Locality-sensitive hashing - Jaccard similarity and minhashing
|
- Section 12.2 - Nick Harvey's book
|
|
Quiz #1
Tue 04/03
|
Mid-semester examination
|
|
|
Lecture #25
Wed 05/03
|
Online algorithms - model and examples • Bipartite matching - online greedy algorithm and lower bound
|
- Section 6.1 - Course notes
|
|
Lecture #26
Thu 06/03
|
Online paging - LRU and its competitive ratio • Lower bounds for deterministic paging
|
- Section 6.2.1 - Course notes
|
|
Lecture #27
Fri 07/03
|
Marker algorithm for online paging
|
- Section 6.2.2 - Course notes
|
|
Lecture #28
Tue 11/03
|
Yao's minimax principle and lower bounds for online paging
|
- Section 6.3 - Course notes
|
|
Lecture #29
Wed 12/03
|
Greedy matching revisited - primal dual analysis
|
- Section 6.4.1 - Course notes
|
|
Lecture #30
Thu 13/03
|
Online fractional matching - primal dual analysis
|
- Section 6.4.2 - Course notes
|
|
Lecture #31
Tue 18/03
|
Online fractional matching (contd) • RANKING - online bipartite matching
|
- Section 6.4.2, 6.4.3 - Course notes
|
|
Lecture #32
Wed 19/03
|
RANKING - analysis using primal-dual • Online predictions
|
- Section 6.5.1 - Course notes
|
|
Lecture #33
Thu 20/03
|
Online predictions with experts - weighted majority and randomized weighted majority
|
- Section 6.5 - Course notes
|
|
Lecture #34
Fri 21/03
|
Multiplicative weights update • Linear classification - Winnow algorithm as MWU
|
|
|
Lecture #35
Tue 25/03
|
Randomized 2-SAT - algorithm description and analysis
|
|
|
Lecture #36
Wed 26/03
|
Markov chains - definition, properties • Randomized 2-SAT as a Markov chain • Randomized 3-SAT - Schoening's algorithm
|
|
|
Lecture #37
Thu 27/03
|
Schoening's algorithm (contd) • Properties of Markov chains, stationary distributions, and the fundamental theorem - examples
|
|
|
Lecture #38
Fri 28/03
|
Random walks on graphs - cover times and reachability using random walks
|
|
|