|
General Information
|
|
Lecturer:
|
Wing-Kai Hon
|
|
wkhon@cs
|
|
|
|
|
Tutors:
|
Chris Tan, Rick Wu
|
|
|
ddtddt1225 @ hotmail.com, wudaiyang @ gmail.com
|
|
|
|
|
Meeting Time:
|
|
Tue 1010--1200, Thu 1010--1100
|
|
|
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%
|
|
Sep 16:
|
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 Min-Cut
|
[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
|
Balls-and-Bins Model
|
Lecture 13 to Lecture 15
|
|
6
|
Probabilistic Methods
|
Lecture 17 to Lecture 19
|
|
7
|
Markov Chains
|
Lecture 21 to Lecture 24
|
Last updated: September 13, 2015
|