Lesson planSorting Robot Algorithm Race: Counting Comparisons
STEAM40 minutesGrades: 8th
Overview
Count a sorting robot's comparisons and graph the growth.
Description
Your teen acts as a sorting robot that can compare only two playing cards at a time. They count the comparisons needed to sort 2 to 8 cards using selection sort, graph the results, and discover that the work grows in a nonlinear way, unlike a simple 'find the biggest card' scan.
Objective
Your teen will run a sorting algorithm by hand, record comparisons for different input sizes, graph the data, and explain why one relationship is linear and the other is not.
Standards
8.F.3Math · Grade 8 · Functions Interpret the equation y = mx + b as defining a linear function, whose graph is a straight line; give examples of functions that are not linear.
8.F.5Math · Grade 8 · Functions Describe qualitatively the functional relationship between two quantities by analyzing a graph (e.g., where the function is increasing or decreasing, linear or nonlinear). Sketch a graph that exhibits the qualitative features of a function that has been described verbally.
Materials
| Item | Quantity |
|---|
| Deck of playing cards (or numbered paper slips) | 1 |
| Graph paper | 2 sheets |
| Pencil and tally sheet | 1 each |
| Two sticky notes labeled 'smallest so far' and 'sorted' | 2 |
Vocabulary
Algorithm
A step-by-step procedure for solving a problem.
Selection sort
A sorting algorithm that repeatedly finds the smallest remaining item and moves it to the sorted side.
Comparison
One check of which of two items is larger.
Nonlinear function
A relationship whose graph is not a straight line because it does not change at a constant rate.
Preparation
- Pull out cards ace through 8 of one suit (ace = 1).
- Make a table with columns: n (number of cards), comparisons to find the max, comparisons to selection sort.
Introduction
Lay 8 cards face down. Say: 'A robot in a warehouse sorts packages, but it can only compare two at a time. How many comparisons will it need to put these in order?' Have your teen guess.
If 4 cards take a certain number of comparisons, will 8 cards take twice as many?
Why would a company care how many steps its robot takes?
Steps
1Step 1
Find the biggest
(6 min) Your teen flips 4 cards face up in a row and finds the largest by comparing two at a time, keeping the winner and tallying each comparison. Repeat for 2, 3, 6 and 8 cards and record the counts.
2Step 2
Run selection sort
(14 min) Your teen sorts 3, 4, 5, 6 and 8 cards with selection sort: compare to find the smallest card in the unsorted part, move it to the sorted side, and repeat. A partner tallies every comparison so the counts are exact.
3Step 3
Graph both
(8 min) Your teen plots both data sets on one graph with n on the x-axis and comparisons on the y-axis. They connect each set of points.
4Step 4
Analyze
(8 min) Your teen writes the equation for the find-the-biggest line (y = n - 1) and explains why it is linear. Then they describe the sorting graph in words, test the rule comparisons = n(n - 1) ÷ 2 against the data, and predict comparisons for 20 cards.
Conclusion
Ask: if a warehouse had 1,000 packages, why would programmers look for a faster sorting algorithm? Computer scientists study exactly this kind of growth to make software and robots efficient.
Make your own lesson plan in minutes
Describe a topic and Resource Portal AI writes the objectives, materials and steps for your group.
Try Resource Portal AI