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