隨機演算法
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 20% Midterm 50% Final Exam 30%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Basic discrete probability |
| 第 2 週 | Randomized quicksort and Minimum cut |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem |
| 第 4 週 | Chernoff and Hoeffding Bounds, |
| 第 5 週 | Balls, Bins, and Random Graphs |
| 第 6 週 | The Probabilistic Method |
| 第 7 週 | Markov Chains and Random Walks |
| 第 8 週 | The Normal Distribution |
| 第 9 週 | Entropy, Randomness, and Information |
| 第 10 週 | The Monte Carlo Method |
| 第 11 週 | Coupling of Markov Chains |
| 第 12 週 | Martingales |
| 第 13 週 | Sample Complexity, VC Dimension, and Rademacher Complexity |
| 第 14 週 | Pairwise Independence and Universal Hash Functions |
| 第 15 週 | Power Laws and Related Distributions |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing |
| 第 17 週 |
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