必修課程介紹

• 預備知識：Introduction to Computer Science, Data Structures
• 適合年級： 研究生
• 課程簡介：

本課程是最基本的「計算機科學」之課程之一，目的在學習 “設計演算法” 及 “分析演算法” 的各種技巧，進而明瞭 -- 如何為自己所要解決的問題設計出有效率的演算法，以及分析演算法所使用的資源之多寡。

• 課程大綱：

1. The Role of Algorithms in Computing
2. Growth of Functions, Solving Recurrences
3. Insertion Sort, Merge Sort, Heapsort, Quicksort, Sorting in Linear Time, Medians and Order Statistics
4. Dynamic Programming, Greedy Algorithms
5. Amortized Analysis, Data Structures and Disjoint Sets
6. Graph Algorithms: BFS, DFS, Topological Sort, Minimum Spanning Trees, Single-source Shortest Paths, All-pairs Shortest Paths, Network Flows
7. Special Topics: Sorting Networks, Matrix Multiplication, String Matching
8. NP-Completeness, Approximation Algorithms

• 參考書目：

1. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Edition, 2009, The MIT Press.