|
|
|
General Information
|
|
|
|
|
|
Tutor: Wisely Ku (古宗翰)
Bay-Yuan
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 Min-Cut
|
[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
(Balls-and-Bins 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 (De-randomization,
Sample and Modify)
|
[pdf]
|
|
19
|
Probabilistic Method (2nd 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,
Balls-and-Bins
|
[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
|