Make locally optimal choices that sometimes give a global optimum.
Greedy algorithms make the locally best choice hoping for a global optimum; correct when the greedy-choice property holds (activity selection, Huffman coding, Kruskal, Prim). Proof by exchange argument. Fails for problems like 0/1 knapsack.
Making change with US coins by taking the largest coin first is optimal.
Greedy algorithms are simple and fast, and they are correct for some problems, so recognising when they work saves effort.
Make locally optimal choices that sometimes give a global optimum.
Greedy algorithms are simple and fast, and they are correct for some problems, so recognising when they work saves effort.
When a locally best choice can always be extended to a global optimum, which must be proven, often with an exchange argument.
A locally attractive choice can block a better global option, as with some coin systems where greedy uses too many coins.
Typical applications include making change with coins where the currency system is canonical, scheduling as many non-overlapping meetings as possible by earliest end time and compressing data with Huffman codes built from frequencies.
Study "Dynamic programming" first (topic 29 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Local vs global optimum. Exchange argument. Fast and simple.
Making change with US coins by taking the largest coin first is optimal.
The next topic is "Divide and conquer", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 30 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.