C33 · Topic 3.9 · 40 minutes · AAP-2.L, AAP-2.M
Comparing algorithm behaviour
By the end you can:
- Compare contracts before comparing outputs.
- Construct a distinguishing counterexample.
- Justify a full-traversal counting equivalence.
Before this lesson: topics 3.6, 3.8.
- Equivalent algorithms
- Algorithms with the same required result or effect for every allowed input under the stated contract.
- Counterexample
- A permitted input that disproves a general claim.
Understand
Algorithms can use different steps yet satisfy the same specification. Compare their allowed inputs and output meanings before treating equal numbers as evidence of equivalence. A count of matches and a position of the first match are different results even when they happen to be numerically equal on one list.
One counterexample disproves a claim of equivalence, but several agreeing tests do not prove it for every permitted input. A general argument can explain why two implementations always agree, for example by showing that they partition the same list into qualifying and nonqualifying entries.
Worked example
Algorithm A counts qualifying entries. B starts at length and subtracts nonqualifying entries. C returns the first qualifying position or 0.
- For[2,7,3,7,0],minimum 5,all three produce 2.
- For[0,0,8],minimum 5,A and B produce 1 but C produces 3.
- A and B agree generally because every element is either qualifying or not;C answers a different question.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Minimum and maximum
- Sum and average
- Divisibility and composition
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Values, comma separated (0–100; max 8)2,7,3,7Waiting
- AlgorithmsumWaiting
Ready to explore: Build algorithms from running summaries
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 12,7,3,7,0Waiting
- Input 25Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Try repeated boundary values, no matches and an empty list.
Check a misconception
Claim: Agreement on a convenient input proves algorithms equivalent.
A distinguishing input can expose a difference; proving equivalence needs reasoning across the whole stated domain.
Guided practice
Give a counterexample separating count from first position and state both results.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
Explain why starting at length and subtracting entries below threshold gives the count at or above it.
Exit check
Why must equivalence include the empty-list case if allowed?
Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.
Check yourself
Your practice so far
Check an answer to see its rationale.