Lecture

Topics

Related
Files

0

Overview

[pdf]

1

Basics of Probability Theory

[pdf]

2

Verifying Polynomial Identities

[pdf]

3

Verifying Matrix Multiplication, MinCut

[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 (Derandomization, Sample and Modify)

[pdf]

19

Probabilistic Method (2^{nd} 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]
