# Greedy Choices and Counterexamples

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/greedy-choices-and-counterexamples

A **greedy algorithm** builds a solution step by step, making the **locally best** choice at each turn without ever reconsidering. While simple and fast, a series of local optimizations does not always yield a **globally optimal** result.

| Approach | Behavior | Risk / Benefit |
| --- | --- | --- |
| **Greedy** | Grabs immediate best step | Fast, but can fail globally |
| **Optimal** | Maximizes overall result | Guaranteed best, often slower |

Some problems allow greedy solutions. **Making change** with standard coins, minimizing lateness, and building minimum spanning trees are proven optimal via **exchange arguments** or **matroids**.

## When Greedy Fails

Greedy often fails, and the definitive proof is a **counterexample**. Consider making change for 30 using coins of sizes $c \in \{1, 15, 20\}$.

The greedy choice picks 20 first, leaving 10, and takes ten 1sts for a total of 11 coins. The optimal solution uses two 15s, totaling just 2 coins.

**Common pitfall:** Assuming a locally optimal choice guarantees a global optimum. **Never assume correctness**; you must mathematically prove it, or a single counterexample will demolish your algorithm.

## Practice questions

5 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Select every true statement about greedy algorithms.

A. A single counterexample is enough to disqualify a greedy strategy.
B. The coin-change problem shows greedy depends on the coin system.
C. Kruskal's and Prim's algorithms are greedy and provably correct.
D. At each step it takes whatever looks best right now and never revisits it.
E. Greedy always produces the optimal solution for any optimisation problem.

**Answer:** B. The coin-change problem shows greedy depends on the coin system.; C. Kruskal's and Prim's algorithms are greedy and provably correct.; D. At each step it takes whatever looks best right now and never revisits it.; E. Greedy always produces the optimal solution for any optimisation problem.

**Why:** Greedy is simple, fast, and never backtracks, and it needs a correctness proof or a counterexample. What it is NOT is automatically globally optimal, that overclaim is the trap.

Page: https://tryals.app/practice/computer-science-i/greedy-choices-and-counterexamples/select-every-true-statement-about-greedy-algorithms

### 2. Dijkstra's shortest-path algorithm is greedy and provably optimal, until an edge has negative weight, when it breaks. What assumption did the proof rely on?

A. That all paths are unique, which negative weights make ambiguous
B. That extending a path never makes it shorter
C. That the graph is connected, which negative weights can violate
D. That the priority queue orders correctly, which fails for negative numbers

**Answer:** B. That extending a path never makes it shorter

**Why:** The greedy step is safe only because distances never decrease as paths grow, so the nearest unvisited node cannot be improved later. A negative edge breaks that guarantee and the finalisation becomes premature, which is why Bellman-Ford, slower and relaxing repeatedly, exists for those graphs.

Page: https://tryals.app/practice/computer-science-i/greedy-choices-and-counterexamples/dijkstras-shortest-path-algorithm-is-greedy-and-provably-optimal

### 3. Greedy change-making with British coins always gives the fewest coins, and with the coin set {1, 15, 20} it fails on 40 - taking 20+15+1+1+1+1+1 instead of 20+20. Why does the same algorithm succeed on one coin set and fail on another?

A. Because greedy algorithms fail whenever the coin values are not multiples of each other.
B. Because {1, 15, 20} is not a valid coin system, so the failure does not count.
C. Because greedy is optimal only when the problem has the right structure.
D. Because greedy succeeded by luck on British coins and has no reliable cases.

**Answer:** C. Because greedy is optimal only when the problem has the right structure.

**Why:** The failure is clearest on 30: greedy takes 20 and needs ten 1s, where 15+15 uses two coins, a locally best first choice has cut off the better solution. Whether that can happen is a property of the system, to be proved rather than assumed. Greedy is provably optimal for Huffman coding and minimum spanning trees, each with an exchange argument behind it.

Page: https://tryals.app/practice/computer-science-i/greedy-choices-and-counterexamples/greedy-change-making-with-british-coins-always-gives-the-fewest

### 4. Order what happens when greedy makes change for 30 with coins {1, 15, 20}.

**Answer:**

1. Take 20, the largest coin not exceeding 30
2. Now 10 remains; take 1, since 15 and 20 are too big
3. Keep taking 1s until nothing remains
4. End with 11 coins, worse than the optimal 2

**Why:** Greedy grabs 20, then is forced onto ten 1s, ending at 11 coins, while two 15s would have done it in 2. A locally best first move led straight to a globally worse answer.

Page: https://tryals.app/practice/computer-science-i/greedy-choices-and-counterexamples/order-what-happens-when-greedy-makes-change-for-30-with-coins-1-15

### 5. Sort each problem by whether the greedy approach is provably optimal or can fail.

**Answer:**

- Greedy is provably optimal: Minimum spanning tree via Kruskal's or Prim's algorithm, Scheduling to minimize maximum lateness, Making change with a standard coin system
- Greedy can fail: Making change for 30 with coins {1, 15, 20}

**Why:** Minimum spanning trees, minimizing lateness, and standard coin systems are cases where greedy is provably optimal (via exchange arguments or matroids). The oddball {1, 15, 20} system is where greedy fails.

Page: https://tryals.app/practice/computer-science-i/greedy-choices-and-counterexamples/sort-each-problem-by-whether-the-greedy-approach-is-provably-optimal