Lecture Notes

Template

Dynamic Programming 1

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)$

Divide and Conquer

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.

Dynamic Programming 2

Shortest Paths

Graphs 1 (Strongly Connected Components)

Strongly Connected Components

2-Satisfiability

Graphs 2 (Minimum Spanning Tree)

Minimum Spanning Tree (MST)

Graphs 3 (Max Flow)

Max Flow (Ford-Fulkerson, Max Flow Min Cut, Edmonds-Karp)

NP Theory

Definitions

3-SAT, Graphs (Independent Set, Clique, Vertex Cover), Knapsack (Subset Sum)