Greedy Algorithms

Greedy algorithm makes the locally optimal choice at each step to find the overall optimal way to solve the entire problem. If both of the properties below are true, a greedy algorithm can be used to solve the problem.

• Greedy choice property: A global optimal solution can be reached by choosing the optimal choice at each step.
• Optimal substructure: A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.

Critical Ideas to Think

• In many problems, a greedy strategy does not produce an optimal solution.
• Proving that a greedy algorithm is correct is more of an art than a science. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.

Applications of greedy algorithms: Huffman Encoding, Shortest Path Algorithms, Minimum Spanning Tree, Travelling Salesman Problem, Job Scheduling Problem, Graph Vertex Cover etc .