What is greedy algorithm¶

• Greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece.
• It always chooses the next piece that offers the most obvious and immediate benefit.
• Greedy fits perfectly for those solutions in which choosing a locally optimal solution also leads to global optimal solution (aka greedy choice).

Common greedy algorithms¶

• Already taught algoritms:
  • Insertion Sort
  • Selection Sort
  • Topological Sort
  • Prims
  • Kruskal
• Activity Selection Problem
• Coin Change Problem
• Fractional Knapsack