Algorithm Design: Greedy, Divide & Conquer, Dynamic Programming

The three design techniques are usually taught as three separate toolkits. They are better understood as three answers to a single question.

When a problem breaks into subproblems, what is the relationship between those subproblems?

If the subproblems are independent, use divide and conquer. Solve each once, combine the answers, and nothing is computed twice because nothing overlaps.

If the subproblems overlap, use dynamic programming. The same subproblem is reached by many different paths, so solving it repeatedly is exponentially wasteful and storing the answer is the entire optimisation.

If one choice is provably safe, use greedy. There is then only one subproblem to consider at each step, and no comparison of alternatives is needed at all.

So the diagnostic question is always: do the subproblems overlap, and can I prove a choice is safe? Answering those two settles which technique applies, and getting the answer wrong is what produces an exponential algorithm for a polynomial problem, or a fast algorithm that returns wrong answers.

1. Divide and Conquer

The pattern has three steps: divide the problem into subproblems, conquer them recursively, and combine their solutions.

The defining property is that the subproblems are disjoint. Merge sort's two halves share no elements, so no work is duplicated and the recursion tree has no repeated nodes.

The cost is a recurrence of the form $T(n)=aT(n/b)+f(n)$, solved by the master theorem.

Strassen's algorithm is the standard illustration of why the branching factor matters. Naive matrix multiplication does 8 recursive multiplications of half-sized matrices, giving ${\log }_{2}8=3$ and the familiar $O(n^3)$. Strassen restructures the arithmetic to use only 7, giving ${\log }_{2}7\approx 2.81$.

The saving comes entirely from reducing $a$ from 8 to 7, at the cost of more additions — which are cheaper and do not affect the exponent.

2. Dynamic Programming

Dynamic programming applies when two conditions hold together.

Optimal substructure: an optimal solution contains optimal solutions to its subproblems. Overlapping subproblems: the same subproblem is solved many times by naive recursion.

Both are required. Optimal substructure alone permits divide and conquer; overlap alone without optimal substructure means the stored answers are not reusable.

The canonical demonstration is Fibonacci. Naive recursion computes $F(n-2)$ twice, $F(n-3)$ three times, and so on, giving exponential total work — yet there are only $n$ distinct subproblems. Storing each result makes the algorithm linear.

That gap between the number of distinct subproblems and the number of recursive calls is exactly what dynamic programming recovers.

Two implementations exist and are examined as a contrast.

Memoisation is top-down: write the natural recursion and cache each result the first time it is computed. It solves only the subproblems actually reachable, and its overhead is recursion and hashing.

Tabulation is bottom-up: fill a table in an order guaranteeing that every dependency is already computed. It has no recursion overhead and better locality, but it solves every subproblem whether needed or not.

Tabulation also permits space optimisation that memoisation cannot. If each row of the table depends only on the previous row, two rows suffice and the space drops from $O(nW)$ to $O(W)$.

3. The Classic Dynamic Programs

Each classic problem is defined by its state and its recurrence, and knowing those two is knowing the problem.

0/1 knapsack. State is (item index, remaining capacity). The recurrence chooses the better of taking the item and skipping it:

$V[i][w]=\max (V[i-1][w],v_i+V[i-1][w-w_i])$

Cost is $O(nW)$. This is pseudo-polynomial, not polynomial, because $W$ is a value rather than an input length — writing $W$ takes only $\log W$ bits, so the cost is exponential in the input size.

Longest common subsequence. State is (position in first string, position in second). Matching characters extend the subsequence; mismatches take the better of two skips. Cost is $O(mn)$.

Edit distance. State is the same, with three operations — insert, delete, replace — each costing one. Cost is $O(mn)$.

Matrix chain multiplication. State is (start, end) of a subchain, and the recurrence tries every split point. Cost is $O(n^3)$ because there are $O(n^2)$ states each taking $O(n)$ to evaluate.

Longest increasing subsequence. The straightforward dynamic program is $O(n^2)$; a patience-sorting formulation using binary search achieves $O(n\log n)$.

Coin change. Counting the minimum coins needed is $O(nA)$ for $n$ denominations and amount $A$, and it is a dynamic program precisely because greedy fails on general denominations.

4. Greedy Algorithms

A greedy algorithm makes the locally best choice at each step and never reconsiders.

It needs optimal substructure, like dynamic programming, plus the greedy choice property: a globally optimal solution can be reached by making the locally optimal choice.

That second condition is what must be proved, and it is what fails for most problems. The usual proof technique is an exchange argument: take any optimal solution, show it can be transformed into one containing the greedy choice without becoming worse, and conclude the greedy choice is safe.

Greedy is faster than dynamic programming when it works, because it considers one option per step rather than all of them. The risk is that it silently returns a wrong answer when the property does not hold.

The knapsack pair is the canonical contrast and appears constantly. Fractional knapsack is greedy by value-to-weight ratio and runs in $O(n\log n)$; 0/1 knapsack is a dynamic program at $O(nW)$. The only difference is whether items can be split, and that single difference changes the technique entirely.

5. Why Greedy Fails on 0/1 Knapsack

The failure is worth seeing concretely, because it shows what the greedy choice property actually asserts.

Take a capacity of 10 and three items: A with value 60 and weight 10 (ratio 6), B with value 100 and weight 6 (ratio 16.7), and C with value 50 and weight 4 (ratio 12.5).

Greedy by ratio takes B first, using 6 of the capacity. Then C fits in the remaining 4, giving total value 150 and using the full capacity — which here happens to be optimal.

Change C's weight to 5. Greedy takes B (weight 6), then C no longer fits in the remaining 4, so it tries A, which also does not fit. Total value 100.

The optimal solution takes A alone, for value 60 — worse. So change A's value to 140: now greedy still takes B for 100, while taking A alone gives 140.

Greedy fails because taking the highest-ratio item consumed capacity that a lower-ratio but higher-value item needed. In the fractional version this cannot happen, since the leftover capacity is always filled by a fraction of the next item.

6. Classic Greedy Algorithms

Activity selection chooses the maximum number of non-overlapping activities. Sorting by earliest finishing time and taking greedily is optimal, and the exchange argument is short: the activity finishing earliest leaves the largest remaining interval, so swapping it into any optimal solution cannot reduce the count.

Sorting by earliest start or by shortest duration both fail, which is a standard multiple-choice distractor.

Huffman coding builds an optimal prefix-free code by repeatedly merging the two least frequent symbols. The greedy choice is safe because the two least frequent symbols must be siblings at the greatest depth in some optimal tree.

Job sequencing with deadlines schedules unit-time jobs to maximise profit, taking jobs in decreasing profit order and placing each as late as its deadline allows.

Minimum spanning tree algorithms are greedy in two different ways. Kruskal's adds the globally cheapest edge that does not form a cycle; Prim's grows a single tree by adding its cheapest outgoing edge. Both are justified by the cut property.

Dijkstra's algorithm is greedy over vertices, finalising the closest unfinalised vertex at each step. It requires non-negative weights, because a negative edge could reduce a distance already declared final.

7. Choosing Between the Three

The decision procedure is short.

First ask whether the subproblems overlap. If a naive recursion would recompute the same subproblem, dynamic programming is indicated. If not, divide and conquer suffices.

Then ask whether a locally optimal choice can be proved safe. If yes, greedy is faster and simpler. If the proof fails, or a counterexample exists, dynamic programming is required.

The cost ordering is usually greedy, then divide and conquer, then dynamic programming, and the applicability ordering is the reverse: dynamic programming works whenever greedy does, but not conversely.

A useful sanity check is to test a greedy idea on a small adversarial input before trusting it. Most greedy failures show up on three or four elements.

8. Worked Examples

Example 1. Solve the 0/1 knapsack problem with capacity 5 and items of (weight, value) $(2,3),(3,4),(4,5),(5,6)$.

Build the table $V[i][w]$ where $i$ indexes items considered and $w$ is capacity.

With no items, every entry is 0.

Item 1, weight 2, value 3. For $w\ge 2$ the value is 3; below that, 0. Row: 0, 0, 3, 3, 3, 3.

Item 2, weight 3, value 4. At $w=3$, choose between skipping (3) and taking ($4+V[1][0]=4$), so 4. At $w=4$, skip gives 3, take gives $4+V[1][1]=4$, so 4. At $w=5$, skip gives 3, take gives $4+V[1][2]=4+3=7$, so 7. Row: 0, 0, 3, 4, 4, 7.

Item 3, weight 4, value 5. At $w=4$, skip gives 4, take gives $5+V[2][0]=5$, so 5. At $w=5$, skip gives 7, take gives $5+V[2][1]=5$, so 7. Row: 0, 0, 3, 4, 5, 7.

Item 4, weight 5, value 6. At $w=5$, skip gives 7, take gives $6+V[3][0]=6$, so 7. Row: 0, 0, 3, 4, 5, 7.

The maximum value is 7, achieved by taking items 1 and 2 with total weight 5.

Note that the greedy ratio ordering would have picked item 1 (ratio 1.5) then item 2 (ratio 1.33) — which happens to give the same answer here. The table is what guarantees it.

Example 2. Solve the same instance as fractional knapsack.

Compute the value-to-weight ratios: $3/2=1.5$, $4/3\approx 1.33$, $5/4=1.25$, $6/5=1.2$.

Sort descending and fill greedily.

Take item 1 entirely: weight 2, value 3. Remaining capacity 3.

Take item 2 entirely: weight 3, value 4. Remaining capacity 0.

Total value 7, the same as the 0/1 answer because the capacity happened to be filled exactly by whole items.

Change the capacity to 6 to see the difference. Fractional takes items 1 and 2 fully (weight 5, value 7) and then $1/4$ of item 3, adding $5/4=1.25$ for a total of 8.25. The 0/1 version cannot split item 3, so it must choose between items 1 and 2 (value 7) or items 2 and 3 (weight 7, too heavy) or items 1 and 3 (weight 6, value 8) — giving 8.

The fractional answer is always at least the 0/1 answer, and the gap is exactly what splitting buys.

Example 3. Find the length of the longest common subsequence of AGGTAB and GXTXAYB.

Build a table $L[i][j]$ for prefixes of lengths $i$ and $j$.

When characters match, $L[i][j]=L[i-1][j-1]+1$. When they do not, $L[i][j]=\max (L[i-1][j],L[i][j-1])$.

Working through: the common characters that can be aligned in order are G, T, A, B.

Check that this is a genuine subsequence of both. In AGGTAB, the positions of G, T, A, B are 2, 4, 5, 6 — increasing. In GXTXAYB, they are 1, 3, 5, 7 — also increasing.

The length is 4.

The cost is $O(mn)=6\times 7=42$ table entries.

Why is this not greedy? A greedy match of the first common character would take G at position 2 of the first string and position 1 of the second, which happens to work here. But matching the first A of AGGTAB against the A of GXTXAYB would consume the A too early and lose the G, giving a shorter result. Only the table considers both branches.

Example 4. Six activities have (start, finish) times $(1,4),(3,5),(0,6),(5,7),(8,9),(5,9)$. Select the maximum number that do not overlap.

Sort by finishing time: $(1,4),(3,5),(0,6),(5,7),(8,9),(5,9)$.

Take $(1,4)$, the earliest finisher. Current time 4.

$(3,5)$ starts at 3, before 4, so it conflicts. Skip.

$(0,6)$ starts at 0, conflicts. Skip.

$(5,7)$ starts at 5, after 4. Take it. Current time 7.

$(8,9)$ starts at 8, after 7. Take it. Current time 9.

$(5,9)$ starts at 5, conflicts. Skip.

Three activities are selected: $(1,4),(5,7),(8,9)$.

Sorting by start time would have taken $(0,6)$ first, blocking both $(1,4)$ and $(3,5)$ and leaving only $(8,9)$ — two activities instead of three. Sorting by duration would have taken $(8,9)$ first at duration 1, then $(1,4)$, then $(5,7)$ — three here, but that rule fails on other instances.

Only earliest-finish is provably optimal, and the reason is that it leaves the largest possible remaining interval at every step.

Example 5. Build a Huffman code for symbols with frequencies A:5, B:9, C:12, D:13, E:16, F:45. Give the total encoded length.

Repeatedly merge the two smallest frequencies.

Merge A(5) and B(9) into a node of 14. Remaining: 12, 13, 14, 16, 45.

Merge 12 and 13 into 25. Remaining: 14, 16, 25, 45.

Merge 14 and 16 into 30. Remaining: 25, 30, 45.

Merge 25 and 30 into 55. Remaining: 45, 55.

Merge 45 and 55 into 100, the root.

Now read the depths. F is a child of the root at depth 1. C and D are at depth 3, under the 25 node. E is at depth 3, under the 30 node. A and B are at depth 4, under the 14 node.

Total encoded bits: $45(1)+12(3)+13(3)+16(3)+5(4)+9(4)=45+36+39+48+20+36=224$ bits.

A fixed-length code would need 3 bits per symbol for 6 symbols, giving $100\times 3=300$ bits.

Huffman saves 76 bits, about 25 per cent. The saving comes from giving F, which occurs 45 times out of 100, a single bit rather than three.

Example 6. Why is 0/1 knapsack's $O(nW)$ cost called pseudo-polynomial?

A polynomial-time algorithm runs in time polynomial in the length of the input, measured in bits.

The input to knapsack is $n$ items and a capacity $W$. Writing down $n$ items takes space proportional to $n$, so a factor of $n$ in the running time is genuinely polynomial.

But writing down $W$ takes only ${\log }_{2}W$ bits, since it is a single number in binary. A capacity of one billion needs 30 bits.

So the running time $O(nW)$ is $O(n\cdot 2^{\log W})$, which is exponential in the number of bits used to write $W$.

Concretely, doubling the number of bits in $W$ squares the running time rather than doubling it. An instance with $n=100$ and $W=10^9$ requires $10^{11}$ table entries, which is intractable despite the input fitting on one line.

The term pseudo-polynomial names exactly this: polynomial in the numeric value of an input, exponential in its encoded length. The knapsack problem is NP-complete, and the existence of this algorithm does not contradict that, precisely because the algorithm is not polynomial in the input size.

Summary

Three techniques answer one question: how do the subproblems relate?

Independent subproblems mean divide and conquer, with cost given by a master-theorem recurrence. Strassen shows that reducing the branching factor from 8 to 7 is what lowers the exponent.

Overlapping subproblems plus optimal substructure mean dynamic programming. The gap between distinct subproblems and recursive calls is exactly what caching recovers.

Memoisation is top-down and solves only what is reached; tabulation is bottom-up, has better locality, and permits rolling-array space optimisation.

Each classic dynamic program is defined by its state and recurrence: knapsack on (item, capacity), LCS and edit distance on (position, position), matrix chain on (start, end), and coin change on amount.

Greedy needs optimal substructure plus a provable greedy choice property, established by an exchange argument. It is faster when it works and silently wrong when it does not.

Fractional knapsack is greedy by ratio; 0/1 knapsack is a dynamic program. The only difference is whether items can be split.

Activity selection is optimal by earliest finishing time, and both earliest start and shortest duration fail. Huffman merges the two least frequent symbols. Dijkstra requires non-negative weights.

$O(nW)$ is pseudo-polynomial because $W$ is a numeric value written in $\log W$ bits, so the cost is exponential in the input length.