Read this right before the exam. You can't bring it in, so it's for memorizing, not for reference.
| Question says | Do |
|---|
| "pre and post numbers", "alphabetically first" | DFS with a clock starting at 1. Outer loop and neighbor lists both in alphabetical order. Write a pre/post table. |
| "classify each edge" | u→v: tree if the DFS went there; forward if pre(u)<pre(v), post(v)<post(u) and not tree; back if v is an ancestor (pre(v)<pre(u), post(u)<post(v)); cross if post(v)<pre(u). Undirected graphs have only tree and back edges. |
| "topological ordering" | Decreasing post. Count orderings by multiplying the choices at each "free" level. |
| "strongly connected components" | DFS on GR → list vertices by decreasing post → explore in G in that order. Each explore outputs one SCC (sink SCCs first). Edges to add = max(#source SCCs, #sink SCCs), or 0 if there's one SCC. |
| "Dijkstra … show the table" | One column per deleteMin. Ties alphabetical. Only update vertices not yet removed. Final: prev pointers = the shortest-path tree. |
| "Bellman–Ford" | Update every edge, |V|−1 rounds. One more round: anything changes ⇒ negative cycle. |
| "negative edges", "Dijkstra fails" | Example: S→A 2, S→B 3, B→A −2. Dijkstra finalizes A = 2; truth is 1. |
| "add a constant to every edge" | Fails: it penalizes paths with more edges. Example: u→v −2, v→w 2, u→w 2. Add 3: the best path to w flips from u→v→w to u→w. |
| "unique / count / fewest-edge shortest paths" | Dijkstra plus a tie branch: if d[u]+ℓ < d[v]: copy from u; elif equal: combine (usp=false / count += / best = min). |
| "DAG", "longest path", "schedule" | Topological order, one pass of updates. O(V+E). Longest path = max instead of min. |
| "exchange rates", "arbitrage" | Weight −log r. Best conversion = shortest path (Bellman–Ford). Arbitrage = negative cycle. |
| "MST cost / how many MSTs / Kruskal order" | Sort edges and add unless it makes a cycle. Count MSTs by looking at ties: equal-weight edges that could swap. |
| "give a cut that justifies" | S = the current component of one endpoint; V−S = the rest. The added edge is the lightest crossing it. |
| "Prim … cost array" | Like Dijkstra, but cost(v) = lightest edge from the tree to v (not distance from s). |
| "Huffman" | Merge the two smallest, repeat. Bits = Σ freq × depth = sum of all merge totals. |
| "show greedy may fail" | Small concrete counterexample. Show greedy's answer, then a better one. |
| "prove greedy is optimal" | Exchange argument: take OPT, swap in the greedy choice, show it's no worse, induct on the rest. |
| "dynamic programming algorithm" | Subproblem in words → recurrence (guess the last choice) → base cases → fill order → answer location → time = #subproblems × work each. |
| Problem | Subproblem | Recurrence | Time |
|---|
| LIS | L(j) = longest increasing subsequence ending at j | 1 + max{L(i): i<j, ai<aj} | O(n²) |
| Edit distance | E(i,j) on prefixes | min(E(i−1,j)+1, E(i,j−1)+1, E(i−1,j−1)+diff) | O(mn) |
| LCS | c[i,j] on prefixes | match: c[i−1,j−1]+1; else max(c[i−1,j], c[i,j−1]) | O(mn) |
| 0/1 knapsack | B[k,w]: items 1..k, capacity w | max(B[k−1,w], B[k−1,w−wk]+bk) | O(nW), pseudo-poly |
| Knapsack with repetition | K(w) | maxi: wi≤w K(w−wi)+vi | O(nW) |
| Chain matrix | C(i,j) on intervals | mink C(i,k)+C(k+1,j)+mi−1mkmj | O(n³) |
| Weighted intervals | OPT(k), sorted by finish time | max(OPT(k−1), wk+OPT(p(k))) | O(n log n) |
| Tree independent set | in(u), out(u) | in = w(u)+Σout(c); out = Σmax(in(c), out(c)) | O(n) |
| Max contiguous sum (6.1) | S(j) = best sum ending at j | max(aj, S(j−1)+aj), answer max(0, max S) | O(n) |
| Hotels (6.2 / HW4 P7) | P(j) = min penalty stopping at hotel j | mini<j P(i) + (300 − (aj−ai))² | O(n²) |
| Rod cutting, cut cost c (HW4 P6) | r(n) | max(pn, maxi<n pi+r(n−i)−c) | O(n²) |
| Binomial | C(n,k) | C(n−1,k−1)+C(n−1,k) | O(nk) |