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

Algorithm Design Strategies

Reviewing various algorithm design paradigms: brute force, divide and conquer, greedy, dynamic programming, and backtracking.

• Ontario Curriculum Expectations
• CS.AA.13
• CS.P.23

About This Topic

Algorithm design strategies equip Grade 12 students with methods to tackle complex problems systematically. They review brute force, which exhaustively tries all options; divide and conquer, which recursively splits tasks like in merge sort; greedy approaches, which select immediate best choices as in Dijkstra's algorithm; dynamic programming, which builds solutions from subproblems with memoization like in Fibonacci; and backtracking, which trials paths and retracts errors, as in the N-queens puzzle. These connect to key questions on comparing strengths, such as time complexity trade-offs, selecting based on problem traits, and justifying designs.

Within Ontario's Computer Science curriculum, this topic aligns with standards CS.AA.13 on analysis and CS.P.23 on programming. It builds systems thinking for optimization in units like graph algorithms, preparing students for postsecondary computing or software development roles. Students analyze when brute force suffices for small inputs versus dynamic programming for scalability.

Active learning excels with this topic through comparative implementations and live runtimes. When students code multiple strategies for one problem, measure Big-O empirically, and debate selections in groups, they internalize nuances. Peer coding reviews strengthen justification, turning theoretical paradigms into practical tools.

Key Questions

1. Compare the strengths and weaknesses of different algorithm design strategies.
2. Explain how to select the most appropriate algorithm design strategy for a given problem.
3. Design an algorithm for a complex problem, justifying the chosen design strategy.

Learning Objectives

• Compare the time and space complexity of brute force, divide and conquer, greedy, dynamic programming, and backtracking algorithms for a given problem.
• Explain the core principles and typical use cases for each algorithm design strategy: brute force, divide and conquer, greedy, dynamic programming, and backtracking.
• Design an algorithm for a moderately complex problem, selecting and justifying the most appropriate design strategy from the studied paradigms.
• Evaluate the trade-offs between algorithm efficiency and implementation complexity for different design strategies.
• Critique a proposed algorithm solution by identifying its design strategy and assessing its suitability and potential optimizations.

Before You Start

Introduction to Algorithms and Complexity

Why: Students need a foundational understanding of what algorithms are and how to measure their efficiency using Big O notation before exploring different design strategies.

Recursion

Why: Many advanced algorithm design strategies, particularly divide and conquer and dynamic programming, rely heavily on the concept and implementation of recursion.

Data Structures (Arrays, Lists, Trees, Graphs)

Why: The choice of data structure significantly impacts algorithm design and efficiency, and students must be familiar with common structures to apply these strategies effectively.

Key Vocabulary

Brute Force	An algorithm design strategy that systematically enumerates all possible solutions to a problem and checks each one until the optimal solution is found. It is often simple to implement but can be very inefficient for large inputs.
Divide and Conquer	An algorithm design strategy that recursively breaks down a problem into two or more smaller sub-problems of the same or related type, solves them independently, and then combines their solutions to solve the original problem. Examples include merge sort and quicksort.
Greedy Algorithm	An algorithm design strategy that makes the locally optimal choice at each stage with the hope of finding a global optimum. It does not reconsider previous choices. Examples include Dijkstra's algorithm for shortest paths.
Dynamic Programming	An algorithm design strategy that solves complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing their solutions to avoid redundant computations. It is often used for optimization problems.
Backtracking	An algorithm design strategy that explores potential solutions incrementally. If a partial solution cannot be completed to a valid solution, the algorithm 'backtracks' to a previous decision point and tries a different option. It is often used for constraint satisfaction problems.

Watch Out for These Misconceptions

Common Misconception

Greedy algorithms always yield optimal solutions.

What to Teach Instead

Counterexamples like the knapsack problem show local optima fail globally. Group brainstorming of test cases, followed by paired coding of greedy versus dynamic programming, reveals patterns and builds selection skills through direct comparison.

Common Misconception

Dynamic programming just means more recursion without benefits.

What to Teach Instead

It requires memoization to avoid recomputing subproblems. Students trace table fills on whiteboards in pairs, timing recursive versus memoized versions, to observe exponential speedups and appreciate the paradigm's power.

Common Misconception

Brute force has no practical value.

What to Teach Instead

It verifies optimal solutions or works for tiny inputs. Whole-class runtime demos on growing datasets highlight its role, helping students value it alongside efficient methods through empirical evidence.

Active Learning Ideas

Pairs Duel: Brute Force vs Divide and Conquer

Pairs implement both strategies for finding maximum subarray sum. First, code brute force (nested loops), then divide and conquer (recursive splits). Test on sample arrays, record runtimes, and graph results for class shareout.

35 min·Pairs

Small Groups: Greedy Coin Change Challenge

Groups design a greedy algorithm for minimum coins using Canadian denominations. Test cases with suboptimal results, then discuss limitations. Modify for dynamic programming and compare outputs.

45 min·Small Groups

Whole Class: Backtracking Strategy Vote

Project a Sudoku puzzle. Class proposes backtracking steps live on shared code. Vote on path prunings, simulate fills, and time solutions to see efficiency gains.

30 min·Whole Class

Individual: Paradigm Picker Worksheet

Students get five problems (e.g., traveling salesman, longest common subsequence). Select and sketch best strategy with justification. Share one via gallery walk for feedback.

25 min·Individual

Real-World Connections

• Software engineers at Google use dynamic programming to optimize routing algorithms for Google Maps, finding the most efficient paths for millions of users daily.
• Financial analysts employ greedy algorithms to construct optimal investment portfolios, selecting assets that offer the highest potential return at each step based on current market conditions.
• Game developers utilize backtracking algorithms to solve complex puzzles within video games, such as finding a path through a maze or determining optimal moves in a turn-based strategy game.

Assessment Ideas

Quick Check

Present students with three short problem descriptions (e.g., finding the shortest path in a small graph, sorting a list of numbers, finding all possible combinations of items). Ask them to identify which algorithm design strategy (brute force, divide and conquer, greedy, dynamic programming, backtracking) would be most appropriate for each problem and briefly justify their choice.

Discussion Prompt

Facilitate a class discussion using the prompt: 'Imagine you are tasked with designing an algorithm to find the optimal seating arrangement for a large conference to minimize travel time for attendees. Which algorithm design strategy would you lean towards, and why? What are the potential pitfalls of your chosen strategy, and how might you mitigate them?'

Peer Assessment

Assign students to work in pairs to design a brute force algorithm for a simple problem (e.g., finding all pairs of numbers in a list that sum to a target). Then, have them swap their code and a problem description with another pair. Each pair must critique the other's code for clarity and correctness, and suggest if a more efficient strategy could be applied and why.

Frequently Asked Questions

How to teach algorithm design strategies in Ontario Grade 12 CS?

Start with problem classification: exhaustive needs versus recursive splits. Use visual aids like flowcharts for each paradigm, then assign coding tasks matching standards CS.AA.13 and CS.P.23. Emphasize Big-O analysis through student-led runtime charts to compare trade-offs concretely.

When to choose dynamic programming over greedy?

Use dynamic programming for overlapping subproblems needing exact optima, like sequence alignment, where greedy fails on integers. Greedy suits matroids like minimum spanning trees. Students practice by prototyping both on coin change, measuring accuracy and speed to decide based on constraints.

Active learning ideas for algorithm paradigms?

Incorporate strategy showdowns: students code two paradigms per problem in pairs, benchmark runtimes, and present trade-offs. Add debates on selections for real problems like route planning. These hands-on tasks, aligned with inquiry-based learning, help students justify choices and retain concepts through collaboration and data.

Common errors in backtracking algorithms?

Students often forget pruning invalid paths early, leading to timeouts. They overlook state representation, like board symmetry in puzzles. Address via step-by-step whiteboard simulations in small groups, coding with debug prints, and peer reviews to catch omissions before full implementation.