教學日程
演算法導論(SMA 5503)
因舊版課程無指定課堂作業與考試,因此統整所有作業、講義、考試內容合併列出。
演算法導論(SMA 5503)
因舊版課程無指定課堂作業與考試,因此統整所有作業、講義、考試內容合併列出。
以下日程表提供課程的講授(L)、復習(R)和測試(Q)課程的資訊。
Course schedule. |
||
課 |
課程單元 |
重要日期 |
第一課 |
課程細節 課程介紹 演算法分析、 插入排序、歸併排序 |
分發作業1 |
復習一 |
演算法正確性 Horner定則 |
|
第二課 |
漸進標記法 遞迴 置換、主方式 |
|
第三課 |
分治法: Strassen、費氏數列、多項式乘法 |
|
復習二 |
遞迴、鬆散性質 |
|
第四課 |
快速排序、隨機演算法 |
作業1提交 分發作業2 |
復習三 |
堆排序、動態集合、優先佇列 |
|
第五課 |
線形時間排序:下限、計數排序、根排序 |
|
第六課 |
順序統計、中位數 |
|
復習四 |
中位數應用 桶式排序 |
|
第七課 |
散列法、哈希函數 |
作業2提交 分發作業3 |
第八課 |
一般散列、完美散列 |
今晚有作業實驗室 |
復習五 |
測試1復習 |
作業3提交 |
測試1 |
隨堂測試1 |
|
復習六 |
二元搜索樹、樹的遍歷 |
|
第九課 |
二元排序樹與快速排序的關係 隨機二元排序樹的分析 |
分發作業4 |
第十課 |
紅黑樹、反轉、插入、刪除 |
|
復習七 |
2-3樹、B-樹 |
|
第11課 |
擴充資料結構、動態順序統計、區間樹 |
作業4提交 分發作業5 |
第12課 |
跳過的章節 |
|
復習八 |
範圍樹 |
|
第13課 |
平攤演算法、表的倍增、潛能法 |
作業5提交 分發作業6 |
第14課 |
競爭分析、自組織列表 |
|
復習九 |
競爭分析:滑雪鞋租賃、隨機競爭演算法 |
|
第15課 |
動態規劃、最大公共子序列 |
作業6提交 分發作業7 |
第16課 |
貪心演算法、最小生成樹 |
|
第17課 |
最短路徑I:屬性、Dijkstra演算法、廣度優先搜索 |
作業7提交 分發作業8 |
第18課 |
最短路徑II:Bellman-Ford演算法、線形程式寫作、差異限制 |
|
復習十 |
圖形搜索:深度優先搜索、拓撲排序、DAG最短路徑 |
|
第19課 |
最短路徑III:所有頂點對間最短路徑演算法、矩陣乘法、Floyd-Warshall演算法、Johnson演算法 |
作業8提交 |
第20課 |
測試2復習 |
|
第21課 |
道德規範,解答(強制參加) |
分發課外測驗 |
測試二 |
隨堂測試2 |
測驗二的兩天後提交課外測驗 |
第22課 |
高級論題 |
分發作業9 |
第23課 |
高級論題(續) |
今晚有作業實驗室 |
復習11 |
高級論題 |
作業9提交 |
第24課 |
高級論題(續) |
|
第25課 |
高級論題(續) 討論後續的課程 |
|
|
期末考試 |
|