105i - Testing and Describing Algorithms

Lesson 105 — Testing Algorithms and Describing How They Work

Strand: Space | Descriptor: AC9M7SP04 | Duration: 45 minutes

Learning Intentions

• To test an algorithm systematically and find its failures.
• To describe in words how an algorithm works and why.

Success Criteria

I can:

1. Choose test cases that probe an algorithm properly, including edge cases.
2. Find and fix a fault in an algorithm.
3. Explain in words what an algorithm does and how each decision contributes.
4. Judge whether an algorithm is exhaustive, unambiguous and efficient.

Warmup

(6 minutes — find the fault, pairs)

The broken sorter.

1. Does the shape have sides?
   • Yes → quadrilateral. Stop.
   • No → go to step 2.
2. Does the shape have sides?
   • Yes → triangle. Stop.
   • No → quadrilateral. Stop.

1. Trace a pentagon through it. What happens?
2. Name the fault.
3. Fix it with the smallest possible change.

Answers: 1. It reaches step 2, answers “no”, and is called a quadrilateral; 2. The final branch has the wrong label — the algorithm is unambiguous but not correct; 3. Change the last output to “other polygon”.

The lesson’s habit: you cannot trust an algorithm you have not tested — and the test that matters most is the one you did not expect to fail.

Activities

Activity 1 — Explicit Instruction: how to Test (14 min)

A test case is an input plus the classification you expect. Testing means running the algorithm and comparing what happens with what should happen.

The four kinds of test case — teach all four:

Kind	What it probes	Shape example
Typical	Everyday correctness	A rectangle
Edge	Boundaries between categories	A square (rectangle and rhombus)
Extreme	The limits of the design	A -sided polygon; a concave shape
Invalid	Inputs the algorithm was never meant for	A circle; an open curve

Most faults hide in the edge cases. Typical cases pass easily; the square, the equilateral triangle and the concave polygon are where trees break.

I do — test a flawed triangle sorter:

1. Are exactly two sides equal?
   • Yes → isosceles. Stop.
   • No → go to step 2.
2. Are all three angles less than ?
   • Yes → acute scalene. No → right or obtuse scalene. Stop.

Test table, built live:

Test case	Kind	Expected	Actual	Pass?
	typical	isosceles	isosceles	✓
	typical	right scalene	right or obtuse scalene	✓
	edge	isosceles/equilateral	acute scalene	✗
obtuse	edge	isosceles	isosceles	✓

Diagnose the failure: an equilateral triangle has three equal sides, so “exactly two” answers no, and it falls into the scalene branch. Fix: test “all three equal?” first, or change step 1 to “at least two equal?“.

Emphasise: the algorithm was not obviously wrong. Only a deliberately chosen edge case exposed it.

We do — choose test cases. For a quadrilateral sorter, which four shapes would you test first, and why?

(Expect: a square — edge case sitting in several categories; a rhombus and a rectangle — near neighbours of the square; a kite or a concave “dart” — the usual gap in a tree.)

Activity 2 — Test, Fix, Describe (16 min)

Pairs. Three algorithms to test; each contains a fault.

Algorithm P — polygon sorter.

1. Are all sides equal?
   • Yes → regular. Stop.
   • No → irregular. Stop.

Algorithm Q — angle classifier for triangles.

1. Is there an angle greater than ?
   • Yes → obtuse. Stop.
   • No → acute. Stop.

Algorithm R — quadrilateral sorter.

1. Two pairs of parallel sides?
   • Yes → go to step 2. No → trapezium. Stop.
2. All angles right angles?
   • Yes → rectangle. No → parallelogram. Stop.

For each:

1. Write two test cases you expect to pass and one you suspect will fail.
2. Run all three; record expected versus actual.
3. Name the fault precisely.
4. Fix it with the smallest change you can.
5. Re-test your failing case.

Socratic scaffolding:

Prompt	Purpose
For P: try a rhombus.	All sides equal but angles are not — it is called regular, wrongly.
So what does P actually test?	Only equal sides; regularity needs equal angles too (Lesson 43).
For Q: try a right-angled triangle.	Exactly is not greater than , so it is called acute — wrong.
For R: try a kite.	It has no parallel pairs, so it is called a trapezium — wrong.
Smallest fixes?	P: add “and all angles equal?“. Q: add a right-angle test. R: add a parallel-pair count test before labelling trapezium.

Then, for one fixed algorithm, write a description (three to four sentences) answering:

• What does this algorithm do?
• What does each decision contribute?
• What does it not handle?

Model description (teacher, for the fixed Algorithm Q):

“This algorithm classifies a triangle by its largest angle. The first decision separates obtuse triangles by testing for an angle over . The second checks for exactly , catching right-angled triangles that the first test misses. Anything left has all angles under and is acute. It classifies by angles only — it says nothing about side lengths, so an isosceles right triangle and a scalene right triangle both come out simply as ‘right’.”

Activity 3 — Inquiry: how Good is Your Algorithm? (7 min)

Pairs, evaluating their Lesson 104 sorter.

Judge your own sorting algorithm against four criteria. Score each out of and justify.

Criterion	Question
Correct	Does every test case reach the right category?
Exhaustive	Does every possible shape reach some category?
Unambiguous	Could any shape reach two categories?
Efficient	What is the greatest number of questions any shape needs?

Then: identify your algorithm’s weakest criterion and write one specific improvement.

Discussion targets: most trees score well on correct and unambiguous, and poorly on exhaustive (a shape type was never anticipated) or efficient (questions in a poor order). Efficiency improves by asking the most-splitting question first — the halving principle from Lessons 103 and 104.

Checks for Understanding

(5 minutes — exit ticket, collected)

1. Name the four kinds of test case, with one shape example each.
2. Why are edge cases more likely to reveal faults than typical cases?
3. A sorter calls a rhombus “regular”. What is the fault and the fix?
4. Write two sentences describing what this algorithm does: “1. Are all sides equal? Yes → go to 2, No → stop with ‘irregular’. 2. Are all angles equal? Yes → ‘regular’, No → ‘equilateral but not regular’.”
5. Reasoning. An algorithm passes every test you tried. Does that prove it is correct?

Answers: 1. Typical (a rectangle), edge (a square), extreme (a -gon or concave shape), invalid (a circle); 2. They sit on the boundary between categories, where a poorly ordered or incomplete test is most likely to misfire; 3. It tests only equal sides; regularity also needs equal angles — add an angle test; 4. E.g. “It checks first whether all sides are equal, and only then whether all angles are equal, so a shape must pass both to be called regular. A rhombus passes the first test but fails the second.”; 5. No — testing can only reveal faults, never prove their absence. An untried case may still fail. (The same logic as Lessons 30 and 44: examples disprove; they do not prove.)

Common Misconceptions

Misconception	How to pre-empt it
Testing only typical cases.	The four-kinds table; edge cases are required.
Believing a passing test proves correctness.	Exit Q5, explicitly linked to the proof discussions in Lessons 30 and 44.
Rewriting a whole algorithm instead of finding the minimal fix.	”Smallest change” is a stated requirement.
Describing what an algorithm is rather than what it does.	The three-question description frame.
Confusing “all sides equal” with “regular”.	Algorithm P’s fault, straight from Lesson 43.
Treating “greater than ” as including .	Algorithm Q’s fault; the strictness point from Lesson 103.

Enrichment — Competition-Style Problems

E1 (Kangaroo style). An algorithm classifies triangles by asking only “is there a right angle?” How many of the six side-and-angle triangle types can it distinguish?

Answer

Two — “right” and “not right”. A single yes/no question can never produce more than two categories.

E2 (AMC Junior style). A sorter uses three questions but two of its eight paths lead to the same category. How many distinct categories does it produce?

Answer

Seven.

E3 (Challenge). Design a test set of exactly five shapes that would fully exercise a quadrilateral sorter. Justify each choice.

Answer

E.g. square (edge — sits in several categories), non-square rectangle (typical), non-square rhombus (typical), kite (commonly omitted), concave dart (extreme). Together they probe every branch and the usual gaps.

E4 (Challenge). An algorithm is exhaustive and unambiguous but still wrong. Give an example and explain how both can be true.

Answer

The warmup’s broken sorter: every shape reaches exactly one category, but pentagons are labelled “quadrilateral”. Exhaustive and unambiguous concern structure; correctness concerns whether the labels are true.

E5 (Challenge). Why can testing never prove an algorithm correct, and what would?

Answer

Testing checks finitely many inputs; there are infinitely many possible shapes. A proof — an argument covering every case by reasoning about the decisions, not by trying them — is what establishes correctness.

Homework

1. Name the four kinds of test case and give a shape example of each for a triangle sorter.
2. Test this algorithm and find its fault: “1. Are two sides equal? Yes → isosceles, stop. No → scalene, stop.” Use , and .
3. Fix the algorithm in Q2 with the smallest change, and re-test all three cases.
4. Test this algorithm on a square, a rectangle, a rhombus and a kite: “1. All angles right? Yes → rectangle, stop. No → 2. All sides equal? Yes → rhombus, stop. No → other, stop.” Record expected versus actual for each.
5. Write a three-sentence description of the fixed algorithm from Q3: what it does, what each decision contributes, and what it does not handle.
6. Write two test cases that would probe whether a polygon sorter handles concave shapes.
7. Reasoning. Explain why a square is such a useful test case for a quadrilateral sorter.
8. Reasoning. An algorithm passed twelve tests. Explain why its designer still cannot claim it is correct.
9. Challenge. Take your Lesson 104 sorting algorithm. Write a full test table (case, kind, expected, actual, pass/fail) with at least six cases including two edge cases, then state one improvement with its justification.

Answers: Q2 — is called isosceles, which is acceptable under the “at least two” convention but hides equilateral; isosceles ✓; scalene ✓. The fault is that equilateral triangles are never identified. Q3 — insert “Are all three sides equal? Yes → equilateral, stop” as the new step 1. Q4 — square: called rectangle (correct but not most specific); rectangle: rectangle ✓; rhombus: rhombus ✓; kite: other ✓. Q7 — a square belongs to several nested categories at once, so it exposes both wrong question order and over-broad labelling. Q8 — twelve passes leave infinitely many untried inputs; testing reveals faults but cannot exhaust the possibilities.