計算機演算法

臺北科技大學 114-2 學期課程，課號 355287。

課程大綱

介紹計算機演算法的設計與分析,內容包含了: 函數成長, 遞迴關係, 排序及序列統計, 基礎與進階資料結構, 動態規劃, 貪婪演算法, 搜尋, 圖形與幾何演算法, 字串比對, NP-completeness, 近似演算法, 及平行與分散式演算法. This course gives a broad introduction about the design and analysis of computer algorithms. General topics to be covered include: growth of functions, recurrences, sorting and order statistics, fundamental and advanced data structures, dynamic programming, greedy algorithms, searching, graph and geometry algorithms, string matching, NP-completeness, approximation algorithms, parallel and distributed algorithms.

課程進度

Calendar: 1. No Class (2/28, 國定假日) 2. Mathematical Foundations: Introduction 3. Analyzing & Designing Algorithms 4. Growth of Functions, Recurrences 5. Heapsort 6. No Class (4/3, 國定假日) 7. Quicksort, Sorting in Linear Time 8. Mid-term Exam (in class) 9. No Class (4/24, 統測考場)，Mid-term Exam (take home) 10. No Class (5/1, 國定假日) 11. Medians, Order Statistics 12. Greedy Algorithms 13. Dynamic Programming (I) 14. Dynamic Programming (II) 15. Elementary Graph Algorithms & Minimum Spanning Trees 16. Shortest Paths Algorithms 17. No Class (6/19, 國定假日) 18. Final Exam

評量方式

Grading: 30% Assignments & Term Project 30% Mid-term Exam (take home 40%, in class 60%) 40% Final Exam (take home 40%, in class 60%)

教材

【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】 使用外文原文書：是 1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Ed., The MIT Press, 2001. (開發) 2. Michael T. Goodrich, Roberto Tamassia, and David M. Mount, Data Structures and Algorithms in C++, Second Edition, John Wiley & Sons, Inc, 2011. (ISBN-13 978-0-470-38327-8)