|
General Information
|
|
Lecturer:
|
Wing-Kai Hon
|
|
wkhon @ cs
|
|
|
|
|
Tutors:
|
Jenny Liu, Chris Tan
|
|
|
hhliu @ cs, ddtddt1225 @ hotmail.com
|
|
|
|
|
Meeting Time:
|
|
Tue 1010--1200, Thu 1010--1100
|
|
|
Announcements
|
|
Quiz 3
Date: January 15, 2013 (2 hours)
Scope: Lectures 17--19, 21--23, HW 4
|
|
Textbook & References
1. Probability and Computing (Textbook)
2. Randomized Algorithms
3. Probabilistic Methods
|
|
Scoring Method
4 Assignments (3 * 16.67% + 5%)
3 Exams (3 * 15%)
--------------------------------------------------------
Total = 100%
|
|
Dec 10:
|
Lecture Notes 17, 18, and 19 posted
|
|
|
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: January 2, 2013
|