Computer Science · 12th Grade

Active learning ideas

Greedy Algorithms and Their Limitations

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.

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

• 30–40 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Simulation Game
• 30 min · Small Groups

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.

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.

What to look for

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.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Formal Debate
• 40 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.

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.

What to look for

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.

• Analyze
• Evaluate
• Create
• Self-Management
• Decision-Making

Activity 03

• Gallery Walk
• 35 min · Pairs

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.

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.

What to look for

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.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 04

• Think-Pair-Share
• 30 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.

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.

What to look for

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.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

A few notes on teaching this unit

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.

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.

---

Watch Out for These Misconceptions

• During 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.

  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.

• During the Structured Debate, watch for students who generalize that greedy algorithms are always faster than dynamic programming without considering correctness.

  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.

• During Think-Pair-Share, watch for students who assume the greedy choice is the most obvious or largest value option.

  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.

---

Methods used in this brief

• Simulation Game
• Formal Debate
• Gallery Walk
• Think-Pair-Share