Computer Science · Grade 12

Active learning ideas

Greedy Algorithms

Active learning fits greedy algorithms well because the topic balances abstract reasoning with hands-on problem solving. Students need to see how local choices cascade into global outcomes, which simulations and puzzles make concrete rather than abstract. The topic’s counterexamples only click when students test greedy picks against brute-force results themselves.

• Ontario Curriculum Expectations
• CS.AA.11
• CS.P.21

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

Activity 01

• Case Study Analysis
• 25 min · Pairs

Pairs Simulation: Coin Change Race

Provide pairs with play coins in standard denominations. One partner requests random amounts under $2; the other assembles change greedily. Switch roles, then compare to minimal coin counts found by recounting. Discuss why it works here.

Explain the core principle of a greedy algorithm and when it is applicable.

Facilitation Tip

During the Coin Change Race, circulate with a timer and remind pairs that the goal is to compare their greedy steps to the final count, not just to finish first.

What to look for

Present students with a modified coin system (e.g., denominations 1, 4, 6) and ask them to find the minimum number of coins to make change for 8. Have them write down the greedy choices they made at each step and the final count. Check if their choices align with the greedy principle.

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

Activity 02

• Case Study Analysis
• 35 min · Small Groups

Small Groups: Interval Scheduling Puzzle

Give groups paper slips with meeting start and end times. Sort by earliest finish time and select greedily. Compare group schedules to an optimal one provided. Identify proof of optimality through discussion.

Analyze scenarios where a greedy approach might not yield the optimal solution.

Facilitation Tip

For the Interval Scheduling Puzzle, provide colored strips so groups can physically rearrange tasks and visually spot overlaps or gaps.

What to look for

Pose the following scenario: 'Imagine you are planning a road trip and want to visit as many cities as possible within a week, starting from your home city. Each city has a travel time from the previous one. How would you design a greedy algorithm to select the next city to visit at each step? What are the potential pitfalls of this approach?'

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

Activity 03

• Case Study Analysis
• 40 min · Whole Class

Whole Class: Dijkstra's Path Walkthrough

Draw a weighted graph on the board. Class votes on next node by lowest distance. Update distances collectively. Trace path and contrast with non-greedy choices to see efficiency.

Design a greedy algorithm to solve a simple optimization problem.

Facilitation Tip

While walking through Dijkstra's algorithm, draw the priority queue on the board and have students call out the next node to expand before you reveal the next step.

What to look for

Ask students to identify one problem where a greedy algorithm is guaranteed to work and one problem where it might fail. For each, they should briefly explain why the greedy approach is suitable or unsuitable.

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

Activity 04

• Case Study Analysis
• 20 min · Individual

Individual: Greedy Code Sketch

Students pseudocode a greedy algorithm for Huffman coding prefixes. Test with sample frequencies. Pair-share to verify greedy property before full implementation.

Explain the core principle of a greedy algorithm and when it is applicable.

What to look for

Present students with a modified coin system (e.g., denominations 1, 4, 6) and ask them to find the minimum number of coins to make change for 8. Have them write down the greedy choices they made at each step and the final count. Check if their choices align with the greedy principle.

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

A few notes on teaching this unit

Teachers introduce greedy algorithms by contrasting their speed with brute-force methods, using timers in simulations to show the difference. Avoid overloading students with theory upfront; let examples drive the principles. Research shows students grasp the greedy choice property better when they first see it work in familiar contexts like coin change, then encounter a counterexample like 0/1 knapsack to refine their understanding.

By the end of these activities, students will articulate when greedy algorithms succeed or fail, justify their steps with the greedy choice property, and compare greedy methods to other approaches. They will also explain efficiency trade-offs using runtime data from simulations. Clear justifications, not just answers, mark successful learning.

---

Watch Out for These Misconceptions

• During the Interval Scheduling Puzzle, watch for students assuming greedy selection by earliest finish time always gives the maximum number of non-overlapping intervals.

  Use the colored strips to have them test a counterexample, such as intervals A: 1-4, B: 2-3, C: 3-5. Ask them to try both greedy and exhaustive selections to see where the greedy choice fails to cover the most intervals.

• During the Coin Change Race, watch for students assuming that always picking the largest denomination first will always yield the minimum number of coins.

  Provide a modified coin system (e.g., denominations 1, 4, 6) and challenge pairs to find a counterexample where the greedy choice does not yield the minimum number of coins, then compare their results with the standard Canadian coin system.

• During Dijkstra's Path Walkthrough, watch for students believing that greedy node selection works for all shortest-path problems without considering edge weights or negative cycles.

  Pose a follow-up graph with a negative-weight edge and ask students to run Dijkstra's steps to see where the greedy selection fails, then discuss why dynamic programming or Bellman-Ford is needed in such cases.

---

Methods used in this brief

• Case Study Analysis