Tag
dynamic-programming
- Jul 5, 2026 Recurrences as DAGs: Why Optimal Substructure Makes Tables Work How a recurrence defines a graph of states, why overlapping subproblems collapse an exponential recursion tree into a polynomial one, and where the optimal-substructure argument fails. algorithms
- Feb 10, 2026 Join Order Search and the Explosion of the Plan Space Left-deep and bushy trees, why the search is NP-hard, and the pruning rules that keep a twenty-table join tractable. databases
- Feb 5, 2026 Connectionist Temporal Classification and Monotonic Alignment How a blank symbol and a collapse rule turn frame-by-frame predictions into a sequence probability, why the sum over alignments needs a lattice recursion, and what the independence assumption costs. deep learning
- Jan 29, 2026 Edit Distance and the Shape of a Two-Dimensional Table How the Levenshtein recurrence fills a grid, why three neighbouring cells are enough, and how the band and Hirschberg variants trade the full matrix for time and reconstruction ability. algorithms
- Nov 17, 2025 Longest Increasing Subsequence and the Tails Array Invariant The O(n log n) patience-sorting method keeps one number per length instead of a full two-dimensional table, and the invariant explaining why is a dominance argument. algorithms
- Oct 30, 2025 Floyd-Warshall, Johnson Reweighting, and the All-Pairs Choice Two all-pairs methods with opposite preconditions: one tolerates negative edges through a triple loop, the other restores nonnegativity by changing the weights and then runs Dijkstra from every vertex. algorithms
- Dec 19, 2024 Maximal Munch and Dynamic-Programming Tiling Two ways to choose which instruction patterns cover an expression tree, why greedy top-down matching can be arbitrarily bad, and what the optimal algorithm costs to run. compilers
- Nov 27, 2024 Chomsky Normal Form and the CYK Table How rewriting a grammar so every rule is A to BC or A to a makes cubic-time recognition possible, and why the table is indexed by substrings rather than by derivation prefixes. computation theory
- Nov 19, 2024 Interval DP: Choosing the Last Operation Instead of the First Why splitting a contiguous range at its final split point turns exponential enumeration into an O(n cubed) table, and how the quadrangle inequality later removes a factor of n. algorithms
- Oct 20, 2024 Memoization Mechanics: Cache Keys, Laziness, and Recursion Depth How top-down memoization turns a recursion tree into a DAG, what the cache key must contain to be sound, and why the lazy traversal sometimes loses to a full table. algorithms
- Aug 4, 2024 Pseudo-Polynomial Knapsack: Why the Capacity State Is Not Polynomial The O(nW) knapsack table is polynomial in the capacity value and exponential in its bit length, which is why the problem stays NP-hard and why scaling the weights yields an approximation scheme. algorithms
- Jul 16, 2024 State Sufficiency: What the Past Must Leave Behind How to decide which facts about a partial solution a DP state must record, why insufficient states produce wrong answers rather than slow ones, and what each extra dimension costs. algorithms