計算機演算法

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

課程大綱

介紹計算機演算法的設計與分析,內容包含了: 函數成長, 遞迴關係, 排序及序列統計, 基礎與進階資料結構, 動態規劃, 貪婪演算法, 搜尋, 圖形與幾何演算法, 字串比對, 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.

課程進度

Week 01: Introduction Week 02: Array Week 03: Linked list Week 04: Hash table Week 05: Memorization, dynamic programming Week 06: Disjoint classes Week 07: Backtracking Week 08: Tree (1/2) Week 09: Tree (2/2) and immutable data structure Week 10: Mid-term Week 11: Priority queues Week 12: Data compression Week 13: Sorting (1/2) Week 14: Sorting (2/2) Week 15: Graph (1/2) Week 16: Graph (2/2) Week 17: Final Week 18: Final comments

評量方式

Assignment 50% Midterm 20% Final 30%

教材

【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】 使用外文原文書：否 Useful references: 1. Algorithm, 4th ed, https://algs4.cs.princeton.edu/home/, Robert Sedgewick and Kevin Wayne. 2. Introduction to Programming in Java, https://introcs.cs.princeton.edu/java/home/, Robert Sedgewick and Kevin Wayne. 3. Introduction to Algorithms, 3rd Edition by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein 4. The Art of Computer Programming, vol. 2 & 3, https://www-cs-faculty.stanford.edu/~knuth/taocp.html, Donald E. Knuth.