Computer Science · 12th Grade · Complex Algorithms and Optimization · Weeks 1-9

Greedy Algorithms and Their Limitations

Students explore greedy algorithms, understanding when they provide optimal solutions and when they fall short.

• Common Core State Standards
• CSTA: 3B-AP-12
• CCSS.ELA-LITERACY.RST.11-12.3

About This Topic

Greedy algorithms make locally optimal decisions at each step with the hope of reaching a globally optimal solution. In 12th-grade computer science, students encounter greedy strategies in classic problems like coin change, activity selection, and Huffman encoding. The elegance of greedy algorithms is their simplicity: pick the best available option right now and move on, without backtracking. This makes them computationally efficient compared to exhaustive search approaches, and they are foundational in the CSTA curriculum for understanding algorithmic design.

The challenge is knowing when to trust a greedy approach. Students learn to construct counterexamples, proving that a strategy that seems correct can fail for specific inputs. The classic example is a coin system with unusual denominations where always picking the largest coin fails to minimize the count. Understanding these limitations prepares students for more comprehensive approaches like dynamic programming, which guarantees correctness where greedy methods do not.

Active learning is especially valuable here because greedy failures become visceral when students run simulated scenarios and discover firsthand that their chosen strategy led them astray. Structured debates and counterexample-finding challenges build the critical thinking engineers use when validating algorithm correctness, skills that transfer directly to software testing and formal reasoning.

Key Questions

1. Analyze the conditions under which a greedy algorithm guarantees an optimal solution.
2. Critique the limitations of greedy approaches by identifying counterexamples.
3. Design a problem that can be effectively solved using a greedy strategy and justify the choice.

Learning Objectives

• Analyze the conditions under which a greedy algorithm guarantees an optimal solution for a given problem.
• Critique the limitations of greedy approaches by constructing specific counterexamples that demonstrate sub-optimal outcomes.
• Design a problem solvable by a greedy strategy and justify why the greedy choice property holds for that problem.
• Compare the time complexity of greedy algorithms to brute-force or dynamic programming solutions for similar problems.

Before You Start

Introduction to Algorithms and Complexity

Why: Students need a foundational understanding of what an algorithm is and how to analyze its efficiency (e.g., Big O notation) before exploring specific algorithmic paradigms.

Basic Data Structures (Arrays, Lists, Trees)

Why: Greedy algorithms often operate on or produce data structures like sorted lists or trees (e.g., Huffman trees), requiring familiarity with these concepts.

Key Vocabulary

Greedy Choice Property	A property stating that a globally optimal solution can be arrived at by making a locally optimal choice at each step, without reconsidering previous choices.
Optimal Substructure	A property where an optimal solution to a problem contains within it optimal solutions to subproblems. This is often a prerequisite for greedy algorithms.
Counterexample	A specific instance or input for which a proposed algorithm or strategy fails to produce the correct or optimal result.
Activity Selection Problem	A classic problem where the goal is to select the maximum number of non-overlapping activities from a set of activities, each with a start and finish time.

Watch Out for These Misconceptions

Common Misconception

A greedy algorithm that works on a few test cases is always correct.

What to Teach Instead

Correctness must be proven, not just tested. A greedy strategy may work for most inputs but fail for a specific edge case. Encouraging students to actively seek counterexamples rather than confirming the algorithm with easy examples builds a testing habit that transfers directly to rigorous software quality assurance.

Common Misconception

Greedy algorithms are always faster than dynamic programming.

What to Teach Instead

Greedy algorithms are typically faster, but the real distinction is correctness: a greedy approach may produce the wrong answer where dynamic programming guarantees the right one. Speed is only an advantage if the greedy strategy actually solves the problem. Group comparisons of greedy versus DP solutions on the same problem make this tradeoff concrete.

Common Misconception

The 'greedy' choice is always the obvious one.

What to Teach Instead

What counts as the greedy choice depends entirely on the problem structure. For activity selection, the greedy choice is the activity that ends earliest, not the one that starts earliest or runs the longest. Peer comparison of different greedy interpretations helps students see that choosing the right greedy criterion requires careful problem analysis.

Active Learning Ideas

Simulation Game: The Greedy Coin Game

Give student groups two different coin systems: one where the greedy algorithm works (US coins: 25, 10, 5, 1) and one where it fails (coins: 4, 3, 1, making change for 6). Students must make change using the greedy rule of always picking the largest coin that fits, then verify whether they achieved the minimum number of coins. Groups compare results and discuss why one system succeeded and the other did not.

30 min·Small Groups

Formal Debate: Greedy or Not?

Present students with four real-world optimization problems (routing packages, scheduling classes, building a Huffman tree, packing a knapsack). Teams argue for or against using a greedy strategy for their assigned problem, citing specific scenarios where their position holds. The class votes after each debate, then the teacher reveals the mathematically correct answer and discusses what made the greedy approach viable or not.

40 min·Small Groups

Gallery Walk: Famous Counterexamples

Post 5 greedy algorithm posters around the room, each showing a problem and a greedy strategy. Students rotate, first predicting whether the greedy strategy is optimal, then finding or verifying a counterexample at each station. After the walk, the class compiles a shared list of conditions under which greedy algorithms are provably correct.

35 min·Pairs

Think-Pair-Share: Design for Greediness

Each student individually designs a simple optimization problem that is intentionally solvable by a greedy algorithm. They pair up, swap problems, and attempt to break their partner's problem with a counterexample. This reversal of the typical problem-solving direction deepens understanding of what structural properties make greedy strategies safe to apply.

30 min·Pairs

Real-World Connections

• Financial advisors use greedy-like strategies when recommending investment portfolios, prioritizing investments with the highest immediate returns, though this doesn't always guarantee the best long-term outcome.
• Network routing protocols, such as OSPF (Open Shortest Path First), often employ greedy algorithms to find the shortest path for data packets between network nodes, making quick decisions based on current link costs.
• Huffman coding, used in data compression for formats like ZIP files and JPEG images, applies a greedy algorithm to build optimal prefix codes by repeatedly merging the two least frequent symbols.

Assessment Ideas

Quick Check

Present students with a modified coin system (e.g., denominations 1, 3, 4) and ask them to find the minimum number of coins to make 6. Then, ask them to explain why the greedy approach (always picking the largest coin first) fails for this specific system.

Discussion Prompt

Facilitate a class debate on the statement: 'Greedy algorithms are always the most efficient solution.' Students should use examples of problems where greedy works well (like activity selection) and problems where it fails (like the coin change problem with specific denominations) to support their arguments.

Exit Ticket

Ask students to write down one problem that can be optimally solved using a greedy algorithm and one problem that cannot. For each, they should briefly explain why the greedy choice property applies or does not apply.

Frequently Asked Questions

What makes a problem suitable for a greedy algorithm?

Two structural properties must hold: the greedy choice property (a locally optimal choice leads to a globally optimal solution) and optimal substructure (an optimal solution to the whole problem contains optimal solutions to its subproblems). Both must be present for a greedy algorithm to be provably correct, not just fast.

Can greedy algorithms be used in real software applications?

Yes, frequently. Dijkstra's shortest path algorithm is greedy, as is Huffman compression used in JPEG and MP3 encoding. Scheduling algorithms in operating systems often use greedy heuristics. Understanding when greedy strategies are reliable is essential for systems programming and algorithm design at every level.

How does active learning help students understand greedy algorithm limitations?

Running simulations where a greedy strategy visibly fails, like making change with non-standard coins, creates a memorable experience that challenges overconfidence in intuitive solutions. Students who have been fooled by a greedy approach they trusted are far more likely to look for counterexamples in future algorithm design.

What is the difference between a greedy algorithm and dynamic programming?

Greedy algorithms make one irrevocable optimal decision at each step and never reconsider. Dynamic programming solves all subproblems and builds up to the full solution, guaranteeing correctness. Greedy is faster when it applies, but dynamic programming is the reliable fallback when the greedy choice property cannot be proven.