難解計算問題專論(英文授課)
Selected Topics in Intractable Problems
學期
107-2
學分
3
學分
當期課號
5241
永久課號
IOC5204
開課單位
資訊科學與工程研究所
授課教師
蔡孟宗
校區
光復
類別
選修
上課時間表
| 節 | 週二 | 週五 |
|---|---|---|
3 10:10–11:00 | 難解計算問題專論(英文授課) ED102 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 難解計算問題專論(英文授課) ED102 |
* 根據陽明交大上課時間表所列
概述
Understand the limit of computers, and learn how to design algorithms better than exhaustive search for intractable problems.
先修科目
Introduction to Algorithms, Introduction to Formal Language, Probability, Linear Algebra, Data Structures and Object-Oriented Programming
教學方式
TA: TBA; Course Materials: https://e3new.nctu.edu.tw/login/index.php ; Online Judge: https://oj.nctu.me
評分方式
4 written assignments and 4 programming assignments. Take best 5 out of the 8 assignments.
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | NP-hardness, Exponential-time Hypothesis |
| 第 2 週 | NP-intermediate, Sparse Languages, Ladner's Theorem, Mahaney's Theorem |
| 第 3 週 | Enumeration, Heap's Algorithm |
| 第 4 週 | CPU-dependent Instruction Sets, Inline Assembly, Bitwise Parallelism |
| 第 5 週 | Table-lookups, Hashing, Dynamic Programming |
| 第 6 週 | Pruning by Fractional Solutions, Linear Programming |
| 第 7 週 | Pruning by Shortcutting, Matching, Graph Bandwidth |
| 第 8 週 | #P-hardness, Permanent, Ryser's Formula |
| 第 9 週 | Probabilistic Methods |
| 第 10 週 | PTAS, Separator Theorems, Planar Graphs, k-nearest Neighbor Graphs |
| 第 11 週 | PCP Theorem, APX-hardness, log-APX-hardness, poly-APX-hardness, APX-intermediate |
| 第 12 週 | Approximation Algorithms |
| 第 13 週 | Approximation Algorithms |
| 第 14 週 | W Hierarchy |
| 第 15 週 | Fixed-Parameter Algorithms |
| 第 16 週 | Fixed-Parameter Algorithms |
| 第 17 週 | RP, co-RP, BPP, ZPP, Randomized Algorithms |
| 第 18 週 | Randomized Rounding, Linear Programming, Semidefinite Programming |
教科書
Research papers
Office Hours
- 地點
- EC336
- 時間
- TBA
- 聯絡方式
- mtsai@cs.nctu.edu.tw