隨機演算法
Randomized Algorithms
學期
112-2
學分
3
學分
當期課號
535522
永久課號
CSIC30133
開課單位
資訊科學與工程研究所
授課教師
蔡錫鈞
校區
光復
類別
選修
上課時間表
| 節 | 週一 | 週四 |
|---|---|---|
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 |
| 第 1 週 | Basic discrete probability |
| 第 2 週 | Randomized quicksort and Minimum cut |
| 第 2 週 | Randomized quicksort and Minimum cut |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem |
| 第 3 週 | Minimum cut and Boolean Function Evaluation Lower bound with Yao's Minmax Principle Stable marriage problem |
| 第 4 週 | Chernoff and Hoeffding Bounds, |
| 第 4 週 | Chernoff and Hoeffding Bounds, |
| 第 5 週 | Balls, Bins, and Random Graphs |
| 第 5 週 | Balls, Bins, and Random Graphs |
| 第 6 週 | The Probabilistic Method |
| 第 6 週 | The Probabilistic Method |
| 第 7 週 | Markov Chains and Random Walks |
| 第 7 週 | Markov Chains and Random Walks |
| 第 8 週 | The Normal Distribution |
| 第 8 週 | The Normal Distribution |
| 第 9 週 | Entropy, Randomness, and Information |
| 第 9 週 | Entropy, Randomness, and Information |
| 第 10 週 | The Monte Carlo Method |
| 第 10 週 | The Monte Carlo Method |
| 第 11 週 | Coupling of Markov Chains |
| 第 11 週 | Coupling of Markov Chains |
| 第 12 週 | Martingales |
| 第 12 週 | Martingales |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity |
| 第 13 週 | Sample Complexity, VC Dimension, and RademacherComplexity |
| 第 14 週 | Pairwise Independence and Universal Hash Functions |
| 第 14 週 | Pairwise Independence and Universal Hash Functions |
| 第 15 週 | Power Laws and Related Distributions |
| 第 15 週 | Power Laws and Related Distributions |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing |
| 第 16 週 | Balanced Allocations and Cuckoo Hashing |
| 第 17 週 | Report |
教科書
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
Office Hours
- 地點
- 工三 623
- 時間
- By appointment
- 聯絡方式
- sctsai@nycu.edu.tw