Greedy Algorithm

Definitions

1. An algorithmic paradigm that makes the locally optimal choice at each step, hoping to reach a globally optimal solution. Works for problems with the greedy-choice property (local optima lead to global optimum). Examples: Huffman coding, Dijkstra's algorithm, activity selection, and minimum spanning tree. Doesn't always yield optimal results (e.g., coin change problem with arbitrary denominations).

   In plain English: An algorithm that always picks the best-looking option at each step, which sometimes leads to the best overall solution.

   Example: "The greedy approach for making change works with standard denominations (25¢, 10¢, 5¢, 1¢) but fails with arbitrary values like 30¢, 24¢, 1¢."

Related Terms

• Cache
• Data Structure
• Profile
• Tail Call
• Vectorization
• Rolling Update
• Dijkstra's Algorithm
• Dynamic Programming
• Divide and Conquer