Greedy Algorithm

Definitions

1. An algorithm that builds a solution incrementally by always making the locally optimal choice at each step, hoping this leads to a globally optimal solution. Works perfectly for some problems (Huffman coding, MST) but fails for others (knapsack, TSP).

   In plain English: Always pick whatever looks best right now and never look back. Sometimes that gives you the perfect answer; sometimes it doesn't.

   Example: "Dijkstra's algorithm is greedy — it always expands the nearest unvisited node — and it works because edge weights are non-negative."

Related Terms

• Dynamic Programming
• Amortized Analysis
• Big Theta
• Knuth
• Merge Sort
• Provider
• Quick Sort
• Round Robin
• Bit Manipulation
• Composite
• Constraint Programming