CS 5314 Randomized Algorithms (Fall 2015)

General Information
Lecturer: Wing-Kai Hon
wkhon@cs
Tutors: Simon Chang
simonC @ cs.nthu.edu.tw
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%

 

Feb 22: 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: February 22, 2018