
General Information



Tutor: Wisely Ku (古宗翰)
BayYuan
Hsu (許倍源)


thku @ cs.nthu.edu.tw
bayyuan @ cs.nthu.edu.tw


Meeting Times:


Mon 1520—1710, Thu 1410—1500




Announcement

Recent Events
Jan 05: HW 5 Deadline +
Solution
Jan 09: Final Exam
(Notes 21 to 23,
HW 4)

Dec 26:

Lecture Notes 17, 18, and 19 posted

Dec 29:

Homework 5 (optional) released


Course Materials
Lecture

Topics

Related
Files

0

Overview

[pdf]

1

Basics of Probability Theory

[pdf]

2

Verifying Polynomial Identities

[pdf]

3

Verifying Matrix Multiplication, Randomized MinCut

[pdf]

4

Binomial Random Variables

[pdf]

5

Geometric Random Variables, Conditional
Expectation

[pdf]

6

Coupon Collector Problem,
Analysis of Quicksort

[pdf]

7

Markov Inequality, Variance

[pdf]

8

Common Variance, Chebyshev Inequality

[pdf]

9

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]




17

Probabilistic Method (Introduction)

[pdf]

18

Probabilistic Method (Derandomization,
Sample and Modify)

[pdf]

19

Probabilistic Method (2^{nd} Moment, Conditional
Expectation Inequality)

[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]

Tutorial

Topics

Related
Files

1

Homework 1
Hints, Secretary Problem

[pdf]

2

Homework 1
Solutions, Homework 2 Hints

[ppt]

3

Homework 2
Solutions

[ppt]

Assignment

Topics

Related
Files

1

Random
Variables and Expectations

[pdf]

2

Moments and Deviations

[pdf]

3

Chernoff Bounds,
BallsandBins

[pdf]

4

Markov Chains

[pdf]

5

Probabilistic Methods

[pdf]

Teaching Plan
1

Events and Probability

Lecture 1 to Lecture 3

2

Discrete Random Variables and
Expectation

Lecture 4 to Lecture 6

3

Moments and Deviations

Lecture 7 to Lecture 9

4

Chernoff Bounds

Lecture 10 to Lecture 12

5

Balls, Bins, and Random Graphs

Lecture 13 to Lecture 15

6

The Probabilistic Method

Lecture 17 to Lecture 19

7

Markov Chain and Random Walk

Lecture 21 to Lecture 24

Last updated: December 29, 2011
