Practice question · Select all that apply
Select every true statement about greedy algorithms.
Hints
- Only one option overclaims a guarantee.
- Simplicity and speed are real virtues; global optimality is not automatic.
Show the 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.
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
- 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}.
- Sort each problem by whether the greedy approach is provably optimal or can fail.