-
Lecture 1 (Jan 6): Introduction, Quicksort, Karger's Algorithm, Monte Carlo and Las Vegas Algorithms. (Ref: MR Chap 1)
-
Lecture 2 (Jan 11): Probability space, expectations and linearity thereof, Freivald's matrix multiplication algorithm, and examples of the probabilistic method. (Ref:
rough notes, MR Appendix C)
-
Lecture 3 (Jan 13): Conditional expectation, a simple branching process, balls and bins, Markov and Chebyshev, pairwise independence and reducing randomness for RP algorithms. (Ref: MR Chap 3)
-
Lecture 4 (Jan 20): Randomized Median Finding, Coupon Collector Problem. (Ref: MR Chap 3)
-
Lecture 5 (Jan 25): Poisson Approximation, Balls and Bins, Coupon Collector Problem, Random Graphs (Ref: MR Chap 3.6, MU Chapter 5)
-
Lecture 6 (Jan 27): Chernoff Bounds, Randomized Rounding (Ref: MR Chap 4)
-
-
Lecture 8 (Feb 1): Permutation routing on the hypercube, Fixed path routing and scheduling (Ref: MR 4.2,
very rough notes.)
-
Lecture 9 (Feb 3): The Probabilistic Method, Alterations, Independent Sets, Girth and Edges. (Ref: MR 5, MU 6)
-
Lecture 10 (Feb 8): Lovasz Local Lemma: symmetric and asymmetric versions, k-SAT satisfiability,, colourful independent sets (Ref: MR 5.5, MU 6.7)
-
Lecture 11 (Feb 10): Lovasz Local Lemma: packet routing in networks, Moser's constructive proof of LLL (Ref:
Rough notes,
Tao blog post)
-
Lecture 12 (Feb 15): Janson's Inequalities, Triangles in Random Graphs. (Ref: Google!
Here are some slides. )
-
Lecture 13 (Feb 19): Janson's Inequalities: Group Steiner Tree. (Ref:
Notes from CMU . Caution: this is not how we proved stuff in class.)
-
Lecture 14 (Feb 22): Markov Chains: Definition, a randomized algorithm for 2-SAT, classification of states, existence of stationary distribution, ergodicity theorem (Ref: MR 6.1-6.2, MU 7.1-7.3,
Rough notes)
-
Lecture 15 (Feb 24): Random walks on undirected graphs: definitions of hitting time and commute time, bounds and connection to effective resistance in electrical networks (Ref: MR 6.3-6.4, MU 7.4)
-
Lecture 16 (Mar 4): Cover times and MCMC: definition of cover times, bounds, log space algorithm for connectivity, polynomial length universal traversal sequences, motivation for MCMC, reduction from approximate sampling to approximate counting (Ref: MR 6.5, 11.1, MU 10.3-10.4,
Rough notes)
-
Lecture 17 (Mar 7): Coupling: definition of total variation distance, mixing time, and coupling between distributions, the coupling lemma, bounding mixing times for lazy random walk on cycle and hypercube (Ref: MU 11,
Rough notes,
lecture on coupling by David Levin)
-
Lecture 18 (Mar 9): More on bounding mixing time: sampling random spanning trees and (4Δ +1)-colorings and coupling-based analysis, spectral methods, conductance and canonical paths (Ref: MU 11.5, MR 11.3,
Rough notes)
-
Lecture 19 (Mar 14): A Markov chain for uniformly sampling matchings, analysis using canonical paths. Martingales: definition, motivation, stopping time. (Ref: MR 4.4.1-4.4.2, MU 12.1-12.2,
Rough notes on martingales)
-
Lecture 20 (Mar 18): Martingales: stopping time theorem, Wald's equation, expected waiting time for patterns in coin tosses, Doob's martingales, Azuma's inequality (Ref: MR 4.4.3-4.4.4, MU 12.2-12.5,
Rough notes on martingales)
-
Lecture 21 (Mar 21): Azuma's inequality in action: stochastic bin packing, number of empty bins, chromatic number in random graphs. Distributed algorithms: Synchronized Byzantine consensus, impossibility when at least n/3 faulty processors, Rabin's randomized consensus algorithm (Ref: MR 4.4.4, MU 12.5,
Arora's lecture notes for Rabin's algorithm)
-
-
Lecture 23 (Mar 28): Hash functions, Hash Tables, Fredman-Komlos-Szemeredi O(1)-query,O(s)-space double hashing. (MR 8.5)
-
Lecture 24 (Mar 30): Bloom Filters, Nearest Neighbor problem, Locally Sensitive Hashing. (MU 5.5)