CS 5314 Randomized Algorithms (Fall 2012)

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