Search Speed Teacher Guide Search Speed
Teacher Facilitation Guide
Subject: Computer Science
Grade: 12th Grade
Duration: 60-75 Minutes
Lesson Summary
In this lesson, students transition from "writing code that works" to "analyzing code for efficiency." They will explore Linear Search and Binary Search through a hands-on physical simulation, discovering how dataset organization impacts search speed and deriving the concept of logarithmic growth.
Learning Objectives
Contrast the mechanics and efficiency of Linear vs. Binary search.
Identify the requirement of sorted data for binary search execution.
Predict the growth rate of steps as input size (N) increases.
Materials Needed
20 Sealed envelopes containing random numbers (1-100)
1 set of 20 sorted index cards
Classroom projector / Slides
Student Search Step Tracker (Worksheet)
Instructional Sequence
0-10m
The Hook: High-Stakes Guessing Game
Ask for two volunteers. Volunteer A must find a specific number in an unsorted pile of 20 envelopes. Volunteer B must find a number in a sorted pile. Limit both to only checking one at a time. Record how many "probes" (checks) each takes.
10-25m
Direct Instruction: Linear vs. Binary Logic
Use slides to visualize the decision tree of a binary search. Emphasize that each step eliminates 50% of the remaining search space. Contrast this with linear search where each step eliminates only 1 item.
25-50m
The Search Lab (Guided Practice)
Students work in pairs using the Search Step Tracker. They simulate searches for datasets of size N=8, N=16, and N=32. They must record the maximum possible steps (worst-case scenario) for both algorithms.
50-60m
Debrief: The "Why" of Scalability
Ask: "If the dataset had 1 million items, how many steps for Linear? (1 million). How many for Binary? (~20)." Introduce the term "Logarithmic Growth."
Pedagogical Strategies
Common Misconceptions
Sorted requirement: Students often forget that Binary Search requires the data to be sorted first. Remind them that sorting itself has a cost.Worst Case: Students may focus on finding the item quickly by luck. Force them to calculate the maximum number of steps needed.
Differentiation
Enrichment: Have students research "Interpolation Search" for datasets that are uniformly distributed.Support: Provide a physical number line for students to physically mark off sections as they "divide" the search space.
Discussion Prompts
PROMPT 1
"Is Binary Search always better? When might Linear Search be the right choice?"
PROMPT 2
"If you have to search 100 items only once, is it worth sorting them first?"
PROMPT 3
"What real-world systems use binary search? Think about dictionaries or phone books."
Search Speed Slides Presentation Lesson 01: Algorithmic Foundations
Search Speed
Why some code runs in milliseconds while others takes hours.
The Challenge
01. Setup
I have a secret number between 1 and 100 hidden in one of these 20 envelopes.
Rules of Engagement
• You can only open ONE envelope at a time.
• If it's not the right number, put it back.
• Goal: Find the target in the fewest steps.
Strategy A
Linear Search
The "Brute Force" approach. Check every single item, one by one, from the start.
Worst Case Scenario
Steps = N
If you have 1,000,000 items, you might have to check 1,000,000 times.
for i from 0 to array.length: if array[i] == target: return i return -1
Strategy B
Binary Search
The Requirement
Data MUST be sorted.
The "Divide and Conquer" approach. Check the middle. Throw away half. Repeat.
1
Check middle index.
2
Is target higher or lower?
3
Discard the wrong half.
Comparing Growth
Input Size (N)
1,024
Linear Search
1,024 Steps
Binary Search
10 Steps
Input Size (N)
1,048,576
Linear Search
1M+ Steps
Binary Search
20 Steps
Scalability
Linear is O(N)
Search Speed Tracker Worksheet Search Step Tracker
Module 01: Algorithmic Efficiency
Name:
Date:
Lab 1.1: Physical Search Simulation
Simulate searching for a target number in datasets of varying sizes. Record the maximum possible steps required (Worst Case) for both Linear and Binary search strategies.
Dataset Size (N) Linear Search (Steps) Binary Search (Steps) N = 8 N = 16 N = 32 N = 1,024
Analysis & Prediction
1. Look at your results for Binary Search. Every time you double the input size (N), how many steps are added to the search?
2. Suppose you have an unsorted list of 1 million names. Why can't you use Binary Search immediately? What would you have to do first?
3. Prediction: If a dataset has 2,000,000 items, estimate the number of steps for Binary Search. Explain your logic.
The Efficiency Equation
Mathematical shorthand: In CS, we use "Logarithms" to describe the speed of Binary Search.
Steps ≈ \(\log_2(N)\)
Quadratic Sorting Teacher Guide Quadratic Sorting
Teacher Facilitation Guide
Subject: Computer Science
Topic: O(N^2) Algorithms
Duration: 60 Minutes
Lesson Summary
Students explore "Brute Force" sorting algorithms: Bubble Sort and Selection Sort. By manually tracing these algorithms, students will understand how nested loops lead to quadratic growth, and why these methods become unusable for large datasets.
Learning Objectives
Manually execute Bubble and Selection Sort on small datasets.
Calculate the total number of comparisons and swaps for a dataset of size N.
Identify the relationship between nested loops and O(N^2) complexity.
Materials Needed
8 Numbered cards per student pair
Bubble vs. Selection Tracing Worksheet
Large floor space for the "Human Line-Up"
Instructional Sequence
0-15m
The Hook: Human Bubble Sort
Call 8 students to the front. They must sort themselves by height using ONLY neighbor-swapping (Bubble Sort). Every time a swap happens, the whole class yells "SWAP!" By the end, discuss how exhausting and repetitive it felt.
15-30m
Visualizing the Code (Slides)
Show the nested loop structure. Explain that the outer loop represents 'passes' and the inner loop represents 'comparisons'. Point out that for every item (N), we check every other item (N).
30-50m
Sort Race (Guided Practice)
Students work in pairs with cards. One student performs Bubble Sort, the other records every comparison. Then they switch and do Selection Sort. They must count total comparisons for N=4 and N=8.
50-60m
The Square Rule
Debrief: "If N=8 took ~28 comparisons, how many would N=16 take? (~120)." Introduce the concept of Quadratic growth: \(N \times N = N^2\).
Quadratic Sorting Slides Presentation Lesson 02: Brute Force Sorting
Quadratic Sorting
Bubble, Selection, and the cost of nested loops.
Bubble Sort
The Algorithm
The simplest sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order.
1 Compare neighbors (A, B)
2 Swap if A > B
3 Repeat until largest "bubbles" to the top.
5
1
4
2
8
Comparing [1] and [4]...
The Efficiency Trap
for pass in range(N): for comparison in range(N-1): if array[j] > array[j+1]: swap(...)
For every item in the outer loop, we scan almost every other item in the inner loop.
Quadratic Growth
If N=10, we do ~100 comparisons.
O(N2)
Selection Sort
Search for the minimum, swap it to the front.
Pass 1
Find the absolute smallest number in the entire array. Swap it to index 0.
Pass 2
Find the smallest number in the remaining array. Swap it to index 1.
Complexity
Still O(N2)
Even though it performs fewer swaps, it still performs the same number of comparisons as Bubble Sort.
When O(N2) Fails
Sorting the population of Los Angeles (~4 million people) with Bubble Sort?
Total Operations:
16,000,000,000,000
That's 16 TRILLION comparisons.
CODE KILLED BY SCALABILITY
Quadratic Sorting Trace Worksheet Brute Force Tracing
Exp: O(N^2) Complexity
Subject:
Algorithms - Sorting Pass
N-Count:
Activity A: Bubble Sort Trace
Sort the following array using Bubble Sort. Track the array state after each complete Pass (when the largest remaining item reaches its final spot).
7
2
5
1
Initial: [ 7, 2, 5, 1 ]
Pass 1:
Pass 2:
Pass 3:
Analysis Check:
How many total COMPARISONS were made to sort this N=4 array? ________
Activity B: Selection Sort Trace
Find the minimum value, swap it with the first unsorted element.
9
3
8
4
Initial: [ 9, 3, 8, 4 ]
Swap 1:
Swap 2:
The Efficiency Synthesis
Look at both algorithms above. Even though Selection Sort makes fewer swaps, both have a "for loop inside a for loop." Explain in your own words why doubling the input size N makes the runtime go up by 4 times (N x N).
Divide and Conquer Teacher Guide Divide and Conquer
Teacher Facilitation Guide
Subject: Computer Science
Topic: Recursion & Efficiency
Duration: 75 Minutes
Lesson Summary
Students explore recursive sorting algorithms: Merge Sort and Quick Sort. By contrasting the "Divide and Conquer" strategy with the "Brute Force" methods from the previous lesson, students learn how breaking problems into smaller sub-problems can dramatically improve efficiency to O(N log N).
Learning Objectives
Define recursion and identify base cases in sorting.
Trace the "split" and "merge" phases of Merge Sort.
Contrast O(N^2) sorting with O(N log N) sorting.
Materials Needed
Decks of cards (1 per 4 students)
Merge Sort Visualization Worksheet
Stopwatch or Timer
Instructional Sequence
0-15m
The Hook: Card Sorting Race
Divide the class into two teams. Team A must sort a deck by finding the minimum (Selection Sort style) by themselves. Team B must split the deck among 4 people, each sorting their pile, then merging them back together. Team B almost always wins, demonstrating parallel processing and recursion logic.
15-35m
Direct Instruction: Merge Sort Tree
Use slides to draw a recursive tree. Emphasize the "Divide" phase (splitting until size = 1) and the "Conquer" phase (zipping sorted sub-lists back together). Explain that merging two sorted lists is very fast (\(O(N)\)).
35-60m
Tree Mapping (Guided Practice)
Students complete the worksheet, drawing the full recursive tree for an 8-item array. They must label each level and identify the base case.
60-75m
Quick Sort Pivot Talk
Briefly introduce Quick Sort. Show how choosing a "pivot" element creates sub-problems. Mention that while Merge Sort uses extra space (memory), Quick Sort is usually faster in practice.
Divide and Conquer Slides Presentation Lesson 03: Recursive Strategies
Divide and Conquer
Breaking big problems into tiny, manageable ones.
Recursion
Fundamental Logic
A function that calls itself to solve a smaller version of the same problem.
Two Mandatory Parts:
1. Base Case
The "stop" condition. (e.g., list size is 1)
2. Recursive Step
Splitting the problem into smaller pieces.
sort([5, 2, 8, 1])
sort([5, 2])
sort([8, 1])
[5]
[2]
[8]
[1]
Merge Sort: Divide
[ 38, 27, 43, 3, 9, 82, 10 ]
[ 38, 27, 43 ]
[ 3, 9, 82, 10 ]
[ 38 ]
[ 27, 43 ]
[ 3, 9 ]
[ 82, 10 ]
We split until every sub-array contains only ONE item. A list of size 1 is, by definition, sorted.
Merge Sort: Conquer
Merging Sorted Lists
Merging two lists that are ALREADY sorted is very fast. You just compare the heads of both lists and pick the smallest.
Merging [27, 38] and [3, 43]:
1. Compare 27 and 3 → Pick 3
2. Compare 27 and 43 → Pick 27
3. Compare 38 and 43 → Pick 38
4. Final → [3, 27, 38, 43]
Efficiency Boost
O(N log N)
N2 vs N log N
N = 10,000
Bubble Sort (N2)
100,000,000 ops
Merge Sort (N log N)
130,000 ops
The Result:
Merge Sort is
...and the gap only gets bigger as N grows.
Recursive Tree Worksheet Recursive Tree Mapping
Algorithm: Merge Sort
Name:
Date:
Phase 1: The Divide
Map out the recursive splitting of the following 8-item array. Continue splitting until you reach the Base Case (size = 1).
[ 8, 3, 5, 1, 7, 2, 6, 4 ]
Phase 2: The Conquer (Merge)
Explain the "Merge" logic. When you have two sorted lists, [1, 3, 5, 8] and [2, 4, 6, 7] , how does the algorithm combine them back into one sorted list?
Reflect:
Why is it more efficient to sort four lists of size 2 than one list of size 8?
Complexity Check:
The number of levels in the tree above is 3 (for N=8). 23 = 8. In math, we call this the:
LOGARITHM (log N)
Big O Mastery Teacher Guide Big O Mastery
Teacher Facilitation Guide
Subject: Computer Science
Unit: Computational Thinking
Duration: 60-75 Minutes
Lesson Summary
This lesson transitions students from intuitive efficiency understanding to formal mathematical Big O notation. Students will learn to classify code based on time complexity, graph growth rates, and understand how complexity impacts real-world hardware.
Learning Objectives
Classify code snippets into complexity classes: O(1), O(N), O(log N), O(N^2), O(2^N).
Graph the growth rates of standard Big O functions.
Calculate estimated runtimes for massive datasets using Big O.
Teacher Key Concepts
Worst Case: Big O always assumes the slowest possible performance.Dominant Terms: \(N^2 + N\) is just \(O(N^2)\). Ignore lower orders.Constants: \(O(2N)\) is just \(O(N)\). Scale matters, not small multipliers.
Instructional Sequence
0-15m
The Hook: The Billion Data Point Challenge
Ask: "If a computer can do 1 billion operations per second, how long does it take to sort 1 billion people using Bubble Sort vs. Merge Sort?" (Bubble = ~30 years, Merge = ~30 seconds). The difference is life and death for a program.
15-35m
The Hierarchy of Growth (Slides)
Present the "Big O Hierarchy." Use a chart to show how runtimes explode for different classes. Introduce formal terminology (Linear, Quadratic, Exponential, Logarithmic).
35-55m
Big O Battles (Skill-Building)
Students analyze code snippets on their worksheet. They must identify loops, nested loops, and recursive splits to determine the Big O class of each snippet.
55-60m
Exit Ticket: The Rule of Scale
Ask: "Which grows faster: \(N^2\) or \(N \log N\)? At what dataset size does the difference become obvious?"
Big O Mastery Slides Presentation Lesson 04: Formal Complexity
Big O Mastery
The universal language of algorithmic efficiency.
What is Big O?
The Definition
Big O notation describes the upper bound of an algorithm's growth rate.
It answers:
"As the input size (N) grows towards infinity, how much more work does the computer do?"
The Notation
O( f(N) )
The Hierarchy
O(1)
Constant
Instant. Always the same time regardless of size.
O(log N)
Logarithmic
Excellent. Rises slightly as N grows. (Binary Search)
O(N)
Linear
Fair. Direct 1:1 relationship. (Linear Search)
O(N log N)
Quasilinear
Efficient for sorting. (Merge Sort)
O(N2)
Quadratic
Poor. Explodes quickly. (Bubble Sort)
How to Analyze Code
Rule 1: Drop Constants
O(2N) becomes O(N). In the long run, small multipliers don't matter.
Rule 2: Drop Dominant Terms
O(N2 + N) becomes O(N2). The largest factor "wins" at scale.
Example Snippet
for i in range(N):
O(2N) → O(N)
Visualizing Growth
Time
Input Size (N)
O(1)
O(log N)
O(N)
O(N2)
Big O Analysis Lab Worksheet Big O Lab Analysis
Algorithm Classification & Growth
Student:
Date:
Task 1: Classify the Snippets
Determine the Big O complexity of each code block. Show your reasoning by circling loops or recursive calls.
for i in range(len(arr)):
Big O:
for i in range(len(arr)):
Big O:
while N > 1:
Big O:
def func(N):
Big O:
Task 2: Scalability Estimation
A hypothetical processor can execute 1 billion operations per second . Calculate the time it would take to process a dataset of N = 100,000,000 (100 million) items for the following complexities:
O(N)
Calculation:
= ___________ seconds
O(N2)
Calculation:
= ___________ years
3. Based on these numbers, why is it vital for software companies like Google or Meta to avoid O(N^2) algorithms in their search and feed logic?
Optimization Workshop Teacher Guide Optimization Workshop
Teacher Facilitation Guide
Subject: Computer Science
Capstone: Efficiency & Trade-offs
Duration: 90 Minutes
Workshop Goal
Students act as senior engineers tasked with optimizing a critical system bottleneck. They must analyze three different algorithmic approaches to the same problem, identify their Big O complexities, and choose the best one based on hardware constraints (CPU vs. RAM).
Technical Objectives
Evaluate time vs. space complexity (memory vs. speed).
Write a formal technical justification for an algorithmic choice.
Refactor O(N^2) code to O(N log N) or O(N).
Case Study Brief
Scenario: Social media "Friend Recommendation" algorithm.
Input: 5 million users.
Constraint: Limited Server Memory (16GB RAM) or Limited CPU Time (Must run in < 2s).
Instructional Sequence
0-15m
The Hook: Server Crash Simulation
Present the "emergency": The friend recommendation system has crashed because the dataset grew too large for its O(N^2) logic. Students have 75 minutes to propose a fix before the "CEO" (Teacher) demands an answer.
15-45m
Part A: The Audit (Investigation)
Pairs analyze the "Legacy Code" snippets. They must fill out a technical audit table, calculating the operations needed for 5M users for each version of the code.
45-75m
Part B: The Proposal (Writing)
Students select one algorithm. They must write a one-paragraph justification explaining why they chose it, specifically addressing why they are okay with its trade-offs (e.g., "We chose O(N log N) because while it uses more memory, our servers have plenty of RAM but slow CPUs").
75-90m
Debrief: The Real World
Ask: "When would we ever choose the 'slower' algorithm?" (Answer: when memory is extremely tight, like on a microwave or a Mars rover). Discuss the balance of resources.
Optimization Workshop Slides Presentation Lesson 05: Culminating Workshop
Optimization Workshop
Engineering the balance between time and space.
Emergency Alert
SYSTEM DOWN
The Crash Report
Our user base just hit 5,000,000.
The "Friend Link" algorithm is currently running at O(N2). At our current scale, one calculation takes 43 hours.
Your Mission:
Find a more efficient algorithm and justify the trade-offs.
FATAL ERROR: TimeoutException Thread: "LinkEngine-Main" Execution Time: > 155,000s Status: KILLED
The Engineer's Dilemma
Time Complexity
How many operations are required? Faster code reduces CPU usage and costs.
Space Complexity
How much memory (RAM) is required? Recursive algorithms often need extra space to store sub-problems.
"There is no such thing as a free lunch in CS."
Trade-off
The Three Options
Option 1: Linear Scan
O(N)
Lightning Fast
High RAM usage
Option 2: Divide & Merge
O(N log N)
Solid Balance
Complex Logic
Option 3: Bubble Sync
O(N2)
Tiny RAM Footprint
Heat-Death Speed
Deliverables
What is expected in your report:
Complexity analysis of current "Legacy" code.
Operation count for N=5,000,000.
The "Trade-off Justification" paragraph.
Final Review
Your proposal must be submitted before the servers overheat.
System Architect Report Worksheet System Architect Report
Priority: High | System Optimization
Lead Engineer:
System ID:
Part A: The Bottleneck Audit
Analyze the current "Legacy" system. Calculate the total operations for N=5,000,000 users.
# LEGACY CODE: Friend Recommendation
Complexity Class:
O( ________________ )
Total Ops (N=5M):
25,000,000,000,000
Part B: The Proposed Fix
Choose one of the following optimization paths and justify your choice based on the constraints: Unlimited Server RAM, but CPUs are heavily throttled.
Option 1
O(N log N)
Option 2
O(N)
Option 3
Keep Legacy
1. Why is your chosen algorithm better for the current crisis?
2. What is the "Memory Trade-off" you are making? (e.g. Does it use more RAM?)
Architect's Final Seal
By signing below, you certify that this optimization will prevent further system timeouts and maintain scalability for future growth.
Signature:
