高等演算法
Advanced Computer Algorithms
| 節 | 週二 |
|---|---|
2 09:00–09:50 | 高等演算法 MB312 3 節連堂 |
3 10:10–11:00 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
The theme is to prepare the participants with fundamentals of combinatorial optimization and solution approaches for solving optimization problems. Through theoretical studies as well as computer implementation, we will gain analytical and computational techniques that are useful for optimization research.
Computer Programming or Data Structures
Grading: homework & programming assignment 40% paper presentation: 15% term-project 35%; participation 10%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Overview and Introduction |
| 第 2 週 | Review on Asymptotic Notations; Time Complexity; Lower bounds on Problem's Complexity |
| 第 3 週 | Greedy Algorithms Theory of NP-completeness |
| 第 4 週 | Theory of NP-completeness; Dynamic Programming |
| 第 5 週 | National holiday |
| 第 6 週 | Dynamic programming |
| 第 7 週 | Mid-term presentation |
| 第 8 週 | Mid-term presentation |
| 第 9 週 | Dynamic programming |
| 第 10 週 | Branch-and-Bound Algorithms; Lower Bounds and Upper Bounds (Lagrangian relaxation) |
| 第 11 週 | Branch-and-Bound Algorithms; Lower Bounds and Upper Bounds (Lagrangian relaxation) |
| 第 12 週 | Design and analysis of heuristics |
| 第 13 週 | Design and analysis of approximation algorithms |
| 第 14 週 | Design of PTAS and FPTAS |
| 第 15 週 | Randomization Algorithms |
| 第 16 週 | Projects |
1. R.C.T. Lee, S.S. Tseng, R.C. Chang, Y.T.Tsai, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, 2005. 2. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 4th Ed., MIT Press, 2022. 3. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979, San Francisco. 4. G. Ausiello, P. Cresenzi, G. Gambois, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 2003, Germany. 5. Selected journal papers
- 地點
- MB310
- 時間
- Monday EF, Thursday E
- 聯絡方式
- 5712121-31472 bmtlin@nycu.edu.tw