DataTerminology.comNEW
Algorithmic strategy that makes locally optimal choices at each step, aiming for a globally optimal or near-optimal solution.
DESCRIPTION
Greedy algorithms build solutions incrementally by choosing the best immediate option according to a heuristic. They are efficient and simple but may fail to find global optima. Correctness often depends on properties like matroids or exchange arguments. Classic examples include Huffman coding, Prim’s and Kruskal’s MST algorithms, and interval scheduling. Greedy approaches also serve as fast approximation methods for NP-hard problems.
ALTERNATIVE DEFINITIONS
Wikipedia
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
Heuristic focus on local optimal choices per stage.
MIT OpenCourseWare
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
Highlights incremental construction with immediate-benefit heuristic.
CP-Algorithms
Greedy algorithms are a class of algorithms that make the best decision locally at each step.
Emphasizes local decision-making in competitive programming context.
RELATED TERMS
Backtracking Local Optimum Approximation Algorithm Knapsack Problem Prim’s Algorithm Kruskal’s Algorithm Huffman Coding Interval Scheduling Matroid
COMPETING TERMS
Dynamic Programming Global Optimization
RELATIONS
- Broader: Algorithm
KNOWLEDGE AREAS
Mathematics Software Engineering Data Science AI
TARGET AUDIENCE
Software Developer Data Scientist AI Engineer
EXTERNAL SOURCES
- Wikipedia - Greedy algorithm
- Princeton Algorithms - Textbook site with greedy examples
- CP-Algorithms - Greedy algorithm techniques
- MIT OpenCourseWare - Lectures on greedy algorithms
TOP QUESTIONS
When does a Greedy Algorithm guarantee optimality?
When the problem has a greedy-choice property and optimal substructure, often formalized via matroids or exchange arguments.
Category: Requirements
What is a classic example of a Greedy Algorithm?
Huffman coding constructs optimal prefix codes by greedily merging least frequent symbols.
Category: Example
How do Greedy Algorithms compare to Dynamic Programming?
Greedy chooses local best without revisiting states; dynamic programming explores subproblems systematically to ensure global optimality.
Category: Distinction
What are common pitfalls with Greedy Algorithms?
Assuming greedy optimality without proof, using incorrect heuristics, and ignoring counterexamples.
Category: Mistakes
Are Greedy Algorithms useful for NP-hard problems?
Yes, they often provide fast approximations with provable bounds, like set cover’s logarithmic approximation.
Category: Opinion
How do you validate a Greedy Algorithm?
Provide a proof using exchange arguments or matroid theory, and test on edge cases.
Category: Testing
Can Greedy Algorithms be combined with local search?
Yes, greedy initialization followed by local improvements can achieve better solutions.
Category: Best practices
What is the greedy-choice property?
It states that a globally optimal solution can be constructed by making a locally optimal choice.
Category: Definition
Where do Greedy Algorithms appear in graph theory?
Minimum spanning tree algorithms (Prim’s, Kruskal’s) and scheduling problems are well-known greedy applications.
Category: Overview