3.7.4 · D5Algorithm Paradigms
Question bank — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)
Two words we lean on throughout:
- greedy-choice property = the choice that looks best right now is part of some global optimum, so you never need to undo it.
- optimal substructure = after making that choice, the rest of the best answer is just the best answer to a smaller version of the same problem.
True or false — justify
Sort by finish time always beats sort by start time for activity selection.
True — earliest-finish frees the resource soonest, which is provably safe; earliest-start can pick one long job that blocks everything (e.g. C(0,6) devouring the schedule).
Fractional knapsack and 0/1 knapsack are both solved optimally by "densest item first".
False — only the fractional version. In 0/1 you can't slice the last item, so a high-density item may leave an unfillable gap; 0/1 needs Dynamic Programming.
In an optimal Huffman tree the two rarest symbols are always siblings at the deepest level.
True — that's exactly what the exchange argument proves; giving the rarest symbols the longest codes is what minimizes total bits.
A greedy algorithm may revisit and change an earlier choice if a later step reveals a better option.
False — by definition greedy never reconsiders; that non-backtracking is why we must prove each choice is safe before trusting it.
Every problem with optimal substructure can be solved greedily.
False — optimal substructure is also true of 0/1 knapsack and many DP problems. You also need the greedy-choice property; without it, DP is required.
Huffman's total cost equals the sum of the frequencies of all internal nodes.
True — each merge of frequency pushes both its subtrees one level deeper, adding exactly bits; summing over merges gives the total, e.g. .
If two activities have the same finish time, the algorithm's answer depends on which you pick first.
False for the count — tie-breaking may change which set you output, but the maximum number of activities is unaffected, since either tied job frees the resource at the same instant.
Sorting is the real bottleneck in all three algorithms.
True — each is dominated by sorting (or heap operations for Huffman via a Priority Queue / Binary Heap); the actual greedy scan/merge is linear.
A fixed-length code can never beat a Huffman code in total bits.
True — Huffman is provably optimal among prefix codes, and fixed-length is one such prefix code, so Huffman is at least as short (equal only when all frequencies are equal).
Spot the error
"Greedy activity selection: pick the shortest activity first because it uses the least time."
Wrong metric. A short job can straddle the boundary between two otherwise-compatible long jobs, blocking both. The safe key is earliest finish, not shortest duration.
"For fractional knapsack, sort by value descending and take the most valuable items."
Wrong key. A huge-value item may also be huge-weight and hog capacity. The correct key is density — value per kilogram of the resource you're rationing.
"Huffman: merge the two most frequent symbols first so common symbols share a subtree."
Backwards. You merge the two minimum frequencies; merging small ones deepens the rarest symbols, giving them the long codes and keeping frequent symbols shallow.
"The exchange argument proves greedy is optimal by trying every possible solution and comparing."
No brute force involved. An Exchange Argument takes one arbitrary optimal solution and shows you can swap in the greedy choice without worsening it — a single structural swap, not enumeration.
"In fractional knapsack you might need to leave the bag partly empty if items don't fit exactly."
Never — because fractions are allowed, you always top off the last space with a slice of the next-densest item, so the bag ends exactly full (unless total weight < W).
"Any prefix-free code is optimal since every prefix code is uniquely decodable."
Confuses two properties. Decodability guarantees you can read the code, not that it's short. Optimality is about minimizing , which only Huffman's merge order achieves.
"Greedy fails on 0/1 knapsack, so it must fail on fractional knapsack too."
Wrong generalization. The fraction is exactly what rescues greedy: it removes the indivisibility that creates unfillable gaps in the 0/1 case.
Why questions
Why does moving weight from a lower-density item to a higher-density one prove fractional greedy is optimal?
Because the value change is whenever — any solution not maxing the densest first can be strictly improved, so it wasn't optimal.
Why must the two least-frequent Huffman symbols end up deepest, not shallowest?
Depth = codeword length, and long codes should go to rare symbols so their length is multiplied by a small frequency — minimizing the total .
Why does replacing an optimal solution's earliest-finisher with the global earliest-finisher stay feasible?
Because , so conflicts with nothing that didn't already conflict with — it frees the resource no later, so the rest of the schedule still fits.
Why is a min-heap the natural data structure for Huffman rather than a sorted list?
Each step needs the two current minimums and insertion of a new merged node; a Priority Queue / Binary Heap does both in , versus re-sorting a list each time.
Why can't greedy simply "look one step ahead" to fix its 0/1 knapsack mistakes?
The poison can come many steps later — a locally best pick may exclude a combination only visible after several choices, which is precisely why exhaustive-over-subproblems (Dynamic Programming) is needed.
Why does merging the two smallest frequencies add the least possible cost at each step?
Every merge charges to the total; choosing the two smallest available frequencies minimizes that charge at that step, and the greedy-choice proof shows these local minima compose into the global minimum.
Edge cases
What happens in activity selection when all activities are mutually non-overlapping?
You pick all of them — the greedy scan never rejects anyone, and the count equals .
What if all activities overlap a single common instant?
You can pick exactly one — after choosing the earliest finisher, no other start is its finish, so the answer is size 1.
Fractional knapsack when total item weight : what's the answer?
Take every item whole; the bag has leftover room and total value is simply — no fraction is ever needed.
Fractional knapsack with : what does greedy return?
Nothing fits, so for all and total value is ; the "first overflowing item" is the very first item, taken as fraction .
Huffman with a single symbol (): what code length does it get?
There are zero merges, so no bit is ever assigned; a lone symbol technically needs bits by the cost formula (in practice a degenerate 1-bit code is used to make it transmittable).
Huffman when all frequencies are equal: what tree results?
A balanced tree giving codes of length (or one bit less for some leaves if isn't a power of two) — identical to a fixed-length code, which here is already optimal.
What if two Huffman merges tie on frequency — does the total cost change?
No — different tie-breaks can produce different shapes (and different individual code lengths), but the minimum total bit-count is invariant.
Activity selection with a single activity (): what is returned?
That one activity — the greedy always picks the first (earliest finisher), and there's nothing left to scan.
Recall One-line self-check before you close
Say the mnemonic and the key each algorithm sorts/heaps on. Answer ::: "Finish Fast, Pour Pricey, Merge Mini" — earliest finish, highest value/weight density, two minimum frequencies.