Skip to main content

DSAPath9 mincore

Greedy Algorithms

A greedy algorithm builds a solution by repeatedly making the locally best choice. Greedy methods are fast when a proof shows local choices lead to a global optimum.

Why This Matters

Greedy algorithms are attractive because they are usually simple and fast. The danger is that local improvement can fail globally. A greedy solution is not done until the proof is done.

Core Idea

At each step, choose the option that looks best by a local rule. Prove the rule is safe, often with an exchange argument.

Worked example: activity selection by earliest finish time works because any optimal schedule can exchange its first activity for the earliest-finishing compatible activity without reducing the number of scheduled activities.

Common Mistakes

  • Assuming a plausible rule is correct.
  • Confusing greedy with dynamic programming. DP compares many future cases; greedy commits.
  • Ignoring counterexamples. One small counterexample defeats the algorithm.

Exercises

  • Give a greedy rule for coin change and find a coin system where it fails.
  • Explain the exchange argument idea in one paragraph.
  • Compare greedy activity selection with knapsack DP.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 15.
  • MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015.