Exercise 3: Why "Always Use Brute Force Instead of Greedy" Is Wrong — Possible Solution ==================================================================== WHAT'S TRUE IN THE DEVELOPER'S CONCERN ------------------------------ This chapter did verify a real, genuine greedy failure - the {1,3,4} denomination set gave a suboptimal answer for amount=6. Greedy algorithms genuinely are not universally safe, and this chapter was explicit that correctness has to be checked per problem rather than assumed. So the underlying concern (greedy can silently give a wrong answer) is legitimate and well-supported by this chapter's own evidence. WHY "ALWAYS USE BRUTE FORCE INSTEAD" DOESN'T FOLLOW ------------------------------ This chapter also verified the opposite case just as concretely: greedy matched an independently-computed true optimum exactly across three different US-coin amounts. Greedy is not unreliable in some absolute sense - it is unreliable specifically for problems that lack the right structural property, and reliable for problems that have it (like US coin denominations). Blanket-replacing greedy with brute force ignores this distinction entirely, discarding a fast, correct solution (US coin change) in favor of a slower one, without any corresponding gain in correctness for that specific problem. WHY BRUTE FORCE ISN'T A SAFE UNIVERSAL DEFAULT EITHER ------------------------------ Chapter 6 verified directly that brute force's own reliability comes at a real cost that scales with problem size - checking all subsets of just 40 items, at Chapter 6's own measured rate, would take nearly five days. A blanket policy of "always use brute force" would apply that same explosive cost to every problem a greedy algorithm might otherwise solve quickly and correctly, including the US-coin case this chapter proved greedy handles perfectly well. Replacing a fast, verified-correct greedy algorithm with an exponentially slower brute-force approach, purely out of general caution, would make some programs unacceptably slow for no actual improvement in correctness. THE ACTUAL, MORE CAREFUL POLICY ------------------------------ The right approach - which is exactly what this chapter's own two worked examples modeled - is to verify whether greedy is safe for the SPECIFIC problem at hand, using brute force or an independently computed reference answer as the check, rather than adopting a blanket rule in either direction. Greedy and brute force are both genuinely useful tools with different, situation-dependent tradeoffs, not a strictly-better-or-worse pair. WHY THIS WORKS AS AN ANSWER ------------------------------ The response credits the real concern behind the developer's claim using this chapter's own verified failure case, then directly refutes the "always" framing using both this chapter's own successful US-coin result and Chapter 6's own explosive-growth findings, concluding with the actual nuanced policy (verify per problem) rather than simply picking a side.