|
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 Collection, Quick Sort)
|
[pdf]
|
|
7
|
Moments and Deviations (Markov Inequality, Variance)
|
[pdf]
|
|
8
|
Moments and Deviations (Common Variance, Chebyshev
Inequality)
|
[pdf]
|
|
9
|
Moments and Deviations (Randomized Median)
|
[pdf]
|
|
10
|
Chernoff Bounds
(Introduction)
|
[pdf]
|
|
11
|
Chernoff Bounds
(Application)
|
[pdf]
|
|
12
|
Chernoff Bounds
(More Applications)
|
[pdf]
|
|
13
|
Balls and Bins Model (Introduction)
|
[pdf]
|
|
14
|
Balls and Bins Model (Poisson Approximation)
|
[pdf]
|
|
15
|
Balls and Bins Model (Hashing)
|
[pdf]
|
|
16
|
Balls and Bins Model (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, Stationary Distribution)
|
[pdf]
|
|
24
|
Markov Chains (Parrondo’s
Paradox)
|
[pdf]
|
