Stanford CS161 導讀：一門把「寫清楚」列為第三個學習目標的演算法課
CS161 第一堂投影片寫下的課程目標有三個：設計、分析、溝通。第三個才是作業不准手寫、要求寫得像給同事的備忘錄的原因。八份作業裡 HW2 是分水嶺，講義的 Python notebook 用來示範「量時間看不出誰比較快」，而暑期班是同課號、同課名、完全另寫一套的另一門課。
19 篇文章
Stanford CS161 導讀
逐講讀 Stanford CS161 Winter 2026：演算法設計、正確性證明與複雜度分析，完整對齊十八講公開教材。
Stanford CS161 Lecture 1：為什麼分析演算法要從 Karatsuba 乘法開始
把兩個 n 位數各切成兩半，直覺分治仍要做 4 個子乘法，時間沒有離開 n²；Karatsuba 用 (a+b)(c+d)-ac-bd 算交叉項，把分支降到 3，得到約 n^1.585 的成長率。
Stanford CS161 Lecture 2：從 InsertionSort 證明到 MergeSort 的 n log n
第二講把「快」拆成可證明的最壞情況上界：InsertionSort 用迴圈不變量證正確、最壞為 n²；MergeSort 用遞迴不變量與每層 O(n) 的遞迴樹，得到 O(n log n)。
Stanford CS161 Lecture 3：Master Theorem 怎麼讀懂一棵遞迴樹
對 T(n)=aT(n/b)+O(n^d)，真正的比較是分支成長 a 與單題工作縮小 b^d：a=b^d 時每層同重，a<b^d 時頂層主導，a>b^d 時葉層主導；不合模板就改用 substitution。
Stanford CS161 Lecture 4：Median of Medians 如何保證線性 Selection
Selection 不必先排序。Median of medians 每 5 個元素取中位數，再取這些中位數的中位數作 pivot，保證較大的遞迴側至多 7n/10+5；用 substitution 可證 worst-case O(n)。
Stanford CS161 Lecture 5：Randomized QuickSort 的期望時間怎麼證
Randomized QuickSort 對每個固定輸入都有 O(n log n) 期望時間，但最壞仍是 Θ(n²)；正確證明不是把期望子問題大小代入 recurrence，而是計算每對元素被比較的機率。
Stanford CS161 Lecture 6：Sorting 下界與線性時間 Radix Sort
Ω(n log n) 只限制 comparison sorting。若整數 key 可直接索引 bucket，stable Counting Sort 可作為 Radix Sort 的內層；在 M≤n^c 等條件下能達 O(n)。
Stanford CS161 Lecture 7：二元搜尋樹、紅黑樹與最壞 O(log n) 的來源
一般 BST 的操作成本是 O(h)，偏斜時會退化成 O(n)；紅黑樹用五條顏色不變量把高度限制在 2 log₂(n+1)，因此搜尋、插入與刪除都有最壞 O(log n) 保證。
Stanford CS161 Lecture 8：雜湊、碰撞與期望 O(1) 到底保證什麼
Universal hash family 只需讓任意兩個不同 key 的碰撞機率不超過 1/n，就能把某個 key 所在 bucket 的期望長度壓到 2 以下；這給的是 expected O(1)，不是每次操作的最壞 O(1)。
Stanford CS161 Lecture 9：圖的表示、DFS、BFS 與兩種搜尋順序的證明
DFS 與 BFS 都在 adjacency list 上以 O(n+m) 掃完整張圖；DFS finish times 能為 DAG 產生拓撲順序，BFS layers 則精確等於無權圖的最短距離。
Stanford CS161 Lecture 10：兩次 DFS 為什麼能找出強連通分量
把每個 SCC 壓成一點後一定得到 DAG；第一趟 DFS 的 finish times 排出這些分量，第二趟在轉置圖按遞減順序搜尋，每棵 DFS tree 恰好是一個 SCC，總時間 O(n+m)。
Stanford CS161 Lecture 11：Dijkstra、Bellman–Ford 與鬆弛的兩種秩序
Dijkstra 每次確定最小 estimate，正確性依賴非負 edge weights；Bellman–Ford 不挑 vertex、反覆鬆弛所有 edges，以 O(nm) 換取負權支援並能偵測 source 可達的負環。
Stanford CS161 Lecture 12：用動態規劃重寫 Bellman–Ford 與 Floyd–Warshall
動態規劃先精確定義子問題，再用 optimal substructure 寫 recurrence，最後依相依順序填表；Bellman–Ford 以 edge 數分層，Floyd–Warshall 則以允許的中繼頂點分層。
Stanford CS161 Lecture 13：從 LCS、背包到樹上獨立集的動態規劃設計法
Lecture 13 把動態規劃整理成五步：選 state、寫 transition、填表、回復解、再優化實作。LCS 是 O(mn)，兩種背包都是 O(nW) 的擬多項式時間，樹上最大權重獨立集則能在 O(|V|) 完成。
Stanford CS161 Lecture 14：貪婪演算法何時能從局部最佳走到全域最佳
貪婪演算法不是『每次挑看起來最好的』，而是每次只保留一個選擇，並用交換論證證明它不會排除最佳解。Lecture 14 以 activity selection、weighted completion time 與 Huffman coding 展示三種證明。
Stanford CS161 Lecture 15：用 cut property 證明 Prim 與 Kruskal
MST 的核心不是背兩支演算法，而是維持『目前選邊仍包含於某棵 MST』，再用 cut property 證明 Prim 與 Kruskal 每一步都安全。
Stanford CS161 Lecture 16：Ford–Fulkerson、殘餘網路與最大流最小割
Ford–Fulkerson 在殘餘網路沿 augmenting path 推流；找不到路時，可達集合形成與 flow 同值的 cut，同時證明最大流、最小割與兩者相等。
Stanford CS161 Lecture 17：Gale–Shapley、穩定配對與可撤銷的貪婪選擇
Deferred Acceptance 允許暫時接受後再反悔；proposal 的單調性證明它在 O(n²) 結束、產生 stable matching，且偏向 proposal 的一側。
Stanford CS161 Lecture 18：從演算法工具箱走向 LP、編碼與 ML
期末課以 slides 回顧 CS161 工具箱，再用 LP duality、Reed–Solomon 與 ML-assisted algorithms 指向後續方向；官方沒有提供 notes。