CSCI2100
數據結構
鏈表、堆疊與隊列、動態陣列、雜湊、優先隊列、二叉搜尋樹、平衡搜尋樹與多路搜尋樹、Trie、不相交集合、排序、圖算法及算法分析。
你的進度
0/ 30 節已標記完成
下一節: 不相交集合:劃分、森林與並查集
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI2100 筆記裏的內容
數字只算這門課 30 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 69 · 定義 41 · 反例 39 · 概念視角 20 · 證明透視 35
第 1 章 · 1 節
不相交集合
劃分與並查集
- 1.1
不相交集合:劃分、森林與並查集
用父指標森林表示逐步合併的群組,證明連接根與路徑壓縮的正確性,並分析按大小合併。
第 2 章 · 3 節
線性數據結構
隊列不變量、攤銷分析及鏈表環偵測。
- 2.1
用兩個堆疊建立先進先出隊列
證明隊列不變量,並計算偶爾昂貴的轉移成本。
- 2.2
不用已訪集合找出鏈表中的環
追蹤 Floyd 的指標,證明相遇原因,並定位及安全移除環。
- 2.3
雙堆疊隊列:不變量與攤銷成本
追蹤隊首觀察、轉移迴圈與攤銷成本。
第 3 章 · 2 節
優先隊列
堆不變量、插入及移除最小值。
- 3.1
二叉最小堆與優先隊列
證明二叉最小堆不變量,分析插入及移除最小值。
- 3.2
自底向上建立最小堆
證明下濾的正確性及原地建立堆的線性時間界。
第 4 章 · 2 節
搜尋樹的次序統計量
維持子樹大小並按排名選取鍵。
- 4.1
在搜尋樹中按排名選取
證明排名選取,並在插入、刪除及旋轉下維持子樹計數。
- 4.2
選取最小的 k 個記錄
以排名閾值選出恰好 k 個記錄,明確訂立平手、次序和成本。
第 5 章 · 2 節
雜湊
分離鏈結與碰撞的期望成本。
- 5.1
分離鏈結與碰撞的期望成本
跟蹤鏈結查詢,並在逐對碰撞假設下證明期望界。
- 5.2
線性探測與墓碑刪除
追蹤有界探測並證明刪除與鍵唯一性的不變量。
第 6 章 · 1 節
概率式成員判定
Bloom 過濾器、保證及假陽性模型。
- 6.1
Bloom 過濾器與假陽性
區分確定性成員保證與理想化假陽性模型。
第 7 章 · 2 節
字串 Trie
精確成員、前綴列舉與安全剪枝。
- 7.1
Trie 前綴、終止標記與安全剪枝
維護精確字串成員與前綴列舉,並證明刪除保留共用路徑。
- 7.2
追蹤精確查找與前綴補全
逐字追蹤 trie 查詢,區分到達節點與已儲存鍵值。
第 8 章 · 1 節
多路搜尋樹
在插入時維持 B 樹的佔用及搜尋不變量。
- 8.1
B 樹:不變量、分裂與由上而下插入
定義多路搜尋樹的規格,證明子節點分裂及插入正確,追蹤二階例子,並區分高度、比較及區塊讀取成本。
第 9 章 · 1 節
自調整搜尋樹
伸展旋轉與攤銷存取證明。
- 9.1
伸展樹:旋轉與存取引理
追蹤伸展操作並證明無權攤銷存取界。
第 10 章 · 2 節
鏈表不變量
哨兵環、節點所屬關係與拼接的代價。
- 10.1
哨兵鏈表與節點拼接
從局部連結推導整體成員關係,並計算搜尋與維護大小的代價。
- 10.2
遞歸刪除與回傳的表頭
追蹤節點所有權與元數據,證明遞歸刪除的規格。
第 11 章 · 1 節
動態陣列
幾何擴縮容與攤銷成本。
- 11.1
動態陣列與攤銷成本
追蹤擴縮容並證明攤銷更新界。
第 12 章 · 1 節
有序陣列搜尋
邊界搜尋與迴圈不變量。
- 12.1
二分搜尋:邊界與迴圈不變量
證明上下界,處理重複值並分析存取成本。
第 13 章 · 2 節
圖遍歷
用隊列和發現標記尋找無權圖最短路徑。
- 13.1
廣度優先搜尋:隊列與最短路徑
追蹤入隊標記,證明層次不變量並重建無權圖最短路徑。
- 13.2
圖的表示法與深度優先搜尋
比較鄰接矩陣與鄰接表,並分析深度優先搜尋:時間戳、邊的分類、環偵測與拓撲次序。
第 14 章 · 2 節
圖算法
最小生成森林與並查集。
- 14.1
Kruskal 算法:並查集與最小生成森林
證明森林不變量和貪婪割交換,並追蹤按大小合併。
- 14.2
加權圖的前沿:Dijkstra 與 Prim
在同一加權圖上追蹤使用惰性堆的 Dijkstra 算法及 Prim 算法,並證明各自選取步驟的安全性。
第 15 章 · 2 節
平衡搜尋樹
AVL 樹與紅黑樹:高度界及更新後的修復。
- 15.1
AVL 樹:高度、旋轉與刪除
證明對數高度界,以旋轉保留搜尋次序,並逐步分析插入及向上連鎖的刪除修復。
- 15.2
紅黑樹:黑高度與插入修復
從顏色不變量推導對數搜尋深度,證明各種插入修復,並分清重新着色與旋轉的代價。
第 16 章 · 1 節
雜湊表與通用雜湊
鏈結法、期望鏈長與通用雜湊族。
- 16.1
雜湊表:鏈結法、通用雜湊與期望成本
在碰撞中保留映射,以指示變量證明期望鏈長,並用質數模運算建立通用雜湊族。
第 17 章 · 1 節
二叉搜尋樹
普通二叉搜尋樹的次序不變量與刪除。
- 17.1
二叉搜尋樹刪除:後繼節點、子樹回傳與節點身分
以後繼節點取代法刪除二叉搜尋樹的鍵,回傳新的子樹根,並檢驗次序不變量與成本。
第 18 章 · 2 節
排序
鏈表上的合併排序、陣列合併排序、快速排序與比較排序下界。
- 18.1
鏈表上的合併排序:正確性同樣關乎連結
以破壞性且穩定的方式合併已排序鏈表,用快慢指標分割鏈表,並分析鏈表上的合併排序。
- 18.2
比較排序:合併排序、快速排序與下界
以不變量與遞推式分析陣列上的合併排序和快速排序,並證明任何比較排序都需要約 n log n 次比較。
第 19 章 · 1 節
算法分析
成本模型與漸進記號。
- 19.1
漸進記號與成本模型
固定成本模型,以明確的常數定義 O、Omega 與 Theta,並推導簡單迴圈程式碼的增長類別。