|
|
|
|
|
|
|
|
1 |
|
|
|
第一課 課程細節；序論：演算法分析，插入排序法(Insertion Sort)，合併排序(Merge Sort)
閱讀：1-2章
Lecture 1 Administrivia; Introduction: Analysis of Algorithms, Insertion Sort, Mergesort
Reading: Chapters 1–2 |
|
|
|
-
|
|
|
發測驗 0
Quiz 0 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
-
|
|
|
|
演習課 1 演算法的正確性Recitation 1 Correctness of Algorithms |
|
|
交測驗 0
Quiz 0 Due
發《作業 1》
PS 1 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
第二課趨近符號。遞迴式：取代法，迴圈法，主方式
閱讀：3-4 章，除了§4.4
Lecture 2 Asymptotic Notation. Recurrences: Substitution, Iteration, Master Method
Reading: Chapters 3–4, Excluding §4.4 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
第三課 各個擊破法： Strassen 演算法，費氏數列，多項式乘法。
閱讀：28 章第 2 節，30章第1節
Lecture 3 Divide and Conquer: Strassen's Algorithm, Fibonacci Numbers, Polynomial Multiplication
Reading: §28.2 and §30.1 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
-
|
|
|
|
演習課 2 遞迴公式，鬆散性質
閱讀：Akra-Bazzi 的講義
Recitation 2 Recurrences, Sloppiness (Akra-Bazzi)
Reading: Akra-Bazzi Handout |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
第四課 快速排序法，隨機演算法
閱讀：5 章 1 到 3 節，7 章
Lecture 4 Quicksort, Randomized Algorithms
Reading: §5.1–5.3, Chapter 7 |
|
|
|
-
|
|
|
收《作業 1》
發《作業 2》
PS 1 Due
PS 2 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
-
|
|
|
|
演習課 3 排序：堆積排序法，動態集合，優先佇列
閱讀：6 章
Recitation 3 Sorting: Heapsort, Dynamic Sets, Priority Queues
Reading: Chapter 6 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
第五課 線性時間的排序法，下限，計數排序法， 基數排序法
閱讀： 8 章第 1 到 3 節
Lecture 5 Linear-time Sorting, Lower Bounds, Counting Sort, Radix Sort
Reading: §8.1–§8.3 |
|
|
|
-
|
|
|
收《作業 2》
發《作業 3》
PS 2 Due
PS 3 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
第六課 序列統計，中位數
閱讀：9 章
Lecture 6 Order Statistics, Median
Reading: Chapter 9 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
-
|
|
|
|
演習課 4 中位數的應用，桶式排序
閱讀：8 章第 4 節
Recitation 4 Applications of Median, Bucketsort
Reading: §8.4 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
第七課 雜湊，萬用雜湊
閱讀： 11 章 1 到 3 節
Lecture 7 Hashing, Universal Hashing
Reading: §11.1–§11.3 |
|
|
|
-
|
|
|
收《作業 3》
發《作業 4》
PS 3 Due
PS 4 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
第八課 雜湊函數，完美雜湊
閱讀：11 章第 5 節
Lecture 8 Hash Functions, Perfect Hashing
Reading: §11.5 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
-
|
|
|
|
演習課 5 測驗 1 複習
Recitation 5 Quiz 1 Review |
|
|
收《作業 4》
PS 4 Due |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
評分後的作業4可以在中午拿到
Graded PS 4 Available by Noon |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
測驗 1
Quiz 1 in Class |
|
|
|
-
|
|
|
測驗 1Quiz 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
-
|
|
|
|
演習課 6 二元搜尋樹，樹的追蹤
閱讀：12 章 1 到 3 節
Recitation 6 Binary Search Trees, Tree Walks
Reading: §12.1–§12.3 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
第九課 二元搜尋樹和快速排序法的關係；隨機二元搜尋樹的分析
閱讀：12 章 4 節
Lecture 9 Relation of BST's to Quick Sort; Analysis of Random BST
Reading: §12.4 |
|
|
|
-
|
|
|
發《作業 5》
PS 5 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
第十課 紅黑樹，旋轉，插入，刪除
閱讀：13 章
Lecture 10 Red-Black Trees, Rotations, Insertions, Deletions
Reading: Chapter 13 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
-
|
|
|
|
演習課 7 2-3樹， B-樹
閱讀：18 章 1 到 2 節
Recitation 7 2-3 Trees, B-Trees
Reading: §18.1–§18.2 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
第十一課 擴充資料結構，線段樹
閱讀：14 章
Lecture 11 Augmenting Data Structures, Interval Trees
Reading: Chapter 14 |
|
|
|
-
|
|
|
收《作業 5》
發《作業 6》
PS 5 Due
PS 6 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
第十二課 計算幾何，區間查詢
閱讀：33 章 1 到 2 節
Lecture 12 Computational Geometry, Range Queries
Reading: §33.1–§33.2 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
|
|
-
|
|
|
|
演習課 8 凸多邊形
閱讀：33 章 3 節
Recitation 8 Convex Hulls
Reading: §33.3 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
|
|
|
第十三課 van Emde Boas，優先佇列
閱讀：van Emde Boas 的講義
Lecture 13 van Emde Boas, Priority Queues
Reading: van Emde Boas Handout |
|
|
|
-
|
|
|
收《作業 6》
發《作業 7》
PS 6 Due
PS 7 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
24 |
|
|
|
第十四課 攤提演算法，表的倍增，潛能法
閱讀：17 章
Lecture 14 Amortized Algorithms, Table Doubling, Potential Method
Reading: Chapter 17 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
-
|
|
|
|
演習課 9 競爭分析，自我重組序列
Recitation 9 Competitive Analysis, Self-Organizing Lists |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
|
|
|
第十五課 動態規劃，最長相同子序列，最佳二元搜尋樹
閱讀：15 章
Lecture 15 Dynamic Programming, Longest Common Subsequence, Optimal BST
Reading: Chapter 15 |
|
|
|
-
|
|
|
收《作業 7》
發《作業 8》
PS 7 Due
PS 8 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
27 |
|
|
|
第十六課 貪婪演算法，最小擴張樹
閱讀：16 章 1 到 3 節， 23 章
Lecture 16 Greedy Algorithms, Minimum Spanning Trees
Reading: §16.1–16.3 and Chapter 23 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28 |
|
|
|
-
|
|
|
|
演習課 10貪婪演算法和動態規劃範例
Recitation 10 Examples of Greedy Algorithms and Dynamic Programming |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
29 |
|
|
|
第十七課 最短路徑，Dijkstra演算法，廣度優先搜尋法
閱讀：22 章1， 2 節；第 580 - 587 頁，24章 3 節
Lecture 17 Shortest Paths, Dijkstra's Algorithm, Breadth-First Search
Reading: §22.1, §22.2; pp. 580–587, §24.3 |
|
|
|
-
|
|
|
收《作業 8》
發《作業 9》
PS 8 Due
PS 9 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
|
|
|
-
|
|
|
|
演習課 11 深度優先搜尋法，邊的分類
閱讀：22 章 3 到 5 節
Recitation 11 Depth-First Search, Edge Classification
Reading: §22.3–22.5 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
31 |
|
|
|
第十八課 最短路徑，Bellman-Ford，DAG內的最短路徑，差異限制式
閱讀：24 章 1, 2, 4, 5 節
Lecture 18 Shortest Paths, Bellman-Ford, Shortest Paths in DAGs, Difference Constraints
Reading: §24.1, §24.2, §24.4, §24.5 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
32 |
|
|
|
第十九課 全成對最短路徑，動態規劃，Floyd-Warshall，Johnson 的演算法
閱讀：25 章
Lecture 19 All-Pairs Shortest Paths, Dynamic Programming, Floyd-Warshall, Johnson's Algorithm
Reading: Chapter 25 |
|
|
|
-
|
|
|
收《作業 9》
PS 9 Due |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
33 |
|
|
|
第二十課 分割集合資料結構
閱讀：21 章
Lecture 20 Disjoint-Set Data Structure
Reading: Chapter 21 |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
34 |
|
|
|
評分後的作業9可以在中午拿到
Graded PS 9 Available by Noon |
|
|
|
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
35 |
|
|
|
第二十一課 發回家測驗 2 ; 道德，解題 (強制出席)
Lecture 21 Take-Home Quiz 2 Handed Out; Ethics, Problem Solving (Mandatory Attendance) |
|
|
|
-
|
|
|
發測驗 2
Quiz 2 Out |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36 |
|
|
|
-
|
|
|
|
沒有演習課 - 解答測驗 2!
NO RECITATION - Work on Quiz 2!
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
37 |
|
|
|
沒有課
演算法程式比賽開始 (自由參加)
NO LECTURE
Algorithmic Programming Contest Begins (Optional) |
|
|
|
-
|
|
|
收測驗 2
Quiz 2 Due |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
38 |
|
|
|
第二十二課 網路流量，最大流量最小切割定理
閱讀：26 章 1 - 2 節
Lecture 22 Network Flow, Max-Flow Min-Cut Theorem
Reading: §26.1– 26.2 |
|
|
|
-
|
|
|
發《作業 10》 (選答)
PS 10 Out (Optional) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
39 |
|
|
|
-
|
|
|
|
演習課 12 配對（註：最大二分圖配對）
閱讀：26 章 3 節
Recitation 12 Match Making
Reading: §26.3 |
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
40 |
|
|
|
第二十三課 網路流量，Edmonds-Karp 演算法
Lecture 23 Network Flow, Edmonds-Karp Algorithm |
|
|
|
-
|
|
|
參賽答案截止
Contest Entries Due |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
41 |
|
|
|
第二十四課 隨堂測驗；比賽頒獎；後續課程的討論
Lecture 24 Diagnostic Quiz in Class; Contest Awards; Discussion of Follow-on Courses |
|
|
|
-
|
|
|
《作業 10》解答
PS 10 Solutions Out |
|
|
|
|
|
|
|
