Lecture schedule
| Date | Lecture | References | Misc |
|---|---|---|---|
|
Lecture #1
Mon 31/07 |
Introduction to the course; admin details; outline of the course contents |
|
discussion forum |
|
Lecture #2
Wed 02/08 |
Perfect matchings in bipartite graphs and polynomial identity testing; DeMillo-Lipton-Schwartz-Zippel lemma and a simple randomized algorithm |
|
|
|
Lecture #3
Thu 03/08 |
Basic discrete probability - sample spaces, events, conditional probability; proof of the DeMillo-Lipton-Schwartz-Zippel lemma |
|
|
|
Lecture #4
Fri 03/08 |
Verifying matrix multiplication - Frievald's algorithm; Mincut in graphs - outline of Karger's algorithm |
|
|
|
Lecture #5
Mon 07/08 |
Karger's algorithm for mincut and its analysis; Maxcut in graphs - random variables and expectation |
|
|
|
Lecture #6
Wed 09/08 |
Randomized maxcut - random variables, expectation, pairwise independence; derandomizing maxcut using pairwise independence |
|
|
|
Lecture #7
Thu 10/08 |
Method of conditional expectations - greedy algorithm for maxcut; randomized quicksort - outline |
|
|
|
Lecture #8
Fri 11/08 |
Analysis of quicksort; Binomial and geometric random variables and their expectation; Analyzing the coupon collector problem using geometric random variables |
|
Read the corresponding sections for the proofs and additional material |
|
Lecture #9
Mon 14/08 |
Markov's inequality and a better analysis of quicksort; Variance of random variables - examples, binomial and geometric random variables |
|
|
|
Lecture #10
Wed 16/08 |
Chebyshev's inequality; randomness-efficient error reduction - construction of pairwise independent strings from finite fields |
|
|
|
Lecture #11
Thu 17/08 |
Construction of pairwise independent strings from finite fields; statements of the Chernoff-Hoeffding bounds |
|
|
|
Lecture #12
Fri 18/08 |
Chernoff-Hoeffding bounds - amplifying success probability of two-sided error algorithms; outline of the proof of the Chernoff bounds |
|
Problem set 1 released |
|
Lecture #13
Mon 21/08 |
Balls and bins - birthday problem; upper bound on maximum load; |
|
|
|
Lecture #14
Wed 23/08 |
Poisson approximation of balls and bins; properties of Poisson random variables |
|
|
|
Lecture #15
Thu 24/08 |
Poisson approximation of balls and bins - lower bound for maximum load; static dictionaries and Bloom filters |
|
|
|
Lecture #16
Fri 25/08 |
Bloom filters - analysis of the false positive probability; definitions of \( k\)-universal and \( k\)-wise indepedent hash families |
|
|
|
Lecture #17
Mon 28/08 |
Universal hash families - definition and properties; static and dynamic dictionary with 2-universal hash families; explicit constructions |
|
|
|
Lecture #18
Wed 30/08 |
Universal hash families - explicit constructions; Fredman-Komlos-Szemeredi (FKS) hashing; bitprobe model |
|
|
|
Lecture #19
Thu 31/08 |
Bitprobe model - static dictionaries with single probes; |
|
|
|
Tutorial #1
Fri 01/09 |
Discussion of Problem set 1
|
|
|
|
Lecture #20
Mon 04/09 |
Analysis of open addressing with linear probing |
|
|
|
Lecture #21
Wed 06/09 |
Analysis of open addressing with linear probing (contd); Cuckoo hashing - cuckoo graphs and their properties |
|
|
|
Lecture #22
Thu 07/09 |
Bounding the time for insertion in Cuckoo hashing; Properties of random graphs in analyzing the insertion time |
|
|
|
Lecture #23
Fri 08/09 |
Cuckoo hashing (contd.) - bounds on the size of the connected components and other properties |
|
|
|
Lecture #24
Mon 11/09 |
Online algorithms - competitive ratio; deterministic paging algorithms - LRU, and lower bound |
|
|
|
Lecture #25
Wed 13/09 |
Randomized paging against an oblivious adversary - Marker algorithm and analysis |
|
|
|
Lecture #26
Thu 14/09 |
Yao's minimax principle |
|
|
|
Lecture #27
Fri 15/09 |
Lower bound for online paging using Yao's minimax principle; online bipartite matching |
|
|
|
Quiz #1
Sat 16/09 |
Mid-semester exam based on Lectures 1 to 23
|
|
|
|
Lecture #28
Wed 20/09 |
Discussion of midsem; Online bipartite matching - LP formulation of maximum matching problem |
||
|
Lecture #29
Thu 21/09 |
Online matching - primal-dual analysis of greedy algorithm; fractional matching - waterlevel algorithm |
||
|
Lecture #30
Fri 22/09 |
Online fractional matching - primal-dual analysis of the waterlevel algorithm |
||
|
Lecture #31
Mon 25/09 |
Online matching - RANKING algorithm; primal-dual analysis |
|
|
|
Lecture #32
Wed 27/09 |
Online decisions with experts - the weighted majority algorithm |
|
|
|
Lecture #33
Wed 04/10 |
The multiplicative weights update algorithm |
|
|
|
Lecture #34
Thu 05/10 |
Learning a linear classifier - Winnow algorithm; analysis using the MWU method; 2-SAT vs 3-SAT |
|
|
|
Lecture #35
Fri 06/10 |
Randomized 2-SAT; Markov chains - definitions and examples |
|
|
|
Lecture #36
Mon 09/10 |
Randomized 3-SAT -Schoening's algorithm |
|
|
|
Lecture #37
Fri 13/10 |
Stationary distributions and other properties of Markov chains; Random walks on graphs |
|
|
|
Lecture #38
Mon 16/10 |
FPRAS for #-DNF - Karp's algorithm |
|
|
|
Lecture #39
Wed 18/10 |
From SAT to an FPRAS for #-SAT |
|
|
|
Lecture #40
Thu 19/10 |
Sampling and counting - FPAUS \(\Rightarrow \) FPRAS for independent sets |
|
|
|
Lecture #41
Fri 20/10 |
Sampling and counting - FPAUS \(\Rightarrow \) FPRAS for independent sets (contd.) |
|
|
|
Lecture #42
Wed 25/10 |
Monomer-dimer problem, and approximating the number of perfect matchings |
|
|
|
Lecture #43
Thu 26/10 |
Approximating the number of perfect matchings; Metropolis algorithm |
|
|
|
Lecture #44
Fri 27/10 |
Mixing time of Markov chains; Coupling lemma and applications |
|
|
|
Lecture #45
Mon 30/10 |
Coupling lemma - bounding the mixing time of Markov chains |
|
|
|
Lecture #46
Wed 1/11 |
Canonical paths - Markov chain on the boolean hypercube and its analysis |
|
|
|
Lecture #47
Thu 2/11 |
Canonical paths - Mixing time of Markov chains on matchings |
|