GeeksforGeeks Tutorial: Introduction to Greedy Algorithms

Overview

• Tutorial covers the basic concepts of Greedy Algorithms.
• Greedy Algorithms involve making the locally optimal choice at each stage with the hope of finding a global optimum.

Example Scenario

• A rich programmer needs to give his friend $35 using minimum coins of $20, $10, and $5.
• Possible combinations:
  • Seven $5 coins
  • One $10 coin and five $5 coins
• Optimal Solution using Greedy Method:
  • Start with largest coin not exceeding the amount: $20.
  • Then, give $10 (largest remaining denomination under $15).
  • Finally, give $5 to complete $35 in 3 coins.
• Note: Greedy choice involves selecting the largest coin possible that fits the remaining amount.

Characteristics of Greedy Algorithms

• Simple and easy to code.
• Reasonable running complexity.
• Drawbacks:
  • Often doesn't lead to a globally optimal solution.

Example: Finding Maximum Root to Leaf Sum in a Tree

• Start from root with sum 3.
• Choose between paths with values 4 and 7 (choose 7 = greedy choice).
• Then choose between 9 and 11 (choose 11 = greedy choice), leading to a sum of 21.
• Non-greedy path (3 -> 4 -> 20) gives a sum of 27.
• Conclusion: Locally optimal choices can lead to suboptimal results.

Properties of Greedy Algorithms

• Greedy-choice property: Making the best immediate choice that seems best.
• Optimal substructure: Efficient global solution derivable from optimal solutions of subproblems.

Comparison with Dynamic Programming

• Unlike dynamic programming, greedy algorithms do not reconsider choices.
• Dynamic programming is exhaustive and guaranteed to find a solution.

Applications of Greedy Algorithms

• Activity Selection Problem
• Huffman Coding
• Job Sequencing Problem
• Fractional Knapsack Problem
• Prim's Minimum Spanning Tree

Conclusion

• Greedy algorithms are useful for certain problems but not guaranteed to provide the best solution in every case.
• Questions and suggestions are welcome.