Phase 1: Prepare
Step 1 Warm-up recall
From M8.L3: is searching an unsorted list easy, hard or impossible?
Private: nothing you type here is sent or stored.
Step 2 Learning goal
By the end of this lesson you can:
- state a problem exactly (Foundation);
- design and trace an algorithm (Core);
- test its boundaries and count its cost (Core).
Phase 2: Teach
Step 3 A familiar example
A good design is not just a method that works once. It is a method that you can state, trace, test at its edges and cost, so that other people can trust it.
Step 4 Clear explanation
The capstone uses the whole course. Follow five stages.
Take this problem: find the second-highest score in a list, where a tied top score counts twice. For 90, 90, 70 the answer is 90.
- State it. Input: a list of at least two scores. Output: the second-highest. For fewer than two scores, report an error.
- Design. Let high be the larger of the first two scores and second the smaller. For each later score x: if x is greater than high, set second to high and then high to x; otherwise if x is greater than second, set second to x. Report second.
- Trace. For 50, 80, 70: high 80, second 50; x = 70 is not greater than 80 but is greater than 50, so second becomes 70. Answer 70.
- Test boundaries. See the table.
- Cost. One pass; after the first two items, at most two comparisons per item.
| Input (scores) | Expected second-highest | Why test it |
|---|---|---|
| 50, 80, 70 | 70 | Ordinary case |
| 90, 90, 70 | 90 | Tied top scores count twice |
| 4, 3, 2, 1 | 3 | Descending order |
| 1, 2, 3, 4 | 3 | Ascending order |
| 5, 5 | 5 | Smallest valid list |
| 60 | No answer: report an error | Too few items |
Tests that include ties, orders and the smallest valid input are the kind that catch faults. A written record of the problem, steps, tests and cost is what lets another person check the design, in any programming language. The entry on the algorithm underlies the whole path.
Step 5 Worked example (4 marks)
Trace the design on 4, 4, 2.
- high = 4, second = 4 from the first two. (1 mark)
- x = 2: not greater than high (4) and not greater than second (4). (1 mark)
- No change. (1 mark)
- Answer: second-highest is 4, correct because the tied top score counts twice. (1 mark)
Phase 3: Practise
Step 6 Learner practice (instant-marked)
1. The first stage of the design path is to:
A design needs a precise problem.
2. For scores 90, 90, 70 the second-highest (ties counting twice) is:
The tied top score counts twice.
3. A list with one score should:
There is no second-highest.
4. Which test most likely catches a fault with ties?
It checks equal values at the smallest size.
Phase 4: Close
Step 7 Recap
- State, design, trace, test, cost.
- Test ties, orders and the smallest valid input.
- Write down the problem, steps, tests and cost.
Step 8 Exit ticket (ungraded)
Trace the design on 7, 9, 8 and give the answer.
Private: nothing you type here is sent or stored.
Step 9 Go further (Extension)
Choose your own capstone problem and write the five stages.
Common mistakes
| Mistake | Why it fails |
|---|---|
| Leaving out the error case | State what happens for invalid input. |
| Testing only typical lists | Add ties and the smallest list. |
| Not counting the cost | State the number of comparisons. |
Limits. Testing shows the presence of faults, not their absence; the tests chosen here are a sensible start rather than proof.