104i - Designing Sorting Algorithms

Lesson 104 — Designing Algorithms to Sort Shapes by Attributes

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

Equipment: sets of shape cards (triangles, quadrilaterals, other polygons — regular and irregular, at least 15 per group).

Learning Intentions

• To design an algorithm that sorts and classifies shapes by their attributes.
• To choose testable questions that separate shapes efficiently.

Success Criteria

I can:

1. Choose attributes that can be tested with a yes/no question.
2. Design a decision-tree algorithm that classifies every shape in a set.
3. Order my questions so the sorting is efficient.
4. Trace my algorithm on any shape and reach exactly one classification.

Warmup

(6 minutes — twenty questions, whole class)

The teacher secretly picks one shape card from a displayed set of eight. The class asks yes/no questions only to identify it.

1. Play one round, counting the questions used.
2. Which question narrowed things down the most? Why?
3. Which question was nearly useless? Why?

The principle to draw out: the best question splits the remaining possibilities roughly in half. “Is it a triangle?” (with four triangles among eight) beats “Is it the regular hexagon?” (which eliminates one).

(This is the halving strategy from Lesson 103’s guessing game, now applied to shapes.)

Activities

Activity 1 — Explicit Instruction: Attributes and Decision Trees (14 min)

A usable attribute must be testable — answerable yes or no by looking or measuring, with no judgement:

Testable ✓	Not testable ✗
Does it have exactly sides?	Is it a nice shape?
Are all sides equal?	Is it big?
Does it have a right angle?	Does it look regular?
Are any sides parallel?	Is it pointy?

The decision tree — the standard way to write a sorting algorithm:

                    How many sides?
                    /      |       \
                   3       4        other
                   |       |          |
          All sides equal? Parallel   Regular?
             /     \       pairs?      /   \
          yes       no      ...      yes    no
        equilateral  ...

I do — build a triangle sorter with the class, live:

1. Are all three sides equal?
   • Yes → equilateral. Stop.
   • No → go to step 2.
2. Are exactly two sides equal?
   • Yes → isosceles. Stop.
   • No → scalene. Stop.

Test it on every triangle card. Does each land in exactly one category? (Yes — the categories are exhaustive and non-overlapping. This is what a classification algorithm must achieve.)

Two requirements to name:

• Exhaustive: every shape reaches a classification — no shape falls through.
• Unambiguous: no shape reaches two different classifications.

The ordering question. Could we ask “exactly two equal?” first? Yes — but then equilateral triangles answer “no” and would be wrongly called scalene. Order matters when categories nest (Lesson 41’s “at least two equal” convention).

We do — a quadrilateral sorter, built together:

1. Are all four sides equal?
   • Yes → go to step 2.
   • No → go to step 3.
2. Are all four angles right angles?
   • Yes → square. No → rhombus. Stop.
3. Are all four angles right angles?
   • Yes → rectangle. No → go to step 4.
4. Are there two pairs of parallel sides?
   • Yes → parallelogram. No → go to step 5.
5. Is there exactly one pair of parallel sides?
   • Yes → trapezium. No → kite or irregular. Stop.

Trace it on a square, a rhombus, a rectangle and a trapezium card. Then ask: where does a kite end up? (Step 5’s “no” branch — the algorithm lumps kites with irregulars. That is a limitation to name honestly, and to fix in the homework.)

Activity 2 — Design Your Own Sorter (14 min)

Pairs, with shape cards. The lesson’s core task.

Design an algorithm that sorts your whole set of shape cards into named categories.

Requirements:

1. Written in numbered steps with clear yes/no decisions.
2. Every card reaches exactly one classification.
3. No untestable questions.
4. Trace it on at least five cards, showing the path each takes.

Circulating prompts:

Prompt	Purpose
Which question would split your pile most evenly?	Efficiency — the halving principle.
Take this card and follow your own steps aloud.	Self-tracing exposes gaps fastest.
Where does this card end up?	Hand them the awkward one — a square, a kite, a concave shape.
Is that question answerable by looking, or does it need a ruler?	Both are fine — but the tool must be available.
Two of your branches lead to “quadrilateral”. Is that a problem?	Only if it should have been split further. What is your purpose?

Extension for fast pairs: count the maximum number of questions your algorithm needs for any card. Can you re-order the questions to reduce it?

Activity 3 — Inquiry: the Same Set, Different Trees (9 min)

Two pairs compare algorithms.

Swap your sorting algorithm with another pair.

1. Run their algorithm on three of your cards. Does each reach exactly one category?
2. Do their categories match yours? If not, is one wrong — or just different?
3. Which algorithm asks fewer questions on average?
4. Find a shape (real or invented) that breaks one of the algorithms.

Socratic scaffolding:

Prompt	Purpose
Did both algorithms classify the square the same way?	Nesting (Lesson 42) means a square is legitimately a rectangle and a rhombus.
So can two correct algorithms disagree?	Yes — they may sort to different levels of detail, or use different conventions.
What would make one genuinely wrong?	If a shape reaches no category, or two categories, or a question is untestable.
Q4: what breaks an algorithm?	Concave shapes, shapes with more sides than anticipated, or a category the tree never offers.
Looking back	Correctness is about exhaustiveness and unambiguity — not about agreeing with someone else’s tree.

Checks for Understanding

(5 minutes — exit ticket)

1. Give two testable attributes of a polygon and one untestable “attribute”.
2. Write a three-step algorithm that separates polygons into “triangle”, “quadrilateral” and “other”.
3. In the triangle sorter, why must “all three sides equal?” come before “exactly two equal?”
4. What two requirements must a classification algorithm meet?
5. Reasoning. Two pairs’ algorithms classify the same square differently — one says “square”, the other “rhombus”. Is either wrong?

Answers: 1. E.g. number of sides, all sides equal, has a right angle; untestable: “looks regular”; 2. 1. Does it have sides? Yes → triangle, stop. No → 2. Does it have sides? Yes → quadrilateral, stop. No → other, stop.; 3. Otherwise equilateral triangles answer “no” to the two-equal test and are wrongly classified; 4. Exhaustive and unambiguous; 5. Neither is wrong — a square is a rhombus (Lesson 42’s hierarchy); the algorithms simply stop at different levels of specificity.

Common Misconceptions

Misconception	How to pre-empt it
Untestable questions (“is it pointy?”).	The testable/untestable table; enforced in the design task.
Categories that overlap or leave gaps.	Exhaustive and unambiguous, named and checked by tracing.
Wrong question order with nested categories.	The equilateral/isosceles ordering trap, demonstrated.
Believing there is one correct decision tree.	The swap inquiry: different trees can both be correct.
Designing without tracing.	Five traces are a stated requirement.
Ignoring awkward shapes.	Circulating prompt hands them one.

Enrichment — Competition-Style Problems

E1 (Kangaroo style). A sorter asks: ” sides?” then “all equal?” then “right angles?” Which shape reaches the end of the yes–yes–yes path?

Answer

A square.

E2 (AMC Junior style). A decision tree has yes/no questions. What is the greatest number of different categories it can produce?

Answer

— each question doubles the number of possible paths.

E3 (Challenge). Design the shortest algorithm that distinguishes square, rectangle, rhombus and parallelogram (assuming all four sides and two pairs of parallel sides are given). How many questions are needed?

Answer

Two: 1. All sides equal? 2. All angles right angles? The four yes/no combinations give exactly the four shapes — yes/yes square, yes/no rhombus, no/yes rectangle, no/no parallelogram.

E4 (Challenge). A sorter must separate shapes, one per category. If every question splits the remaining set exactly in half, how many questions are needed?

Answer

: four questions, since .

E5 (Challenge). Why can no yes/no decision tree with questions classify shapes into distinct categories?

Answer

Three questions give at most distinct paths, so at most categories — two shapes must share.

Homework

1. List four testable attributes of a polygon and two untestable ones, with a reason for each untestable one.
2. Write an algorithm sorting triangles into equilateral, isosceles and scalene. Trace it on triangles with sides , and .
3. Write an algorithm sorting polygons by side count into triangle, quadrilateral, pentagon, hexagon and “more than six”.
4. Improve the class quadrilateral sorter so that kites get their own category. Write the extra step and say where it goes.
5. Trace the class quadrilateral sorter on: a square; a rectangle ; a rhombus with a angle; an isosceles trapezium. State the path each takes.
6. A decision tree uses questions. What is the maximum number of categories?
7. Reasoning. Explain why the order of questions matters when categories are nested.
8. Reasoning. Explain what it means for a classification algorithm to be exhaustive, and give an example of one that is not.
9. Challenge. Design an algorithm that sorts any polygon into: regular, irregular convex, or concave. State clearly how each decision would be tested.

Answers: Q2 — as the class version; equilateral at step 1; isosceles at step 2; scalene at step 2’s no-branch. Q4 — insert before the final “kite or irregular”: “Are there two pairs of adjacent equal sides? Yes → kite. No → irregular.” Q5 — square: 1-yes, 2-yes; rectangle: 1-no, 3-yes; rhombus: 1-yes, 2-no; trapezium: 1-no, 3-no, 4-no, 5-yes. Q6 — . Q7 — a broader category tested first will capture shapes that belong in a narrower one; testing narrowest-first (or ordering to exclude) avoids it. Q8 — every input reaches a category; a sorter offering only “triangle” and “quadrilateral” is not exhaustive, since a pentagon falls through. Q9 — 1. Are all sides equal AND all angles equal? Yes → regular, stop. No → 2. Is any interior angle greater than ? Yes → concave, stop. No → irregular convex, stop. Tests: measure sides and angles; a reflex angle is visible as a “dent”.