Practice question · Sort into groups
Sort each problem by whether the greedy approach is provably optimal or can fail.
Groups: Greedy is provably optimal · Greedy can fail
- Making change with a standard coin system
- Scheduling to minimize maximum lateness
- Making change for 30 with coins {1, 15, 20}
- Minimum spanning tree via Kruskal's or Prim's algorithm
Hints
- The lesson names specific cases where greedy is guaranteed optimal.
- The coins {1, 15, 20} are the deliberate counterexample.
Show the 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.
Practise Greedy Choices and Counterexamples
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Greedy Choices and Counterexamples
- Select every true statement about greedy algorithms.
- Dijkstra's shortest-path algorithm is greedy and provably optimal, until an edge has negative weight, when it…
- Greedy change-making with British coins always gives the fewest coins, and with the coin set {1, 15, 20} it…
- Order what happens when greedy makes change for 30 with coins {1, 15, 20}.