Computer Science · 12th Grade

Active learning ideas

Optimization with Memoization and Caching

Active learning builds intuition for optimization by letting students see inefficiency in real time. For memoization and caching, tracing recursive calls or simulating a cache makes the invisible problem of redundant computation visible. This hands-on work helps students connect abstract concepts to concrete performance gains.

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

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

Activity 01

• Gallery Walk
• 40 min · Pairs

Gallery Walk: Tracing the Call Tree

Post 6-8 stations around the room, each showing a Fibonacci or similar recursive function with a different input value. Students walk to each station and manually draw the recursive call tree, marking duplicate calls with a red marker. They then sketch a memoized version and count how many calls are saved at each station.

Explain how remembering past results can speed up a program.

Facilitation Tip

During the Gallery Walk, circulate with a timer to keep groups moving every 3–4 minutes so they focus on tracing rather than lingering on one tree.

What to look for

Present students with a simple recursive function (e.g., a variation of Fibonacci or factorial). Ask them to identify specific inputs that would cause redundant calculations. Then, have them explain in one sentence how memoization would prevent this redundancy for one of those inputs.

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

Activity 02

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: When Does Memoization Help?

Present students with 5 algorithm scenarios (string search, Fibonacci, matrix multiplication, sorting a random list, pathfinding in a grid). Students individually categorize each as 'benefits from memoization' or 'does not,' then pair up to compare their reasoning. Pairs share their most contested categorization with the class, driving discussion about overlapping subproblems.

Identify problems where repeated calculations make an algorithm inefficient.

Facilitation Tip

In Think-Pair-Share, provide a timer for the pair phase to ensure all students contribute their reasoning before the class discussion.

What to look for

Pose the question: 'When might caching actually slow down a program or system?' Guide the discussion towards scenarios like cache invalidation issues, the overhead of managing the cache, or when data changes too frequently to benefit from caching. Ask students to provide a hypothetical example.

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

Activity 03

• Problem-Based Learning
• 50 min · Pairs

Collaborative Lab: Memoize It

Student pairs receive a working but slow recursive function, such as computing Fibonacci(35) or listing all subsets of a set. They first time the unoptimized version, then collaboratively add a dictionary-based memoization layer and compare runtimes. Each pair presents their performance improvement to the class with a before-and-after timing comparison.

Design a simple function that uses memoization to improve its performance.

Facilitation Tip

In the Collaborative Lab, assign roles: one student codes, one tracks time, one records observations so everyone participates actively.

What to look for

Provide students with a small code snippet demonstrating a function without memoization. Ask them to write pseudocode or a brief Python function that adds memoization to this function. They should also state one benefit of their memoized version.

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

Activity 04

• Simulation Game
• 20 min · Whole Class

Simulation Game: Human Cache

One student acts as the 'computer,' another as the 'cache.' The teacher calls out function requests (e.g., 'fib(5), fib(3), fib(5) again'). The cache student must decide whether to look up the stored answer or pass it to the computer to compute fresh. This kinesthetic activity makes clear how a cache lookup differs from a full computation.

Explain how remembering past results can speed up a program.

Facilitation Tip

During the Human Cache simulation, have students rotate roles every round so each learner experiences both the cache manager and the computation roles.

What to look for

Present students with a simple recursive function (e.g., a variation of Fibonacci or factorial). Ask them to identify specific inputs that would cause redundant calculations. Then, have them explain in one sentence how memoization would prevent this redundancy for one of those inputs.

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

A few notes on teaching this unit

Start with a concrete example students already know, like the naive recursive Fibonacci, then immediately show the call tree to highlight repeated work. Use color-coding or underlining to mark overlapping calls. Avoid rushing to the code: let students articulate the inefficiency in their own words first. Research shows that students grasp dynamic programming better when they trace before they code, because the pattern of overlapping subproblems becomes memorable.

Students will recognize overlapping subproblems, modify recursive functions to use memoization, and explain when and why caching improves efficiency. They will also identify scenarios where caching adds overhead instead of benefit.

---

Watch Out for These Misconceptions

• During the Collaborative Lab: Memoize It, watch for students assuming memoization always speeds up every function they write.

  During the Collaborative Lab: Memoize It, have students test their memoized function with two sets of inputs: a sequence of Fibonacci numbers (structured, overlapping) and a set of random large numbers (minimal overlap). Ask them to measure and compare execution times to see when the cache helps or hurts.

• During the Think-Pair-Share: When Does Memoization Help?, watch for students conflating memoization with dynamic programming.

  During the Think-Pair-Share: When Does Memoization Help?, provide side-by-side pseudocode for a memoized recursive Fibonacci and a bottom-up dynamic programming table. Ask pairs to compare structure, recursion vs. iteration, and how solutions are built. Use a Venn diagram template to organize similarities and differences.

• During the Simulation: Human Cache, watch for students thinking caching only applies to recursive functions.

  During the Simulation: Human Cache, introduce a real-world scenario like a browser cache or CPU cache. Have students role-play a browser storing images and scripts on first visit and serving them from disk on return. Ask them to map their human cache actions to how a browser implements caching at scale.

---

Methods used in this brief

• Gallery Walk
• Think-Pair-Share
• Problem-Based Learning
• Simulation Game