難解計算問題專論(英文授課)
Selected Topics in Intractable Problems
| 節 | 週二 | 週五 |
|---|---|---|
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
- 地點
- EC336
- 時間
- TBA
- 聯絡方式
- mtsai@cs.nctu.edu.tw