高等演算法(英文授課)
Advanced Algorithms
學期
108-2
學分
3
學分
當期課號
5903
永久課號
IOC5210
開課單位
資訊科學與工程研究所
授課教師
蔡孟宗
校區
光復
類別
選修
上課時間表
| 節 | 週五 |
|---|---|
3 10:10–11:00 | 高等演算法(英文授課) ED202 3 節連堂 |
4 11:10–12:00 | |
N 12:20–13:10 |
* 根據陽明交大上課時間表所列
概述
Introduction to some frequently-used techniques in algorithm design and some computational models.
先修科目
Data Structures, Algorithms, Probability, Discrete Math, Linear Algebra
教學方式
https://e3new.nctu.edu.tw/
評分方式
In-class quizzes x 5.
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Graph orientation. |
| 第 2 週 | Color coding techniques. |
| 第 3 週 | EC, VC, ear decomposition. |
| 第 4 週 | Spanners. |
| 第 5 週 | Graph decompositions. |
| 第 6 週 | Cuckoo hashing. |
| 第 7 週 | Locality sensitive hashing. |
| 第 8 週 | Quadrangle inequalities. |
| 第 9 週 | Matroid. |
| 第 10 週 | Submodularity and supermodularity. |
| 第 11 週 | Linear programming in low dimensions. |
| 第 12 週 | Parametric search. |
| 第 13 週 | epsilon-nets. |
| 第 14 週 | Naor-Naor derandomization. |
| 第 15 週 | Property testing. |
| 第 16 週 | Streaming algorithms. |
| 第 17 週 | Distributed algorithms. |
| 第 18 週 | Dynamic algorithms. |
教科書
Research papers.
Office Hours
- 地點
- EC 336
- 時間
- TBA
- 聯絡方式
- mtsai@cs.nctu.edu.tw