Computer Science › Algorithms & Software
A problem qualifies for dynamic programming when it has overlapping subproblems (naive recursion redoes the same work over and over) and optimal substructure (an optimal solution is built from optimal solutions to its subproblems).
Take the exact naive recursive solution already familiar, cache each subproblem's answer the first time it's computed, and reuse it instead of recomputing — turning exponential time into polynomial with one small change.
Instead of recursing downward and caching along the way, fill a table of subproblem answers starting from the smallest and building up — the same subproblems, computed in the opposite direction, with no recursion at all.
Finding the longest sequence appearing (in order, not necessarily contiguously) in both of two strings — a two-dimensional table filled from a two-way recurrence, the canonical worked example of DP with more than one shrinking dimension.
Choosing which items to pack, each either fully taken or fully left behind, to maximize value under a weight limit — the canonical worked example of DP where greedy provably fails and a full table is required.
Finding the longest strictly increasing subsequence of a list — a one-dimensional DP whose naive O(n²) solution hides an O(n log n) speed-up built on the searching techniques already covered.
A directed graph with a capacity on every edge, a source, and a sink; a valid flow must respect capacity and conserve flow at every other vertex, and max-flow asks for the assignment of largest possible value.
The residual graph tracks unused forward capacity plus a backward "undo" edge for flow already sent; the method repeatedly finds an augmenting path through it and pushes flow equal to the path's bottleneck.
The value of any flow never exceeds the capacity of any s-t cut, and the maximum flow value always equals the minimum cut's capacity exactly, proven via Ford-Fulkerson's own termination point.
Always choosing the shortest augmenting path, found by BFS on the residual graph, bounds the number of iterations to O(V·E) regardless of edge capacities, giving an overall O(V·E²) running time.
Exploring a graph level by level with a queue, from a chosen source — the algorithm that finds shortest paths, measured in number of edges, in any unweighted graph.
Exploring a graph by plunging as deep as possible before backtracking — a different traversal order than BFS, naturally recursive, and the foundation for cycle detection and topological ordering.
DFS timestamps reveal a cycle the instant one exists, and — when there isn't one — the same traversal produces a valid dependency order for every vertex in a directed acyclic graph.
Once edges carry weights, BFS's "fewest edges" answer stops being the same as "cheapest path" — the setup that motivates every shortest-path algorithm that follows.
Always expanding the closest not-yet-finalized vertex next, using the binary heap already covered as its priority queue — correct whenever every edge weight is non-negative.
Dijkstra's algorithm breaks the instant an edge weight goes negative — Bellman-Ford trades speed for correctness in that case, and can even detect a negative-weight cycle that makes "shortest path" meaningless.
When the graph is guaranteed acyclic, the topological order already covered lets shortest paths be computed in a single linear pass — no priority queue, no repeated relaxation, faster than either general algorithm.
Running BFS from every not-yet-visited vertex partitions an undirected graph into its connected components — a direct, practical payoff of the traversal just covered.
Building a solution by always taking the locally best-looking choice and never reconsidering it — a strategy that is sometimes provably optimal and sometimes simply wrong, with no way to tell which without a proof.
Connecting every vertex of a weighted graph as cheaply as possible, using exactly the spanning-tree structure already covered in discrete math, now with a cost to minimize.
Sort every edge by weight and add each one greedily, skipping any that would close a cycle — a connectivity check answered instantly by the union-find structure already covered.
A second, equally correct way to grow a minimum spanning tree — one vertex at a time from a single starting point, always adding the cheapest edge leaving the tree so far, using the same heap Dijkstra's algorithm relies on.
Scheduling the maximum number of non-overlapping activities by always picking the one that finishes earliest — and a full exchange-argument proof that this greedy choice never costs you the optimal solution.
Solving a problem by breaking it into smaller instances of itself, solving each independently, and combining their results — the general pattern recursion already introduced, now studied as a design strategy in its own right.
Binary search's divide-and-conquer idea generalizes past a plain sorted array — searching a rotated sorted array in O(log n) is a genuinely different, worth-solving puzzle built on the exact same pattern.
Turning a divide-and-conquer algorithm's self-referential running time — T(n) = 2T(n/2) + O(n), for example — into a closed-form bound, by recursion trees and pattern-matching against a few canonical shapes.
The same merge sort already met as one option among several — now studied rigorously as the canonical divide-and-conquer algorithm, with its T(n) = 2T(n/2) + O(n) recurrence solved in full.
A different divide-and-conquer sort — pick a pivot, partition everything smaller to its left and everything larger to its right, then recurse on each side — all done in place, unlike merge sort.
Quicksort's worst case is O(n²) on an already-sorted or adversarial input, but choosing the pivot at random makes that worst case astronomically unlikely, giving expected O(n log n) on any input.
Why no algorithm that sorts purely by comparing elements can beat O(n log n) in the worst case — a genuine impossibility proof, via a decision-tree argument, not just an unmet goal.
Both hit the O(n log n) lower bound on average, but for genuinely different reasons and with genuinely different trade-offs — in-place vs. extra memory, stable vs. not, worst-case guarantee vs. expected performance.
A closing, side-by-side guide across every paradigm covered — divide-and-conquer, greedy, and dynamic programming — organized by the tell-tale signs that point to each one, and worked through on problems that could plausibly go more than one way.
Part of the Computer Science curriculum.
A problem qualifies for dynamic programming when it has overlapping subproblems (naive recursion redoes the same work over and over) and optimal substructure (an optimal solution is built from optimal solutions to its subproblems).
Take the exact naive recursive solution already familiar, cache each subproblem's answer the first time it's computed, and reuse it instead of recomputing — turning exponential time into polynomial with one small change.
Instead of recursing downward and caching along the way, fill a table of subproblem answers starting from the smallest and building up — the same subproblems, computed in the opposite direction, with no recursion at all.
Finding the longest sequence appearing (in order, not necessarily contiguously) in both of two strings — a two-dimensional table filled from a two-way recurrence, the canonical worked example of DP with more than one shrinking dimension.
Choosing which items to pack, each either fully taken or fully left behind, to maximize value under a weight limit — the canonical worked example of DP where greedy provably fails and a full table is required.
Finding the longest strictly increasing subsequence of a list — a one-dimensional DP whose naive O(n²) solution hides an O(n log n) speed-up built on the searching techniques already covered.
A directed graph with a capacity on every edge, a source, and a sink; a valid flow must respect capacity and conserve flow at every other vertex, and max-flow asks for the assignment of largest possible value.
The residual graph tracks unused forward capacity plus a backward "undo" edge for flow already sent; the method repeatedly finds an augmenting path through it and pushes flow equal to the path's bottleneck.
The value of any flow never exceeds the capacity of any s-t cut, and the maximum flow value always equals the minimum cut's capacity exactly, proven via Ford-Fulkerson's own termination point.
Always choosing the shortest augmenting path, found by BFS on the residual graph, bounds the number of iterations to O(V·E) regardless of edge capacities, giving an overall O(V·E²) running time.
Exploring a graph level by level with a queue, from a chosen source — the algorithm that finds shortest paths, measured in number of edges, in any unweighted graph.
Exploring a graph by plunging as deep as possible before backtracking — a different traversal order than BFS, naturally recursive, and the foundation for cycle detection and topological ordering.
DFS timestamps reveal a cycle the instant one exists, and — when there isn't one — the same traversal produces a valid dependency order for every vertex in a directed acyclic graph.
Once edges carry weights, BFS's "fewest edges" answer stops being the same as "cheapest path" — the setup that motivates every shortest-path algorithm that follows.
Always expanding the closest not-yet-finalized vertex next, using the binary heap already covered as its priority queue — correct whenever every edge weight is non-negative.
Dijkstra's algorithm breaks the instant an edge weight goes negative — Bellman-Ford trades speed for correctness in that case, and can even detect a negative-weight cycle that makes "shortest path" meaningless.
When the graph is guaranteed acyclic, the topological order already covered lets shortest paths be computed in a single linear pass — no priority queue, no repeated relaxation, faster than either general algorithm.
Running BFS from every not-yet-visited vertex partitions an undirected graph into its connected components — a direct, practical payoff of the traversal just covered.
Building a solution by always taking the locally best-looking choice and never reconsidering it — a strategy that is sometimes provably optimal and sometimes simply wrong, with no way to tell which without a proof.
Connecting every vertex of a weighted graph as cheaply as possible, using exactly the spanning-tree structure already covered in discrete math, now with a cost to minimize.
Sort every edge by weight and add each one greedily, skipping any that would close a cycle — a connectivity check answered instantly by the union-find structure already covered.
A second, equally correct way to grow a minimum spanning tree — one vertex at a time from a single starting point, always adding the cheapest edge leaving the tree so far, using the same heap Dijkstra's algorithm relies on.
Scheduling the maximum number of non-overlapping activities by always picking the one that finishes earliest — and a full exchange-argument proof that this greedy choice never costs you the optimal solution.
Solving a problem by breaking it into smaller instances of itself, solving each independently, and combining their results — the general pattern recursion already introduced, now studied as a design strategy in its own right.
Binary search's divide-and-conquer idea generalizes past a plain sorted array — searching a rotated sorted array in O(log n) is a genuinely different, worth-solving puzzle built on the exact same pattern.
Turning a divide-and-conquer algorithm's self-referential running time — T(n) = 2T(n/2) + O(n), for example — into a closed-form bound, by recursion trees and pattern-matching against a few canonical shapes.
The same merge sort already met as one option among several — now studied rigorously as the canonical divide-and-conquer algorithm, with its T(n) = 2T(n/2) + O(n) recurrence solved in full.
A different divide-and-conquer sort — pick a pivot, partition everything smaller to its left and everything larger to its right, then recurse on each side — all done in place, unlike merge sort.
Quicksort's worst case is O(n²) on an already-sorted or adversarial input, but choosing the pivot at random makes that worst case astronomically unlikely, giving expected O(n log n) on any input.
Why no algorithm that sorts purely by comparing elements can beat O(n log n) in the worst case — a genuine impossibility proof, via a decision-tree argument, not just an unmet goal.
Both hit the O(n log n) lower bound on average, but for genuinely different reasons and with genuinely different trade-offs — in-place vs. extra memory, stable vs. not, worst-case guarantee vs. expected performance.
A closing, side-by-side guide across every paradigm covered — divide-and-conquer, greedy, and dynamic programming — organized by the tell-tale signs that point to each one, and worked through on problems that could plausibly go more than one way.