Computer Science · Grade 12

Active learning ideas

Dynamic Programming

Dynamic programming requires students to shift from linear problem-solving to strategic planning, where efficiency depends on recognizing patterns in overlapping steps. Active learning lets them experience the 'aha' moment when repeated work is eliminated, building intuition that static examples cannot provide.

• Ontario Curriculum Expectations
• CS.AA.12
• CS.P.22

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

Activity 01

• Flipped Classroom
• 45 min · Pairs

Pair Programming: Fibonacci Showdown

Pairs implement recursive Fibonacci, then add memoization and bottom-up tabulation. They time each version with large inputs and graph results. Discuss which approach scales best.

Differentiate between dynamic programming and recursion with memoization.

Facilitation Tip

During Pair Programming: Fibonacci Showdown, circulate and ask pairs to explain their cache structure before coding, ensuring they understand how keys map to subproblems.

What to look for

Present students with a pseudocode snippet for a recursive solution to a problem (e.g., Fibonacci). Ask them to identify two instances where the same subproblem is calculated. Then, ask them to describe how memoization would prevent this redundant calculation.

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Activity 02

• Flipped Classroom
• 50 min · Small Groups

Small Group Stations: Knapsack Builds

Groups rotate through stations: define items/weights/values, code greedy vs. DP, trace tables, test edge cases. Each station yields a shared solution report.

Explain how dynamic programming avoids redundant calculations.

Facilitation Tip

In Small Group Stations: Knapsack Builds, provide blank grids for tabulation and have groups swap stations to compare solutions before finalizing their own.

What to look for

Pose the question: 'When would you choose tabulation over memoization for a dynamic programming problem, and why?' Facilitate a class discussion where students articulate the trade-offs in terms of implementation, memory usage, and potential for stack overflow.

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Activity 03

• Flipped Classroom
• 30 min · Whole Class

Whole Class Trace: Longest Common Subsequence

Project a table; class calls out values row-by-row while coding live. Vote on decisions, then run code to verify. Extend to student-voted problem variants.

Construct a dynamic programming solution for a classic problem like the Fibonacci sequence or knapsack problem.

Facilitation Tip

For Whole Class Trace: Longest Common Subsequence, use a document camera to let students physically mark the table as you solve, emphasizing how each cell depends on previous ones.

What to look for

Provide students with a small, defined problem (e.g., finding the minimum number of coins to make change for a specific amount). Ask them to outline the steps to solve it using tabulation, including defining the DP table and the recurrence relation.

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Activity 04

• Flipped Classroom
• 35 min · Individual

Individual Optimization: Coin Change Problem

Students adapt DP template to minimize coins for given amounts. Submit code with test cases and complexity analysis for peer review.

Differentiate between dynamic programming and recursion with memoization.

Facilitation Tip

For Individual Optimization: Coin Change Problem, require students to submit a runtime comparison table between their recursive and tabulated solutions before moving to extension problems.

What to look for

Present students with a pseudocode snippet for a recursive solution to a problem (e.g., Fibonacci). Ask them to identify two instances where the same subproblem is calculated. Then, ask them to describe how memoization would prevent this redundant calculation.

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

A few notes on teaching this unit

Teachers should emphasize the 'why' behind each step, not just the 'how.' Start with concrete examples before introducing formal definitions, and always connect back to the problem's structure. Avoid rushing to the algorithm; let students grapple with inefficiency first. Research shows that when students build their own examples of overlapping subproblems, they internalize optimal substructure more deeply.

Successful learning shows when students can explain why tabulation or memoization is chosen for a given problem, trace a solution step-by-step, and articulate the trade-offs between space and time. They should also recognize when dynamic programming is not the right tool, even for recursive problems.

---

Watch Out for These Misconceptions

• During Pair Programming: Fibonacci Showdown, watch for students who assume memoization and tabulation produce identical stack traces.

  Have students print both the memoized recursive calls and the bottom-up iteration steps side by side, then ask them to identify where recursion stacks grow versus where arrays update in-place.

• During Small Group Stations: Knapsack Builds, watch for students who apply dynamic programming to any subset problem without checking for overlapping subproblems.

  Provide a non-overlapping problem variant at one station and have groups attempt to fill the table, then discuss why it fails to produce a valid solution.

• During Individual Optimization: Coin Change Problem, watch for students who believe tabulated solutions always outperform recursive ones regardless of input size.

  Guide students to time both approaches for inputs of 10, 100, and 1000 coins, then ask them to explain why small inputs may favor recursion due to table overhead.

---

Methods used in this brief

• Flipped Classroom