FIB - LIS - LCS, Knapsack, Chain Multiply
| Algorithm | Subproblem Space | Runtime Complexity | Where to get Return Value | Runtime to get Return Value |
|---|---|---|---|---|
| LIS | $O(n)$ | $O(n^2)$ | $\max(L[1 \dots n])$ | $O(n)$ — scan table |
| LCS (Subsequence) | $O(nm)$ | $O(nm)$ | $L[n, m]$ Bottom-right | $O(1)$ |
| Longest Common Substring | $O(nm)$ | $O(nm)$ | $\max(T[*, *])$ — Anywhere in table | $O(nm)$ — scan full table |
| 0/1 Knapsack | $O(nW)$ | $O(nW)$ | $K[n, W]$ — Bottom-right | $O(1)$ |
| Unlimited Knapsack | $O(W)$ | $O(nW)$ | $K[W]$ — Last element | $O(1)$ |
| Matrix Chain | $O(n^2)$ | $O(n^3)$ | $M[1, n]$ — Top-right | $O(1)$ |
Solving Recurrences, Fast Integer Multiplication, Linear-Time Median
| Algorithm | Recurrence Relation | Runtime Complexity (O) | Description of Work |
|---|---|---|---|
| Binary Search | $T(n) = T(n/2) + O(1)$ | $O(\log n)$ | Dividing the range in half and checking the middle element. |
| Merge Sort | $T(n) = 2T(n/2) + O(n)$ | $O(n \log n)$ | Splitting into two halves and merging them in linear time. |
| Fast Select | $T(n) \le T(n/5) + T(7n/10) + O(n)$ | $O(n)$ | Finding a pivot (Median of Medians) and recursing on one side. |
| Fast Multiply | $T(n) = 3T(n/2) + O(n)$ | $O(n^{\log_2 3}) \approx O(n^{1.58})$ | Karatsuba’s method using 3 multiplications instead of 4. |
Max Flow (Ford-Fulkerson, Max Flow Min Cut, Edmonds-Karp)
3-SAT, Graphs (Independent Set, Clique, Vertex Cover), Knapsack (Subset Sum)