隨機演算法
Randomized Algorithms
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 隨機演算法 ED202（光復） 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 隨機演算法 ED202（光復） |
* 根據陽明交大上課時間表所列
使同學了解機率在演算法相關領域之應用. 並熟悉隨機演算法之設計及分析證明方法. This course will discuss how to design and analyze randomized algorithms.
機率,演算法 Prerequisites: Probability, Algorithms
無備註
Lectures
Homework 50% Midterm 20% Final project 30%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Basic discrete probability 2024-02-19(一),2024-02-22(四) 時數：[2024-02-19]蔡錫鈞(1.00) |
| 第 1 週 | Basic discrete probability 2024-02-19(一),2024-02-22(四) 時數：[2024-02-22]蔡錫鈞(2.00) |
| 第 2 週 | Randomized quicksort and Minimum cut 2024-02-26(一),2024-02-29(四) 時數：[2024-02-26]蔡錫鈞(1.00) |
| 第 2 週 | Randomized quicksort and Minimum cut 2024-02-26(一),2024-02-29(四) 時數：[2024-02-29]蔡錫鈞(2.00) |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem 2024-03-04(一),2024-03-07(四) 時數：[2024-03-04]蔡錫鈞(1.00) |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem 2024-03-04(一),2024-03-07(四) 時數：[2024-03-07]蔡錫鈞(2.00) |
| 第 4 週 | Chernoff and Hoeffding Bounds, 2024-03-11(一),2024-03-14(四) 時數：[2024-03-11]蔡錫鈞(1.00) |
| 第 4 週 | Chernoff and Hoeffding Bounds, 2024-03-11(一),2024-03-14(四) 時數：[2024-03-14]蔡錫鈞(2.00) |
| 第 5 週 | Balls, Bins, and Random Graphs 2024-03-18(一),2024-03-21(四) 時數：[2024-03-18]蔡錫鈞(1.00) |
| 第 5 週 | Balls, Bins, and Random Graphs 2024-03-18(一),2024-03-21(四) 時數：[2024-03-21]蔡錫鈞(2.00) |
| 第 6 週 | The Probabilistic Method 2024-03-25(一),2024-03-28(四) 時數：[2024-03-25]蔡錫鈞(1.00) |
| 第 6 週 | The Probabilistic Method 2024-03-25(一),2024-03-28(四) 時數：[2024-03-28]蔡錫鈞(2.00) |
| 第 7 週 | Markov Chains and Random Walks 2024-04-01(一),2024-04-04(四) 時數：[2024-04-01]蔡錫鈞(1.00) |
| 第 7 週 | Markov Chains and Random Walks 2024-04-01(一),2024-04-04(四) 時數：[2024-04-04]蔡錫鈞(2.00) |
| 第 8 週 | The Normal Distribution 2024-04-08(一),2024-04-11(四) 時數：[2024-04-08]蔡錫鈞(1.00) |
| 第 8 週 | The Normal Distribution 2024-04-08(一),2024-04-11(四) 時數：[2024-04-11]蔡錫鈞(2.00) |
| 第 9 週 | Entropy, Randomness, and Information 2024-04-15(一),2024-04-18(四) 時數：[2024-04-15]蔡錫鈞(1.00) |
| 第 9 週 | Entropy, Randomness, and Information 2024-04-15(一),2024-04-18(四) 時數：[2024-04-18]蔡錫鈞(2.00) |
| 第 10 週 | The Monte Carlo Method 2024-04-22(一),2024-04-25(四) 時數：[2024-04-22]蔡錫鈞(1.00) |
| 第 10 週 | The Monte Carlo Method 2024-04-22(一),2024-04-25(四) 時數：[2024-04-25]蔡錫鈞(2.00) |
| 第 11 週 | Coupling of Markov Chains 2024-04-29(一),2024-05-02(四) 時數：[2024-04-29]蔡錫鈞(1.00) |
| 第 11 週 | Coupling of Markov Chains 2024-04-29(一),2024-05-02(四) 時數：[2024-05-02]蔡錫鈞(2.00) |
| 第 12 週 | Martingales 2024-05-06(一),2024-05-09(四) 時數：[2024-05-06]蔡錫鈞(1.00) |
| 第 12 週 | Martingales 2024-05-06(一),2024-05-09(四) 時數：[2024-05-09]蔡錫鈞(2.00) |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity 2024-05-13(一),2024-05-16(四) 時數：[2024-05-13]蔡錫鈞(1.00) |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity 2024-05-13(一),2024-05-16(四) 時數：[2024-05-16]蔡錫鈞(2.00) |
| 第 14 週 | Pairwise Independence and Universal Hash Functions 2024-05-20(一),2024-05-23(四) 時數：[2024-05-20]蔡錫鈞(1.00) |
| 第 14 週 | Pairwise Independence and Universal Hash Functions 2024-05-20(一),2024-05-23(四) 時數：[2024-05-23]蔡錫鈞(2.00) |
| 第 15 週 | Power Laws and Related Distributions 2024-05-27(一),2024-05-30(四) 時數：[2024-05-27]蔡錫鈞(1.00) |
| 第 15 週 | Power Laws and Related Distributions 2024-05-27(一),2024-05-30(四) 時數：[2024-05-30]蔡錫鈞(2.00) |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing 2024-06-03(一),2024-06-06(四) 時數：[2024-06-03]蔡錫鈞(1.00) |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing 2024-06-03(一),2024-06-06(四) 時數：[2024-06-06]蔡錫鈞(2.00) |
| 第 17 週 | Report 2024-06-10(一),2024-06-13(四) |
Textbook: 教科書 Probability and Computing (2nd Edition) , Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Mitzenmacher and Upfal, 2017 Reference: 參考書 Randomized algorithms, by Motwani and Raghavan, Cambridge University Press, 1995
- 地點
- 工三 623
- 時間
- By appointment
- 聯絡方式
- sctsai@nycu.edu.tw