Dynamic programming (Algorithms)

Cheat sheets

ALG-15Cheat sheet1 pageIn a paid pack

DP Foundations, LCS and Edit Distance

Optimal substructure and overlapping subproblems; memoisation versus tabulation with the exact call count of naive Fibonacci; a four-step routine for designing any DP and its cost formula; longest common subsequence with its recurrence, a filled table with arrows and traceback for GATE and GREAT, tie rules and space saving; longest common substring as a different DP; edit distance with its recurrence, base cases and a filled table, plus its relation to LCS when only insertions and deletions are allowed.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

Diagrams from ALG-15

LCS table for X = GATE (rows) and Y = GREAT (columns) with values L[i][j] and arrows: diagonal on a match, up or left otherwise. The traceback from L[4][5] = 3 passes cells (4,5), (3,5), (2,4), (1,3), (1,2), (1,1); matches T, A, G give LCS GAT. — LCS table for GATE and GREAT; traceback cells outlined. Source: sheet ALG-15.

ALG-16Cheat sheet1 pageIn a paid pack

Knapsack, Subset Sum and Coin Change

0/1 knapsack with its recurrence and a fully filled table, the one-array version and why the capacity loop runs downward, unbounded knapsack by running it upward; why O(nW) is pseudo-polynomial; subset sum as a boolean table with every reachable sum per row and the subsets that hit the target; counting coin combinations versus ordered sequences and how the loop order decides which one you get; minimum number of coins with unreachable amounts. All tables are produced by script.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

ALG-17Cheat sheet1 pageIn a paid pack

Matrix Chain and Increasing Subsequences

Matrix-chain multiplication: the cost of one product, the interval recurrence, the m and s tables filled by chain length for four matrices with the optimal parenthesisation read from s, every order's cost compared, the Catalan count of parenthesisations, and time and space; longest increasing subsequence by the quadratic DP and by the n log n tails method with a full trace, why the tails array is not itself a subsequence, and the link to LCS; a summary of DP problems with states, recurrences and costs.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.