COMP9123 — Data Structures & Algorithms
Week 10: Greedy Algorithms
Week 10 studies one of the most attractive and most dangerous design ideas in algorithms: make the best-looking local choice now and never look back. The lecture deliberately shows both success and failure, so the real lesson is not “greedy is fast,” but “greedy is correct only when the problem structure protects your local choices.”
A good Week 10 answer never stops at “pick the biggest” or “pick the earliest.” It explains why that local choice is safe, or breaks it with a clean counterexample.
Greedy Pattern: Commit Locally, but Earn the Right to Trust It
The lecture starts with a deliberately broad template. A greedy algorithm initializes a result, decides the order in which to consider candidates, and then keeps adding the next locally best thing whenever it improves the current solution. That template is elegant, but by itself it proves nothing.
| Greedy ingredient | What it means | Why it can go wrong |
|---|---|---|
| Choice rule | Define what “best” means at each step. | A plausible local score may have nothing to do with global optimality. |
| Processing order | Sort or scan candidates in a specific sequence. | The right order depends completely on the problem objective. |
| Irrevocability | Earlier decisions are never undone. | If the wrong choice is made early, the algorithm has no way to recover. |
Why greedy is tempting
Greedy algorithms are often simple to implement and easy to describe, which is why they are such natural first ideas.
Why greedy is dangerous
Many problems admit several “reasonable” local rules, and most of them are wrong.
Professor lens
The real skill this week is not inventing a greedy rule. It is deciding whether the rule deserves a proof or deserves a counterexample.
Counterexamples: A Few Successful Runs Never Prove a Greedy Rule
The lecture pauses on failed knapsack rules for an important reason: algorithm design includes learning how to disprove a bad idea quickly. A rule that works on one instance or even on many natural-looking instances can still be wrong in general.
How to break a greedy rule cleanly
Make the wrong local choice look attractive, then hide a better overall combination behind it. Small counterexamples are better than large noisy ones because they isolate exactly what goes wrong.
Lecture examples
“Highest benefit first” and “smallest weight first” both feel plausible for fractional knapsack, yet the slides show they miss a better solution than the ratio-based rule.
The tutorial extends this idea nicely: it asks you to show that even wrong greedy rules can succeed on infinite classes of instances. That is the perfect reminder that examples are evidence, not proof.
Fractional Knapsack: The Ratio Rule Works Because Fractions Are Allowed
The lecture uses fractional knapsack to show both sides of greedy design. Several local rules look reasonable, but only the benefit-to-weight ratio rule is actually safe. The reason it works is structural: once fractions are allowed, exchanging one small amount of weight for another becomes a legal local repair.
| Candidate rule | Result | Main lesson |
|---|---|---|
| Highest benefit first | Not always optimal | Big reward alone can be misleading if the item is too heavy. |
| Smallest weight first | Not always optimal | Light items are not necessarily dense in value. |
| Highest benefit / weight ratio first | Optimal for the fractional version | Every unit of remaining capacity should go to the densest available value. |
Suppose an optimal solution leaves some capacity assigned to a lower-ratio item while not fully taking a higher-ratio item.
Swap equal weight from the worse-ratio item into the better-ratio item. Feasibility is preserved because total weight does not change.
Total benefit strictly improves, contradicting optimality. So an optimal solution can always be reshaped to agree with the greedy ratio choice.
The lecture's final implementation point is practical: sort items by ratio in descending order, then scan once. That gives \(O(n \log n)\) time because sorting dominates.
Scheduling: The Right Greedy Order Depends on the Objective
Week 10 uses scheduling to show that “sort by something obvious” only works when that sorting key aligns with the optimization target. The lecture's main scheduling problem is interval partitioning, while the tutorial adds weighted completion-time scheduling with an exchange argument.
| Problem | Greedy idea | Why that order fits |
|---|---|---|
| Interval partitioning | Sort lectures by increasing start time, then assign each lecture to any compatible classroom. | The algorithm stays ahead of the overlap depth and opens a new classroom only when no existing room can host the lecture. |
| Weighted sum of completion times | The tutorial's optimal rule comes from comparing adjacent swaps and ordering jobs by the right ratio. | This is a good example of a greedy rule that comes from proof, not guesswork. |
| Unit-length interval cover | Place each interval as far right as possible while still covering the leftmost uncovered point. | That greedy placement maximizes future coverage from each interval. |
For interval partitioning, the lecture's lower bound is the depth of the interval set: the maximum number of lectures overlapping at any time. A greedy schedule is optimal when it uses exactly that many rooms.
Huffman Coding: Greedy Merging Builds an Optimal Prefix Code
The Huffman section is the capstone of the chapter because it gives the full greedy package: a clean objective, a priority-queue implementation, structural observations, and an inductive correctness proof.
Start with leaves
Each character is a single-node tree weighted by its frequency.
Merge the two lightest trees
Use a min-priority queue to repeatedly combine the least frequent available trees.
Read codes from root-to-leaf paths
Left and right edges define a prefix code once the full tree is built.
Optimization target
Minimize the weighted external path length \(\sum_{c \in C} f(c) \cdot depth_T(c)\).
Key observation
In an optimal tree, deeper leaves should correspond to rarer characters, not common ones.
Runtime
The priority queue dominates, giving \(O(|C|\log |C|)\) after frequencies are known. The lecture also writes the full pipeline as \(O(n + d\log d)\).
The lecture's correctness arc is worth remembering in words: there is an optimal tree where the two least frequent symbols are deepest siblings, so you may merge them, solve the smaller problem optimally, and then expand back.
Greedy Limits: Small Changes to the Problem Can Destroy Correctness
The lecture ends with a healthy warning. Even when a greedy algorithm is correct for one problem, tiny-looking changes in the model can make the same idea fail completely.
| Correct greedy result | Nearby harder variant | What changes |
|---|---|---|
| Fractional knapsack | 0/1 knapsack | Without fractional exchange, the ratio rule is no longer always safe. |
| Interval partitioning | Scheduling with richer constraints | Compatibility or objective changes can invalidate the simple start-time rule. |
| Binary Huffman coding | Non-binary or modified encoding settings | The classic merge-two-lightest structure is tied to the binary prefix-code model. |
This is one of the most important closing lessons in the course: the success of a greedy algorithm is always a theorem about a specific problem definition, not a transferable personality trait of the idea itself.
Tutorial & problem lens: Week 10 is about proof habits as much as algorithms
The tutorial makes the chapter more interesting than a list of classic examples. It asks you to build trees, identify infinite success cases for bad rules, prove and disprove greedy matchings, cover points with unit intervals, derive the right weighted scheduling order, and reason about a florist pricing challenge.
Warm-up and proof habits
- Construct a Huffman tree for a real phrase instead of only reading the algorithm abstractly.
- Show that wrong knapsack rules can still succeed on infinitely many inputs, which separates “sometimes works” from “always correct.”
- Practice both proof and disproof on greedy matching algorithms.
Problem-solving extensions
- Cover points on the real line with the fewest unit intervals.
- Minimize weighted completion time using an adjacent-swap exchange argument.
- Design a greedy buying order for the florist problem and justify why expensive flowers should be purchased early under increasing multipliers.
Best way to study the last week
Do not ask only “what is the rule?” Ask “what exact exchange or contradiction would prove this rule safe?” and “what smallest instance would break it if it were wrong?” If you can do both, you have actually learned the greedy chapter.
The lecture also points to a fractional-knapsack code-along on Ed. That is useful, but the real exam value is still the correctness logic and the counterexample instinct.
Quiz Hub & spaced review
Use the inline checks to verify the three highest-value habits first: disprove bad greedy rules cleanly, choose the ratio rule for fractional knapsack, and explain Huffman's merge step. Then use the mixed tools to rehearse Week 10 alongside the earlier data-structure weeks.
Recommended sequence. Do one small counterexample, one fractional-knapsack trace, and one Huffman merge tree by hand, then use the Quiz Hub or flashcards to see whether the proof ideas still feel clear without the lecture scaffolding.