隨機演算法
Randomized Algorithms
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 隨機演算法 ED302（光復） 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 隨機演算法 ED302（光復） |
* 根據陽明交大上課時間表所列
使同學了解機率在演算法相關領域之應用. 並熟悉隨機演算法之設計及分析證明方法. This course will discuss how to design and analyze randomized algorithms.
機率,演算法 Prerequisites: Probability, Algorithms
無備註
Lectures
Homework 20% Midterm 40% Final project 40%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Basic discrete probability 2026-02-23(一),2026-02-26(四) 時數：[2026-02-23]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 1 週 | Basic discrete probability 2026-02-23(一),2026-02-26(四) 時數：[2026-02-26]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 2 週 | Randomized quicksort and Minimum cut 2026-03-02(一),2026-03-05(四) 時數：[2026-03-02]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 2 週 | Randomized quicksort and Minimum cut 2026-03-02(一),2026-03-05(四) 時數：[2026-03-05]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem 2026-03-09(一),2026-03-12(四) 時數：[2026-03-09]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem 2026-03-09(一),2026-03-12(四) 時數：[2026-03-12]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 4 週 | Chernoff and Hoeffding Bounds, 2026-03-16(一),2026-03-19(四) 時數：[2026-03-16]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 4 週 | Chernoff and Hoeffding Bounds, 2026-03-16(一),2026-03-19(四) 時數：[2026-03-19]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 5 週 | Balls, Bins, and Random Graphs 2026-03-23(一),2026-03-26(四) 時數：[2026-03-23]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 5 週 | Balls, Bins, and Random Graphs 2026-03-23(一),2026-03-26(四) 時數：[2026-03-26]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 6 週 | The Probabilistic Method 2026-03-30(一),2026-04-02(四) 時數：[2026-03-30]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 6 週 | The Probabilistic Method 2026-03-30(一),2026-04-02(四) 時數：[2026-04-02]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 7 週 | Markov Chains and Random Walks 2026-04-06(一),2026-04-09(四) 時數：[2026-04-06]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 7 週 | Markov Chains and Random Walks 2026-04-06(一),2026-04-09(四) 時數：[2026-04-09]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 8 週 | The Normal Distribution 2026-04-13(一),2026-04-16(四) 時數：[2026-04-13]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 8 週 | The Normal Distribution 2026-04-13(一),2026-04-16(四) 時數：[2026-04-16]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 9 週 | Entropy, Randomness, and Information 2026-04-20(一),2026-04-23(四) 時數：[2026-04-20]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 9 週 | Entropy, Randomness, and Information 2026-04-20(一),2026-04-23(四) 時數：[2026-04-23]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 10 週 | The Monte Carlo Method 2026-04-27(一),2026-04-30(四) 時數：[2026-04-27]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 10 週 | The Monte Carlo Method 2026-04-27(一),2026-04-30(四) 時數：[2026-04-30]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 11 週 | Coupling of Markov Chains 2026-05-04(一),2026-05-07(四) 時數：[2026-05-04]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 11 週 | Coupling of Markov Chains 2026-05-04(一),2026-05-07(四) 時數：[2026-05-07]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 12 週 | Martingales 2026-05-11(一),2026-05-14(四) 時數：[2026-05-11]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 12 週 | Martingales 2026-05-11(一),2026-05-14(四) 時數：[2026-05-14]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity 2026-05-18(一),2026-05-21(四) 時數：[2026-05-18]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity 2026-05-18(一),2026-05-21(四) 時數：[2026-05-21]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 14 週 | Pairwise Independence and Universal Hash Functions 2026-05-25(一),2026-05-28(四) 時數：[2026-05-25]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 14 週 | Pairwise Independence and Universal Hash Functions 2026-05-25(一),2026-05-28(四) 時數：[2026-05-28]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 15 週 | Power Laws and Related Distributions 2026-06-01(一),2026-06-04(四) 時數：[2026-06-01]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 15 週 | Power Laws and Related Distributions 2026-06-01(一),2026-06-04(四) 時數：[2026-06-04]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing (Optional) 2026-06-08(一),2026-06-11(四) 時數：[2026-06-08]蔡錫鈞(1.00) 蔡錫鈞(2.00) |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing (Optional) 2026-06-08(一),2026-06-11(四) 時數：[2026-06-11]蔡錫鈞(2.00) 蔡錫鈞(1.00) |
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