Divide and Conquer, Greedy, and Dynamic Programming

The syllabus names three design techniques, and the examinable question is rarely how to implement one — it is which one applies, and whether the shortcut is safe. All three break a problem into subproblems; what separates them is how the pieces relate. Divide and conquer splits into subproblems that do not overlap, solves them independently and combines, which is why its cost is a clean recurrence. Dynamic programming applies when the subproblems do overlap: the same subproblem is needed many times, so it is solved once and stored, and the exponential recursion collapses to a polynomial table. Greedy applies when something much stronger is true — that a locally best choice is part of a globally best solution — and the whole difficulty is that this is sometimes false and always plausible. The clearest demonstration is the knapsack. In the fractional version, taking items in order of value per unit weight is provably optimal, because any leftover capacity can be filled with a fraction of the next item. In the 0/1 version the same rule is simply wrong: with a capacity of 50 and items worth 60, 100 and 120 at weights 10, 20 and 30, the greedy rule takes the 10 and the 20 for 160, while the optimum is the 20 and the 30 for 220. Nothing about the greedy choice looks unsafe until you check, and that is the lesson — greedy needs a proof, and the exam tests whether you know which problems have one. Dynamic programming is what you fall back on when they do not.

Which Technique, and Why

The three techniques, by what they assume
TechniqueNeedsA standard example
Divide and conquerSubproblems that do not overlapMerge sort, binary search, Karatsuba
Dynamic programmingOverlapping subproblems and optimal substructureLCS, 0/1 knapsack, matrix chain, Floyd–Warshall
GreedyA provable greedy-choice propertyFractional knapsack, Huffman, Kruskal, activity selection
⚠️ The knapsack: same items, same capacity, two different answers
Capacity 50; items of weight 10, 20, 30 with values 60, 100, 120, so ratios 6, 5 and 4 per unit weight. Fractional: take all of the 10 and the 20, then 20/30 of the third, for 60 + 100 + 80 = 240, and greedy by ratio is provably optimal. 0/1: the same greedy rule takes the 10 and the 20 and stops at weight 30, leaving 20 of capacity unusable, for 160. The optimum is to skip the highest-ratio item entirely and take the 20 and the 30 for 220. So a greedy rule that is provably correct on one version is 37% off on the other, and nothing in the rule signals the difference. This is why 0/1 knapsack needs a dynamic-programming table of O(nW), and why the exam keeps asking which version it has handed you.

Dynamic Programming, and the Size of the Table

A dynamic program is a table plus a recurrence, and its complexity is almost always (number of cells) × (work per cell). That single sentence answers most complexity questions in this topic without any analysis: the LCS of strings of length m and n has an m × n table filled in O(1) each, so O(mn); 0/1 knapsack has an n × W table, so O(nW); matrix-chain multiplication has an n × n table whose cells each try up to n split points, so O(n³).

🎯 Why O(nW) is not polynomial in the input size
This is the subtlety worth having straight, because it looks like a contradiction. 0/1 knapsack is NP-hard, and yet here is an O(nW) algorithm — so how? Because W is a value, not a size. Writing the number W down takes only log W bits, so an algorithm running in time proportional to W is exponential in the length of its input. That is called pseudo-polynomial, and it is why the table method is perfectly practical for a capacity of 1000 and useless for a capacity of 2⁶⁴. A question asking whether O(nW) contradicts NP-hardness is asking exactly this, and the answer is that it does not.

One worked figure to anchor the LCS: the longest common subsequence of AGGTAB and GXTXAYB is GTAB, of length 4. Note that a subsequence need not be contiguous — that is what separates it from a substring, and confusing the two turns an O(mn) dynamic program into a different and easier problem.

Greedy Where It Is Provable: Huffman

Huffman coding is the greedy algorithm with the cleanest proof: repeatedly merge the two least frequent symbols, and the result is an optimal prefix code. Take frequencies 5, 9, 12, 13, 16 and 45. The merges cost 14, 25, 30, 44 and 100, summing to 224, which is also the total encoded length — and the two agree because every merge adds one bit to every symbol beneath it.

The resulting code lengths, and the total
FrequencyCode lengthContribution
45145
16348
13339
12336
9436
5420
Total—224 bits
🧠 The most frequent symbol gets the shortest code, and the tree is not unique
Two facts save time. The most frequent symbol always ends up with the shortest code — here 45 gets a single bit — so a question offering an assignment where a rare symbol has a shorter code than a common one can be rejected without building anything. And the tree is not unique: ties in the priority queue can be broken either way, producing different trees with the same total length, so a question asking for the total is well posed while one asking for a specific symbol's code may not be. Checking whether the answer depends on tie-breaking is worth the two seconds it takes.

Key takeaways

  • Divide and conquer needs non-overlapping subproblems; dynamic programming exists because they overlap.
  • Greedy needs a provable greedy-choice property — it is sometimes false and always plausible.
  • Greedy by ratio is optimal for fractional knapsack and wrong for 0/1: 240 against 220 optimal and 160 greedy.
  • A dynamic program costs (number of cells) × (work per cell): LCS O(mn), knapsack O(nW), matrix chain O(n³).
  • O(nW) is pseudo-polynomial — W is a value, not a size — so it does not contradict NP-hardness.
  • A subsequence need not be contiguous; a substring must be.
  • Huffman merges the two least frequent symbols; on 5, 9, 12, 13, 16, 45 the total is 224 bits.
  • The most frequent symbol gets the shortest code, and the Huffman tree is not unique though its total is.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. A 0/1 knapsack has capacity 50 and items of weights 10, 20, 30 with values 60, 100, 120. What is the maximum total value?

    Numerical answer — type the value.

    Show answer

    Answer: 220

    The best 0/1 choice is the 20 and the 30, filling the capacity exactly for 100 + 120 = 220. Greedy by value-per-weight would take the 10 (ratio 6) and the 20 (ratio 5), reach weight 30, and be unable to fit the 30 — stopping at 160. And the fractional answer is 240, taking two-thirds of the last item. Three different numbers for one item list, and which is correct depends entirely on whether items may be split. Reading that from the question before computing anything is the whole skill; 240 is the answer to a question that was not asked.

  2. Greedy by value-per-unit-weight is provably optimal for:

    1. The 0/1 knapsack
    2. The fractional knapsack
    3. Both
    4. Neither
    Show answer

    Answer: B — The fractional knapsack

    Only the fractional version. The proof depends on being able to fill any leftover capacity with a fraction of the next-best item, so no capacity is ever wasted — remove divisibility and the argument collapses, because a leftover gap may fit nothing at all. The instance above shows the damage: greedy gets 160 where 220 is available. Option C is the answer a candidate gives from having seen greedy work on the fractional case and generalising, which is precisely the habit this pairing exists to break. 0/1 needs dynamic programming, at O(nW).

  3. Symbols have frequencies 5, 9, 12, 13, 16 and 45. What is the total length in bits of the optimal Huffman encoding?

    Numerical answer — type the value.

    Show answer

    Answer: 224

    Merging the two least frequent each time gives merges of 14 (5+9), 25 (12+13), 30 (14+16), 44 (25+30… by the queue order) and finally 100, and the sum of the merge costs is 224 — which is the total encoded length, because each merge adds one bit to every symbol under it. Checking it the other way agrees: the code lengths come out 1, 3, 3, 3, 4, 4 for 45, 16, 13, 12, 9, 5, and 45×1 + 16×3 + 13×3 + 12×3 + 9×4 + 5×4 = 224. Computing it both ways is the reliable habit here, since the merge-sum method is fast and the length method catches a mis-built tree.

  4. The 0/1 knapsack dynamic program runs in O(nW). Since 0/1 knapsack is NP-hard, this means:

    1. P = NP
    2. The bound is pseudo-polynomial, since W is a value and not an input size
    3. The algorithm is incorrect
    4. 0/1 knapsack is actually in P
    Show answer

    Answer: B — The bound is pseudo-polynomial, since W is a value and not an input size

    Writing the capacity W down takes about log₂W bits, so an algorithm whose running time is proportional to W is exponential in the length of that input. It is called pseudo-polynomial, and it resolves the apparent paradox without disturbing anything: the algorithm is correct, the problem is still NP-hard, and there is no claim about P versus NP. The practical reading is the useful one — the table method is fine for a capacity of a few thousand and hopeless for a 64-bit capacity, and that is a statement about the numbers in the instance rather than about how many items there are.

  5. What is the length of the longest common subsequence of AGGTAB and GXTXAYB?

    Numerical answer — type the value.

    Show answer

    Answer: 4

    The LCS is GTAB, length 4. The characters need not be adjacent in either string — that is what makes it a subsequence rather than a substring, and a candidate who looks for a contiguous match finds only length 1 or 2. The dynamic program is an m × n table where a cell is 1 + the diagonal when the characters match and otherwise the larger of its two neighbours, so the cost is O(mn) — here 6 × 7 = 42 cells. The subsequence-versus-substring distinction is worth reading for explicitly, because the two problems have different answers and different algorithms.

  6. Which of the following are true of an optimal Huffman code? (More than one may be correct.)

    1. The most frequent symbol never has a longer code than a less frequent one
    2. No codeword is a prefix of another
    3. The tree is unique for a given set of frequencies
    4. All codewords have the same length
    Show answer

    Answer: A — The most frequent symbol never has a longer code than a less frequent one; B — No codeword is a prefix of another

    A and B. A is what optimality means here — if a rarer symbol had a shorter code, swapping the two would reduce the total, so no optimal code can have that shape, and it lets you reject a proposed assignment on sight. B is the prefix-free property, which is what makes the code decodable without separators and is guaranteed because every symbol sits at a leaf. C is false: ties in the priority queue can break either way, so several distinct trees achieve the same total — 224 here — which is why a question asking for the total is well posed and one asking for a particular codeword may not be. D describes a fixed-length code, which is the thing Huffman improves on.

  7. Matrix-chain multiplication is solved by dynamic programming in:

    1. O(n²)
    2. O(n³)
    3. O(2ⁿ)
    4. O(n log n)
    Show answer

    Answer: B — O(n³)

    O(n³), straight from the rule that a dynamic program costs cells × work per cell: the table is n × n over subchains, and filling one cell tries every split point inside that subchain, which is up to n of them. Option C is the cost of enumerating all parenthesisations, which is Catalan-many and exactly what the table exists to avoid. This is also the standard demonstration that the order of multiplication matters without changing the answer — the product is the same, the number of scalar multiplications is not, which is why the problem is worth solving at all.

  8. Dynamic programming is preferable to plain divide-and-conquer exactly when:

    1. The problem is a minimisation problem
    2. The subproblems overlap, so the same one is solved repeatedly
    3. The input is sorted
    4. The recursion is more than two levels deep
    Show answer

    Answer: B — The subproblems overlap, so the same one is solved repeatedly

    Overlapping subproblems is the whole condition, and it is the difference the two techniques turn on. Merge sort's halves are disjoint, so storing results would buy nothing — there is never a repeat. Fibonacci and LCS revisit the same subproblem many times, so storing collapses an exponential recursion to a polynomial table. The second condition dynamic programming needs is optimal substructure, that an optimal solution is built from optimal solutions to subproblems; without it the table would be storing answers that cannot be combined. Option A is irrelevant — plenty of dynamic programs maximise, and plenty of divide-and-conquer algorithms optimise nothing at all.