Algorithms II: Graphs, Dynamic Programming, Greedy & Flows

Most optimization problems are a graph in disguise — schedules, dependencies, assignments, routes — and the art is recognizing which structure and which paradigm fits. Graph search (DFS/BFS) is the substrate: finish-time order powers topological sort and strongly-connected components; BFS layers give unweighted shortest paths. On top sit three optimization paradigms. Dynamic programming handles overlapping subproblems by tabulating them — and the flagship shortest-path algorithms (Bellman–Ford, Floyd–Warshall) are DP on graphs. Greedy makes one locally-optimal choice and never reconsiders — fast and simple when the substructure is nice, but it must be proven correct, usually by an exchange argument; Dijkstra, Prim, and Kruskal (MST) are greedy on graphs. Flow turns cuts, matchings, and selection problems into max-flow via the max-flow–min-cut duality. The recurring decision is the spine: DP if subproblems overlap, greedy if one choice leaves one clean subproblem, flow if it’s about separating or pairing. Prerequisites cashed in: DFS/BFS and $O(\log n)$ heaps, recurrences and induction, the decomposition method and Monte-Carlo idea (13a); indicator RVs and geometric trials (track 1).

1. Graph foundations and search

• Setup. $G = (V, E)$, $n = |V|$, $m = |E|$. Store as an adjacency list ($O(n+m)$ space, good for sparse graphs — the default) or an adjacency matrix ($O(n^2)$). Undirected: connected components. Directed: strongly connected components (§ below) — don’t conflate the two.

• Depth-first search. Go as deep as possible, mark a node done, backtrack to the nearest unexplored neighbor — DFS implicitly builds a tree (a forest if you must restart at unreached vertices). Track a start and finish time per node. Runtime: each vertex $O(1)$ plus $\sum_w \deg(w) = 2m$, so $O(n+m)$.

  • Parentheses theorem: in the DFS forest the time-intervals nest — if $v$ is a descendant of $w$ then $(w.\text{start}, v.\text{start}, v.\text{finish}, w.\text{finish})$; otherwise the intervals are disjoint.
  • Topological sort (DAG): for any edge $A\to B$, $B.\text{finish} < A.\text{finish}$, so listing vertices in decreasing finish time respects every dependency. $O(n+m)$ — just DFS, prepend each vertex as it finishes.

• Breadth-first search. Explore by distance: a FIFO queue, peeling off layers $L_0, L_1, \dots$. Also $O(n+m)$.

  • Shortest path (unweighted): a vertex’s layer index is its distance from the source (init dist 0 at source, $\infty$ elsewhere; each neighbor is parent-distance + 1).
  • Bipartite test: 2-color by layer parity; a graph is bipartite iff this never puts an edge within a color — equivalently iff it has no odd cycle.

• Strongly connected components. An SCC is a maximal set with a directed path both ways between every pair. Contract each SCC to a meta-vertex → the SCC graph is a DAG (no cycles between SCCs). Kosaraju’s algorithm, $O(n+m)$:

  1. DFS on $G$, record finish times.
  2. Reverse all edges (this leaves SCCs unchanged).
  3. DFS on $G^{\text{rev}}$, starting from the largest finish time first; each tree of this second forest is one SCC.

  Why: the key lemma — in the forward graph, if there’s an edge from SCC $A$ to SCC $B$ then $\max\text{-finish}(A) > \max\text{-finish}(B)$ — so the largest finish time lies in a “source” SCC of the DAG, and exploring the reversed graph from it can’t escape that SCC. Picture (draw it): circle each SCC and contract it to one node — the result is a DAG with source and sink SCCs; the largest overall finish time always lands in a source SCC, so peeling off finish-times-descending on the reversed graph carves out exactly one SCC per DFS tree.

Core competency set

• Give adjacency-list vs matrix tradeoff; state DFS/BFS as $O(n+m)$.
• Topological sort by decreasing finish time; BFS for unweighted shortest path and bipartiteness (odd cycle).
• State Kosaraju’s three steps and the finish-time key lemma.

2. Shortest paths

• Dijkstra — greedy, nonnegative weights, single-source. Maintain a set $S$ of finalized vertices; repeatedly extract the vertex $u \in V \setminus S$ with the smallest distance estimate, add it to $S$, and relax its outgoing edges (update each neighbor’s estimate to $\min(\text{old}, d(u) + w(u,v))$).
  • Why greedy is safe: with nonnegative weights, the closest unfinalized vertex can’t be improved by a detour through a farther one — so its estimate is already final when extracted.
  • Each vertex is extracted once (insert + extract-min, $n$ times) with a decrease-key per edge → with a heap, $O((m+n)\log n)$. (Negative weights break the greedy guarantee — use Bellman–Ford.)
  • Numeric anchor: edges $s\!\to\!a\,(1),\ s\!\to\!b\,(4),\ a\!\to\!b\,(2),\ a\!\to\!t\,(5),\ b\!\to\!t\,(1)$. Finalize in nondecreasing order: $d(s){=}0$; relax → $d(a){=}1,\ d(b){=}4$; extract $a$, relax → $d(b){=}\min(4, 1{+}2){=}3,\ d(t){=}6$; extract $b$, relax → $d(t){=}\min(6, 3{+}1){=}4$; extract $t$. Shortest $s\!\to\!t = 4$ via $s\,a\,b\,t$ — note each vertex is finalized at a value $\ge$ the previous one, the greedy invariant in action.
• Bellman–Ford — DP, tolerates negative edges (no negative cycles). The optimal substructure budgets the output: $d^{(i)}(s,v) =$ shortest-path cost using $\le i$ edges, with recurrence

$d^{(i+1)}(s,v) = \min_{u}\big(d^{(i)}(s,u) + w(u,v)\big)$

(the last hop came from some neighbor $u$). A shortest path is simple (no negative cycle ⇒ no beneficial cycle), so it has $\le n-1$ edges; iterate $i$ up to $n-1$. Negative-cycle detection: if any estimate still improves at iteration $n$, a negative cycle is reachable. $O(nm)$; only the previous row is needed, and you can skip vertices that didn’t change.

• Floyd–Warshall — DP, all-pairs shortest paths. Substructure indexes the allowed intermediate vertices: $D^{(k)}[u,v] =$ shortest $u\to v$ path using only intermediates in $\{1,\dots,k\}$. Adding vertex $k$ either helps or doesn’t:

$D^{(k)}[u,v] = \min\Big(D^{(k-1)}[u,v],\ \ D^{(k-1)}[u,k] + D^{(k-1)}[k,v]\Big).$

Three nested loops → $O(n^3)$, beating $n$ runs of Bellman–Ford ($O(n^2 m)$). (Johnson’s algorithm reweights with a dummy source so Dijkstra can be run from every vertex for APSP on sparse graphs.)

Core competency set

• Dijkstra: greedy procedure, why nonnegativity is required, $O((m+n)\log n)$.
• Bellman–Ford recurrence (budget = edges, $\le n-1$), negative-cycle detection, $O(nm)$.
• Floyd–Warshall recurrence (budget = intermediate set), $O(n^3)$.

3. Dynamic programming

• What it is. Tabulate solutions to overlapping subproblems (unlike divide & conquer’s disjoint ones), filling cells in an order where each depends only on earlier cells, so each is computed once. Runtime $\approx$ (#subproblems) $\times$ (work per subproblem) + postprocessing — the number of subproblems lower-bounds the runtime.
• The recipe: (1) identify the optimal substructure — express the big solution via smaller ones, usually by casing on the last decision; (2) write the recurrence for the optimal value; (3) compute it bottom-up (nested loops, small problems first) or top-down (recursion + memoization — update the cache before returning); (4) reconstruct the actual solution by backtracking through the table. Mental trick: jump into the middle and imagine being handed the optimal solution up to index $j$.
• 0/1 knapsack — items with weights $w_i$, values $v_i$, capacity $C$; each item used $\le 1$. Let $V[i,c]$ = max value from the first $i$ items at capacity $c$. Casing on item $i$ (skip vs take):

$V[i,c] = \begin{cases} V[i-1,c] & w_i > c \\[2pt] \max\big(V[i-1,c],\ \ V[i-1,\,c-w_i] + v_i\big) & w_i \le c. \end{cases}$

Fill over items then capacities → $O(nC)$; reconstruct by checking whether each $V[i,c]$ came from “above” (skipped) or “up-and-left” (took it). (Unbounded knapsack drops the item index: $K[c] = \max_i\big(K[c - w_i] + v_i\big)$.)

• Numeric anchor: items $(w,v) = (1,1),(3,4),(4,5),(5,7)$, capacity $C=7$. The table fills to $V[4,7] = 9$, achieved by items 2+3 (weight $3{+}4{=}7$, value $4{+}5{=}9$) — beating items 1+4 (value 8). Picture (draw it): the DP grid, rows = items $0..n$ down, columns = capacities $0..C$ across; every cell looks only up (skip item $i$) or up-and-$w_i$-left (take it), so you sweep row by row and read the answer at the bottom-right corner, then follow those two arrows back to recover which items were taken.
• Longest common subsequence — $C[i,j]$ = LCS length of prefixes $X[1..i], Y[1..j]$. Case on the last characters:

$C[i,j] = \begin{cases} 1 + C[i-1, j-1] & X[i] = Y[j] \\[2pt] \max\big(C[i-1,j],\ C[i, j-1]\big) & X[i] \ne Y[j]. \end{cases}$

$O(mn)$ to fill, $O(m+n)$ to recover the subsequence by backtracking.

Core competency set

• State the DP recipe (optimal substructure → recurrence → bottom-up/memoized → reconstruct) and bottom-up vs top-down.
• Derive the 0/1 knapsack and LCS recurrences by casing on the last decision, with their runtimes.

4. Greedy algorithms and minimum spanning trees

• The paradigm. Build a solution with locally-optimal choices, never reconsidering — top-down (choose, then one subproblem remains). Fast and simple, but most greedy algorithms are wrong, so correctness is the whole challenge.
• Exchange argument (the standard correctness proof). Invariant: after $t$ greedy choices, some optimal solution still extends them. Base: before any choice, an optimal solution exists. Step: given an optimal $T^\star$ extending the first $t-1$ choices, if our $t$-th choice $a_k$ differs from $T^\star$‘s, swap it in for $T^\star$‘s element and show the result is still feasible and no worse. At the end no choices remain, so our solution is optimal.
• Activity selection — most non-overlapping activities. Greedily pick the one with the earliest finish time, then repeat among the compatible rest. (Earliest finish leaves the most room; exchange proof: it ends no later than $T^\star$‘s pick, so it can’t conflict with anything $T^\star$ scheduled after.) $O(n\log n)$ (sort by finish).
• Job scheduling — minimize total weighted completion time ($\sum c_i \cdot$ completion-time). Order by the ratio $c_i / t_i$ descending (neither cost nor time alone). Exchange: swapping an adjacent out-of-order pair only lowers cost.
• Huffman codes — a prefix-free binary code minimizing $\sum_x p(x)\,d(x)$ (frequency $\times$ depth). Greedily merge the two least-frequent nodes into a parent (a min-priority queue), repeat. Lemma: the two least-frequent symbols are siblings at max depth in some optimal tree.
• Minimum spanning tree. A spanning tree is an acyclic edge subset connecting all vertices; want minimum total cost. Everything rests on the cut lemma: given a cut (a vertex partition) that respects the chosen edge set $S$ (no $S$-edge crosses it), and the light edge (cheapest crossing the cut), there is an MST containing $S \cup \{\text{light edge}\}$. So you can always safely add the cheapest edge crossing a cut — that’s the greedy choice both MST algorithms make.
  • Prim — grow one tree from a start vertex, repeatedly adding the cheapest edge crossing the frontier (tree $X$ vs $V\setminus X$). Heap-keyed by each outside vertex’s cheapest edge to the tree → $O((m+n)\log n)$. (Like Dijkstra, but the key is edge cost to the tree, not distance to a source.)
  • Kruskal — sort all edges, add the cheapest that doesn’t form a cycle (growing a forest of trees that merge). Cycle check = “are the endpoints already connected?” via union-find.
  • Union-find — maintains a partition; each element points to a parent, Find walks to the root (the set’s name), Union attaches the smaller tree under the larger (union by size) to keep depth $O(\log n)$. A cycle would join two endpoints already sharing a root. This brings Kruskal to $O(m\log n)$.

Core competency set

• State the greedy paradigm and prove correctness by exchange argument (the “extends our choices” invariant).
• Give activity selection (earliest finish), job scheduling (cost/time ratio), Huffman (merge least frequent).
• State the MST cut lemma and how Prim and Kruskal each apply it; explain union-find (Find/Union by size) for cycle detection.

5. Max-flow / min-cut

• Flow network. Directed $G$ with edge capacities $c(u,v) \ge 0$; a flow $f$ obeys the capacity constraint $0 \le f(u,v) \le c(u,v)$ and conservation (in = out at every vertex but $s, t$). Value $|f|$ = net flow out of the source $s$.
• s–t cut $(S,T)$ with $s\in S, t\in T$: its capacity is the sum of capacities of edges $S \to T$ only. Weak duality: any flow $\le$ any cut, since all flow must cross the divide — $|f| \le c(S,T)$.
• Max-flow–min-cut theorem: $\max_f |f| = \min_{\text{cut}} c(S,T)$. The three conditions are equivalent: (1) $f$ is maximum; (2) the residual network has no augmenting path; (3) $|f| = c(S,T)$ for some cut.
• Ford–Fulkerson method. Start $f = 0$; while there’s an augmenting path $s\to t$ in the residual network $G_f$, push the bottleneck residual capacity along it. The residual network has, for each edge, a forward edge of leftover capacity $c - f$ and a reverse edge of capacity $f$ (so flow can be cancelled — sending flow backward undoes an earlier bad choice). Augmenting on a forward edge raises its flow, on a backward edge lowers it. Terminates when $t$ is unreachable from $s$ in $G_f$ — exactly when $f$ is max. With integer capacities, $O(E\,|f^\star|)$ (can be slow for large capacities).
  • Numeric anchor: $s\!\to\!a\,(3),\ s\!\to\!b\,(2),\ a\!\to\!b\,(1),\ a\!\to\!t\,(2),\ b\!\to\!t\,(3)$. Augment $s\,a\,t$ (push 2, saturates $a\!\to\!t$), then $s\,b\,t$ (push 2, saturates $s\!\to\!b$), then $s\,a\,b\,t$ on the residual (push 1) → $|f| = 5$. The cut $S = \{s\}$ has capacity $3 + 2 = 5$, so $\max$-flow $=\min$-cut $= 5$ (and $t$ is now unreachable from $s$ in the residual — the termination certificate). Picture (draw it): the $s$–$t$ network with a dashed vertical cut separating $S$ from $T$ (only forward $S\!\to\!T$ edges count toward capacity); beside it the residual graph — each used edge keeps a forward stub of size $c-f$ and gains a backward arrow of size $f$ for cancellation.
• Edmonds–Karp — choose the augmenting path by BFS (fewest edges); runtime becomes $O(nm^2)$, independent of capacities.
• Bipartite matching as flow. Orient all graph edges $L \to R$, add a source $s \to$ every $L$ and every $R \to t$ sink, all unit capacity. An integer max flow decomposes into disjoint unit $s$–$t$ paths, each a matched pair, so max matching = max flow (and integer capacities guarantee an integer/0–1 flow). The model fits assignment problems generally.
• Project selection (min-cut application): infinite-capacity edges from prerequisite to task can never be cut; connect $s\to$ positive-reward tasks and negative-reward tasks $\to t$; the min cut selects the optimal feasible subset.
• Global min cut — Karger (undirected, the fewest edges whose removal disconnects $G$; not an $s$–$t$ cut). Contraction algorithm: repeatedly pick a random edge and contract it (merge its endpoints into a supernode, keeping parallel edges) until two supernodes remain — they define a cut. A Monte Carlo algorithm (always fast, sometimes wrong — it fails iff it ever contracts a min-cut edge).
  • Success probability $\ge 1/\binom n2$: if the min cut has size $k$, every vertex has degree $\ge k$, so $G$ has $\ge nk/2$ edges; after $i-1$ contractions $\ge (n-i+1)k/2$ edges remain, so the chance of contracting a min-cut edge is $\le \tfrac{k}{(n-i+1)k/2} = \tfrac{2}{n-i+1}$. The product of survival probabilities telescopes:

$\prod_{i=1}^{n-2}\Big(1 - \tfrac{2}{n-i+1}\Big) = \frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdots\frac{1}{3} = \frac{2}{n(n-1)} = \frac{1}{\binom n2}.$

Repeat $\binom n2 \ln(1/\delta)$ times to fail with probability $\le \delta$ (since $(1-p)^T \le e^{-pT}$). Karger–Stein notices early contractions are safe and only re-runs the risky late stages, recursing once the graph is down to $n/\sqrt2$ nodes: $O(n^2\log^2 n)$.

Core competency set

• Define a flow, an $s$–$t$ cut, and state weak duality and the max-flow–min-cut theorem (three equivalences).
• Explain Ford–Fulkerson with residual graphs (forward + reverse/cancellation edges) and Edmonds–Karp’s BFS choice.
• Model bipartite matching as unit-capacity flow; state Karger’s contraction and derive $P(\text{success}) \ge 1/\binom n2$.

6. Stable matching

• Setup. $n$ doctors, $n$ hospitals, each with a strict preference list. A blocking pair $(i,j)$ both prefer each other to their assignments — they’d defect. A stable matching has no blocking pair (no pair can profitably subvert it).
• Gale–Shapley (deferred acceptance), $O(n^2)$: while some doctor is unmatched, that doctor proposes to the next hospital on its list; each hospital tentatively holds its best offer so far and rejects the rest. It looks greedy, but acceptances are revocable — a hospital can drop a tentatively-held doctor for a better proposal, which is what lets it escape bad early commitments.
  • Always produces a stable matching. It is proposer-optimal (every doctor gets the best hospital it could have in any stable matching) and simultaneously receiver-worst — the proposing side has no incentive to misreport, the other side sometimes does.
  • Rural-hospital theorem: a hospital left unfilled in one stable matching is matched to the exact same set of doctors in every stable matching.

Core competency set

• Define blocking pair and stable matching; give the Gale–Shapley procedure and why “deferred/revocable” matters.
• State proposer-optimal = receiver-worst and the strategy-proofness of the proposing side.

7. Memorize cold

• DFS/BFS $O(n+m)$. Topo sort = decreasing finish time (DAG). BFS layer = unweighted distance; bipartite ⇔ no odd cycle.
• SCC / Kosaraju: DFS finish times → reverse edges → DFS by decreasing finish time; trees = SCCs. SCC graph is a DAG.
• Dijkstra (greedy, nonneg) $O((m+n)\log n)$. Bellman–Ford (DP, neg edges) $d^{(i+1)}(s,v)=\min_u(d^{(i)}(s,u)+w(u,v))$, $\le n-1$ edges, $O(nm)$, detects neg cycles. Floyd–Warshall (APSP) $D^{(k)}[u,v]=\min(D^{(k-1)}[u,v], D^{(k-1)}[u,k]+D^{(k-1)}[k,v])$, $O(n^3)$.
• DP recipe: optimal substructure → recurrence → bottom-up/memoize → reconstruct. 0/1 knapsack $V[i,c]=\max(V[i-1,c], V[i-1,c-w_i]+v_i)$, $O(nC)$. LCS $C[i,j]=1+C[i-1,j-1]$ or $\max(C[i-1,j],C[i,j-1])$, $O(mn)$.
• Greedy = exchange argument (“after $t$ choices an optimal solution still extends them”). Activity selection = earliest finish; job scheduling = $c_i/t_i$ ratio; Huffman = merge two least frequent.
• MST cut lemma: cheapest edge crossing a cut respecting $S$ is in some MST. Prim (grow one tree, $O((m+n)\log n)$); Kruskal (sort, add acyclic, $O(m\log n)$ with union-find: Find→root, Union by size).
• Max-flow = min-cut. Ford–Fulkerson: augment along residual paths (forward $c-f$ + reverse $f$ for cancellation). Edmonds–Karp (BFS) $O(nm^2)$. Bipartite matching = unit-capacity flow.
• Karger: contract random edges to 2 supernodes; $P(\text{success})\ge 1/\binom n2$; repeat $\binom n2\ln(1/\delta)$; Karger–Stein $O(n^2\log^2 n)$. Monte Carlo.
• Gale–Shapley: propose / tentatively-hold / reject; stable, proposer-optimal = receiver-worst; $O(n^2)$.

Named moves (cross-track glossary): graph-in-disguise (model it as vertices + edges); finish-time-ordering (DFS → topo sort & SCC); BFS-layer-is-distance; greedy-finalize (Dijkstra/Prim extract the safe-closest); budget-the-output (Bellman–Ford: paths with $\le i$ edges); intermediate-set-recursion (Floyd–Warshall); optimal-substructure-then-memoize (DP, vs 13a’s disjoint divide & conquer); case-on-the-last-decision (knapsack/LCS recurrences); exchange-argument (greedy correctness); cut-lemma (the MST safe edge); union-find-for-cycles; residual-graph + augmenting-path + cancellation (flow); max-flow=min-cut (the duality, cf. LP duality track 10); matching-as-unit-flow; contract-random-edges (Karger, Monte Carlo — cf. 13a Las Vegas vs Monte Carlo); defer-acceptance (revocable greedy, Gale–Shapley).