|
Lecture
|
Topics
|
Related
Files
|
|
0
|
Overview
|
[pdf]
|
|
1
|
Basics of Probability Theory
|
[pdf]
|
|
2
|
Verifying Polynomial Identities
|
[pdf]
|
|
3
|
Verifying Matrix Multiplication, Min-Cut
|
[pdf]
|
|
4
|
RVs and Expectations (Basics, Binomial RV)
|
[pdf]
|
|
5
|
RVs and Expectations (Geometric RV, Conditional Expectation)
|
[pdf]
|
|
6
|
RVs and Expectations (Coupon Collector, Quicksort)
|
[pdf]
|
|
7
|
Moments and Deviations (Markov, Variance)
|
[pdf]
|
|
8
|
Moments and Deviations (Common Variance, Chebyshev)
|
[pdf]
|
|
9
|
Moments and Deviations (Randomized Median)
|
[pdf]
|
|
10
|
Chernoff Bounds
(Introduction)
|
[pdf]
|
|
11
|
Chernoff Bounds
(Application)
|
[pdf]
|
|
12
|
Chernoff Bounds
(More Application)
|
[pdf]
|
|
13
|
Balls, Bins, and Random Graphs (Balls-and-Bins Model)
|
[pdf]
|
|
14
|
Balls, Bins, and Random Graphs (Poisson Approximation)
|
[pdf]
|
|
15
|
Balls, Bins, and Random Graphs (Hashing)
|
[pdf]
|
|
16
|
Balls, Bins, and Random Graphs (Random Graphs)
|
[pdf]
|
|
17
|
Probabilistic Method (Introduction)
|
[pdf]
|
|
18
|
Probabilistic Method (De-randomization, Sample and Modify)
|
[pdf]
|
|
19
|
Probabilistic Method
(2nd Moment, Conditional Expectation Inequality)
|
[pdf]
|
|
20
|
Probabilistic Method
(Lovasz Local Lemma)
|
[pdf]
|
|
21
|
Markov Chains
(Definition, Solving 2SAT)
|
[pdf]
|
|
22
|
Markov Chains (Solving
3SAT)
|
[pdf]
|
|
23
|
Markov Chains
(Gambler’s Ruin, Random Walk)
|
[pdf]
|
|
24
|
Markov Chains (Parrondo’s Paradox)
|
[pdf]
|
