General Information

Lecturer:

WingKai Hon


wkhon@cs



Tutors:

Simon Chang


simonC @ cs.nthu.edu.tw



Meeting Time:


Tue 10101200, Thu 10101100



Announcements

Welcome to the Class!

Textbook & References
1. Probability and Computing (Textbook)
2. Randomized Algorithms
3. Probabilistic Methods

Scoring Method
5 Assignments (4 * 12.5% + 5%)
3 Exams (3 * 15%)

Total = 100%

Feb 22:

Lecture Notes is ready


Course Materials

Lecture

Topics

Related Files

1

Events and Probability

[pdf]

2

Verifying Polynomial Identities

[pdf]

3

Verifying Matrix Multiplication, Randomized MinCut

[pdf]

4

Binomial Random Variable

[pdf]

5

Geometric Random Variable

[pdf]

6

Coupon Collection

[pdf]

7

Markov Inequality, Variance

[pdf]

8

Common Variance, Chebyshev Inequality

[pdf]

9

Randomized Median

[pdf]

10

Chernoff Bounds

[pdf]

11

Chernoff Bounds

[pdf]

12

Chernoff Bounds

[pdf]

13

Balls and Bins

[pdf]

14

Balls and Bins

[pdf]

15

Balls and Bins (skipped)

[pdf]

16

Balls and Bins (skipped)

[pdf]

17

Probabilistic Methods

[pdf]

18

Probabilistic Methods

[pdf]

19

Probabilistic Methods

[pdf]

20

Probabilistic Methods (skipped)

[pdf]

21

Markov Chains

[pdf]

22

Markov Chains

[pdf]

23

Markov Chains

[pdf]

24

Markov Chains

[pdf]

Teaching Plan

1

Events and Probability

Lecture 01 to Lecture 03

2

Random Variables and Expectation

Lecture 04 to Lecture 06

3

Moments and Deviations

Lecture 07 to Lecture 09

4

Chernoff Bounds

Lecture 10 to Lecture 12

5

BallsandBins Model

Lecture 13 to Lecture 15

6

Probabilistic Methods

Lecture 17 to Lecture 19

7

Markov Chains

Lecture 21 to Lecture 24

Last updated: February 22, 2018
