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 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 (BallsandBins 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 (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, Random Walk)

[pdf]

24

Markov Chains (Parrondo’s Paradox)

[pdf]
