Greedy Algorithms and Their LimitationsActivities & Teaching Strategies
Active learning works for greedy algorithms because students often assume a greedy strategy is correct after testing a few friendly cases. By playing with counterexamples and debating trade-offs, students confront the limitations of intuition and develop habits of rigorous testing and proof.
Learning Objectives
- 1Analyze the conditions under which a greedy algorithm guarantees an optimal solution for a given problem.
- 2Critique the limitations of greedy approaches by constructing specific counterexamples that demonstrate sub-optimal outcomes.
- 3Design a problem solvable by a greedy strategy and justify why the greedy choice property holds for that problem.
- 4Compare the time complexity of greedy algorithms to brute-force or dynamic programming solutions for similar problems.
Want a complete lesson plan with these objectives? Generate a Mission →
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.
Prepare & details
Analyze the conditions under which a greedy algorithm guarantees an optimal solution.
Facilitation Tip: During The Greedy Coin Game, circulate and ask each pair to explain their algorithm to you before they test it on a new coin system.
Setup: Flexible space for group stations
Materials: Role cards with goals/resources, Game currency or tokens, Round tracker
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.
Prepare & details
Critique the limitations of greedy approaches by identifying counterexamples.
Facilitation Tip: In the Structured Debate, assign roles beforehand so students prepare both sides of the argument and stay engaged.
Setup: Two teams facing each other, audience seating for the rest
Materials: Debate proposition card, Research brief for each side, Judging rubric for audience, Timer
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.
Prepare & details
Design a problem that can be effectively solved using a greedy strategy and justify the choice.
Facilitation Tip: For the Gallery Walk, provide a checklist of what to look for in each counterexample poster so students analyze rather than read passively.
Setup: Wall space or tables arranged around room perimeter
Materials: Large paper/poster boards, Markers, Sticky notes for feedback
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.
Prepare & details
Analyze the conditions under which a greedy algorithm guarantees an optimal solution.
Facilitation Tip: During Think-Pair-Share, give students two minutes of private think time before pairing so quieter students have a chance to formulate ideas.
Setup: Standard classroom seating; students turn to a neighbor
Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs
Teaching This Topic
Teachers should present greedy algorithms as elegant shortcuts with clear conditions for correctness. Emphasize that the goal is not speed alone, but proving the greedy choice leads to an optimal solution. Avoid rushing through examples; instead, slow down to model how to construct counterexamples systematically. Research shows that students learn algorithmic thinking best when they confront their own misconceptions directly through structured disagreement and hands-on testing.
What to Expect
Students will move from believing greedy algorithms always work to recognizing when they do and do not apply. Success looks like students articulating why a greedy choice is correct, spotting counterexamples, and justifying their reasoning in written and verbal form.
These activities are a starting point. A full mission is the experience.
- Complete facilitation script with teacher dialogue
- Printable student materials, ready for class
- Differentiation strategies for every learner
Watch Out for These Misconceptions
Common MisconceptionDuring The Greedy Coin Game, watch for students who declare the greedy algorithm always correct after solving a few simple coin systems like 1, 5, 10, 25.
What to Teach Instead
Use the modified coin system activity (denominations 1, 3, 4) during the game to show that the greedy choice (taking largest first) produces 4 + 1 + 1 = 3 coins for 6, but the optimal is 3 + 3 = 2 coins. Ask students to document this counterexample in their lab notes.
Common MisconceptionDuring the Structured Debate, watch for students who generalize that greedy algorithms are always faster than dynamic programming without considering correctness.
What to Teach Instead
Have students compare the runtime of a greedy coin algorithm with a dynamic programming coin algorithm on the same coin system, then discuss why speed only matters if the answer is correct. Use the debate prompts to focus on trade-offs between correctness and efficiency.
Common MisconceptionDuring Think-Pair-Share, watch for students who assume the greedy choice is the most obvious or largest value option.
What to Teach Instead
Provide a set of activity selection problems where the earliest ending activity is not the one with the highest value or longest duration. Ask students to justify their greedy criterion in writing and compare their reasoning with peers to see that the greedy choice depends on the problem structure.
Assessment Ideas
After The Greedy Coin Game, 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.
During the Structured Debate, facilitate a class discussion 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.
After the Gallery Walk, 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.
Extensions & Scaffolding
- Challenge students to design a coin system where the greedy algorithm fails for amounts greater than 10.
- For students who struggle, provide a partially completed greedy algorithm template with missing conditions they must fill in.
- Allow extra time for students to explore why Huffman encoding works by tracing the construction of a small tree step by step.
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. |
Suggested Methodologies
More in Complex Algorithms and Optimization
Algorithmic Efficiency and Big O Notation
Students learn to mathematically evaluate the performance of code as input size grows, comparing linear, logarithmic, and quadratic growth patterns.
2 methodologies
Analyzing Time and Space Complexity
Students delve into the specifics of calculating time and space complexity for various operations, understanding the trade-offs involved.
2 methodologies
Recursive Problem Solving Fundamentals
Students master the concept of self-referential functions to solve problems, identifying base cases and recursive steps.
2 methodologies
Advanced Recursion: Backtracking and Memoization
Students explore advanced recursive techniques like backtracking for combinatorial problems and memoization for optimizing recursive calls.
2 methodologies
Basic Searching Algorithms: Linear and Binary Search
Students implement and compare linear and binary search algorithms, understanding their applicability based on data organization.
2 methodologies
Ready to teach Greedy Algorithms and Their Limitations?
Generate a full mission with everything you need
Generate a Mission