Greedy Algorithms

---
name: Greedy Algorithms
description: Problem-solving strategy that makes the locally optimal choice at each step with the hope of finding a global optimum
---

# Greedy Algorithms Paradigm

## What It Is
A problem-solving strategy that makes the locally optimal choice at each step with the hope of finding a global optimum. Unlike dynamic programming which considers all possible decisions, greedy algorithms commit to the best immediate option without reconsidering past choices. The key insight: for certain problems, always choosing what looks best right now leads to the overall best solution.

## When to Use It
- Problem has **greedy choice property** (local optimal choices lead to global optimum)
- Problem has **optimal substructure** (optimal solution contains optimal subsolutions)
- Need fast, simple solution (greedy is usually O(n log n) or better)
- Can prove that greedy choice never needs to be undone
- Making irreversible decisions is acceptable (no backtracking needed)
- Problem involves optimization with ordering/scheduling/selection

**Key Test**: Can you prove that choosing the best option now won't block a better overall solution later?

## Execution Steps

### 1. Evaluate Available Options
At each decision point, identify all valid choices. Define what "best" means for your problem (largest, smallest, earliest deadline, highest ratio). Sort or prioritize options if needed.

**Action**: List all candidates. Define the selection criterion clearly (e.g., "choose activity with earliest finish time" or "select item with highest value/weight ratio").

### 2. Make the Greedy Choice
Select the option that appears optimal according to your criterion. Commit to this choice immediately without considering future consequences. This is the core greedy step.

**Action**: Pick the best option from available candidates. Add it to your solution. This choice is final and irreversible.

### 3. Update State
Remove the chosen option from consideration. Update the problem state based on your choice. Define the new subproblem that remains.

**Action**: Mark chosen item as used. Update constraints (remaining capacity, time, etc.). Recompute what's now available for next iteration.

### 4. Iterate
Repeat steps 1-3 until reaching a solution or no further progress is possible. Each iteration solves a smaller subproblem.

**Action**: Loop until goal achieved, resources exhausted, or no valid choices remain. Return accumulated solution.

### 5. Verify Optimality
Prove (or test) that your greedy strategy produces optimal results. Common proof techniques: exchange argument, greedy stays ahead, structural induction.

**Action**: For known problems (MST, shortest path), use established proofs. For new problems, construct counterexamples to test, or prove correctness formally.

## Real-World Applications

**Scheduling & Resource Allocation**
- Activity selection: conference room booking, CPU task scheduling
- Job sequencing: minimize weighted completion time, maximize throughput
- Huffman coding: optimal prefix-free codes for data compression
- Interval scheduling: maximize non-overlapping meetings

**Graph Algorithms**
- Dijkstra's shortest path: GPS navigation, network routing (OSPF protocol)
- Prim's/Kruskal's MST: network design, circuit layout, cluster analysis
- Fractional knapsack: portfolio optimization with divisible assets

**Network & Routing**
- Load balancing: distribute requests to servers (least loaded server)
- Bandwidth allocation: maximize network utilization
- Packet routing: next-hop forwarding (shortest path to destination)

**Financial & Trading**
- Coin change with specific denominations: make change with fewest coins
- Stock trading: maximize profit with one buy-sell (best time to buy/sell)
- Fractional resource allocation: allocate budget to projects by ROI

**Data Compression**
- Huffman trees: ZIP, JPEG, MP3 compression
- Run-length encoding: simple compression for repeated data
- Optimal merge patterns: external sorting of sorted runs

**Machine Learning**
- Feature selection: forward/backward selection by information gain
- K-means clustering: assign points to nearest centroid
- Decision tree splitting: choose best split by Gini/entropy

## Anti-Patterns

**Using greedy when it doesn't guarantee optimality** → Produces suboptimal results; verify greedy choice property first or use DP.

**Not sorting when needed** → Greedy algorithms often require sorted input; missing this step breaks the strategy.

**Confusing greedy with dynamic programming** → If choices overlap or need reconsideration, use DP; greedy is for irreversible local decisions.

**Applying to 0/1 knapsack** → Greedy fails here (DP required); only works for fractional knapsack.

**Ignoring problem constraints** → Greedy choice must respect all constraints; check feasibility before committing.

**No proof of correctness** → Just because greedy seems to work doesn't mean it's optimal; always verify with proof or exhaustive testing.

## Success Metrics
- Solution matches known optimal value (for problems with established answers)
- Algorithm runs in expected time (typically O(n log n) for sorting-based greedy)
- Proof of correctness established (exchange argument, greedy stays ahead)
- Empirical testing on edge cases confirms optimality
- Simplicity: code is straightforward, easy to understand and maintain

## Related Frameworks
- **Dynamic Programming**: When greedy fails, DP often succeeds (but slower)
- **Divide and Conquer**: Both make decisions and recurse, but D&C doesn't commit locally
- **Backtracking**: For constraint satisfaction when greedy is insufficient
- **Primal-Dual Algorithms**: Greedy with duality theory for approximation algorithms
- **Matroid Theory**: Mathematical framework proving when greedy works

## Common Pitfalls
- Assuming greedy always works (it doesn't - most optimization problems need DP or search)
- Not proving correctness (greedy algorithms are easy to get wrong)
- Choosing wrong greedy criterion (e.g., sorting by value instead of value/weight ratio)
- Forgetting to sort input when order matters
- Applying greedy to problems requiring backtracking (e.g., N-Queens, Sudoku)
- Not handling ties in selection criterion (can lead to non-deterministic results)

## Tools & Resources
- **Visualization**: VisuAlgo (visualgo.net) for greedy algorithm animations
- **Practice**: LeetCode greedy tag (~150 problems), Codeforces greedy category
- **Books**: "Algorithm Design" (Kleinberg & Tardos), "Introduction to Algorithms" (CLRS)
- **Proof Techniques**: "Exchange argument" tutorial, "Greedy stays ahead" proof pattern
- **Counterexample Testing**: Generate random inputs, compare greedy vs. brute force on small instances

## Classic Greedy Algorithms

**Activity Selection**: Choose activities with earliest finish time → maximizes number of non-overlapping activities

**Fractional Knapsack**: Sort items by value/weight ratio, take highest ratios first → optimal value

**Huffman Coding**: Build tree by repeatedly merging two lowest-frequency nodes → optimal prefix-free code

**Dijkstra's Algorithm**: Always expand nearest unvisited node → shortest paths from source

**Kruskal's MST**: Add cheapest edge that doesn't create cycle → minimum spanning tree

**Prim's MST**: Grow tree by adding cheapest edge to current tree → minimum spanning tree

**Coin Change (specific denominations)**: Always take largest coin ≤ remaining amount → fewest coins (works for standard denominations like US coins)

## When Greedy Fails

**0/1 Knapsack**: Can't split items, so greedy by value/weight fails. Need DP.

**Longest Path**: Greedy (always choose longest available edge) fails. NP-hard, need exponential search.

**Traveling Salesman**: Greedy (nearest neighbor) gives 2-approximation but not optimal. Need sophisticated approaches.

**Job Scheduling with Dependencies**: Greedy ignores dependencies. Need topological sort + DP.

**Fair Division**: Greedy may give one party too much. Need game-theoretic approaches.

---
*Framework Type*: Algorithm Design Paradigm
*Domain*: Computer Science, Optimization
*Practitioner Score*: 9/10 - Powers many production algorithms (Dijkstra, MST, Huffman)
*Complexity*: Medium - Conceptually simple, but proving correctness is non-trivial
*Prerequisites*: Sorting algorithms, basic graph theory, proof techniques (induction, contradiction)