Computer Science · Grade 12 · Algorithm Analysis and Optimization · Term 2

Greedy Algorithms

Introduction to greedy algorithms and their application in optimization problems, such as coin change or shortest path.

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

About This Topic

Greedy algorithms select the locally optimal choice at each step to achieve a global optimum in optimization problems. Grade 12 students examine core principles through examples like the coin change problem, where choosing the largest denomination first works for standard Canadian coins, and Dijkstra's algorithm for shortest paths, which expands the nearest node first. They identify the greedy choice property and safe substructure that ensure optimality.

This topic anchors the Algorithm Analysis and Optimization unit by contrasting greedy methods with dynamic programming. Students analyze cases where greedy fails, such as activity selection without sorting or knapsack problems, and design simple algorithms to solve real-world scenarios. These skills align with standards CS.AA.11 and CS.P.21, building analytical rigor for advanced computing.

Active learning benefits this topic because students role-play decisions in physical simulations, like sorting coins or plotting paths on maps. Such approaches make abstract trade-offs concrete, reveal failure points through trial and error, and prepare students for coding with intuitive grasp.

Key Questions

1. Explain the core principle of a greedy algorithm and when it is applicable.
2. Analyze scenarios where a greedy approach might not yield the optimal solution.
3. Design a greedy algorithm to solve a simple optimization problem.

Learning Objectives

• Design a greedy algorithm to solve the coin change problem for a given set of denominations.
• Analyze scenarios to identify the greedy choice property and optimal substructure required for greedy algorithms.
• Evaluate the optimality of a greedy algorithm's solution for a given optimization problem.
• Compare the efficiency of a greedy algorithm with other algorithmic approaches for similar problems.

Before You Start

Basic Algorithm Design

Why: Students need a foundational understanding of how algorithms work and how to represent them, such as through pseudocode.

Problem Solving Strategies

Why: Familiarity with breaking down problems into smaller parts and identifying patterns is essential for understanding greedy algorithms.

Key Vocabulary

Greedy Choice Property	A global optimum can be reached by making a locally optimal choice at each step. The choice made at the current step does not affect future choices.
Optimal Substructure	An optimal solution to the problem contains optimal solutions to subproblems. This means that a problem can be solved by combining optimal solutions of its subproblems.
Optimization Problem	A problem where the goal is to find the best solution from a set of possible solutions, often involving minimizing or maximizing a certain value.
Local Optimum	The best possible choice or outcome at a particular step or stage in an algorithm, without considering the overall global outcome.

Watch Out for These Misconceptions

Common Misconception

Greedy algorithms always yield the global optimum.

What to Teach Instead

Counterexamples like 0/1 knapsack show suboptimal results from local choices. Small group packing activities with limited weight capacity let students test greedy picks against exhaustive tries, revealing gaps visually and building discernment.

Common Misconception

Greedy methods check all possibilities like brute force.

What to Teach Instead

Greedy commits early without backtracking, trading completeness for speed. Timed pair simulations of coin change versus enumeration highlight runtime differences, helping students appreciate efficiency trade-offs.

Common Misconception

Shortest path needs dynamic programming, not greedy.

What to Teach Instead

Dijkstra's uses greedy selection on relaxed subproblems. Whole-class graph traversals demonstrate priority queue steps, clarifying why it succeeds where pure greedy might not.

Active Learning Ideas

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.

25 min·Pairs

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.

35 min·Small Groups

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.

40 min·Whole Class

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.

20 min·Individual

Real-World Connections

• Financial analysts use greedy approaches when selecting investments, prioritizing options that offer the highest immediate return, though this may not always lead to the best long-term portfolio.
• Logistics companies like UPS employ greedy algorithms in route planning, aiming to find the shortest path for delivery trucks by selecting the nearest destination at each stop, optimizing for fuel efficiency and time.

Assessment Ideas

Quick Check

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.

Discussion Prompt

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?'

Exit Ticket

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.

Frequently Asked Questions

What is the core principle of a greedy algorithm?

Greedy algorithms make the best local choice at each step, assuming it leads to a global optimum. This requires the greedy choice property, where local picks do not hinder better solutions, and optimal substructure, where solutions build from optimal parts. Students verify through proofs on coin systems or matroids, connecting to optimization theory in the Ontario curriculum.

When does a greedy approach fail to find the optimal solution?

Greedy fails without greedy choice or optimal substructure, as in 0/1 knapsack where picking largest first skips better combinations, or Egyptian fractions needing dynamic programming. Students analyze by constructing counterexamples, comparing greedy outputs to exhaustive or DP results, sharpening algorithm selection skills for CS.AA.11.

What are real-world examples of greedy algorithms?

Coin change with canonical systems, Dijkstra's shortest path in GPS routing, and Prim's or Kruskal's minimum spanning trees in network design apply greedy steps. Huffman coding for compression greedily builds frequent symbols. Classroom designs let students adapt these to problems like task scheduling, linking theory to practice.

How can active learning help students understand greedy algorithms?

Active methods like coin sorting races or graph path voting engage kinesthetic learning, letting students experience local decisions and their global impact firsthand. Group debates on failures, such as knapsack packing, foster peer correction and intuition before code. These build confidence, reduce abstraction barriers, and align with inquiry-based Ontario pedagogy for deeper retention.