The Greedy Paradigm

Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end.

Features and Bugs of the Greedy Paradigm

  • Easy to come up with one or more greedy algorithms
  • Easy to analyze the running time
  • Hard to establish correctness