Specialty Digest

Global English editionLearners’ Study Dashboard — in development
The Knowledge Library for All

Online Courses / University Track / Computing Foundations

Module 8 · Lesson 4 · Core

Capstone preparation: design, test and cost an algorithm

Work through a full design, with testing and costing, ready for the capstone lab.

  • 50 minutes
  • Serves O8
  • Assumes Modules 1 to 7

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.

StateproblemDesignstepsTraceby handTestboundariesCoststeps
Capstone path: from a clear problem to a tested, costed algorithm.

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.

  1. State it. Input: a list of at least two scores. Output: the second-highest. For fewer than two scores, report an error.
  2. 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.
  3. 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.
  4. Test boundaries. See the table.
  5. Cost. One pass; after the first two items, at most two comparisons per item.
Input (scores)Expected second-highestWhy test it
50, 80, 7070Ordinary case
90, 90, 7090Tied top scores count twice
4, 3, 2, 13Descending order
1, 2, 3, 43Ascending order
5, 55Smallest valid list
60No answer: report an errorToo 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.

  1. high = 4, second = 4 from the first two. (1 mark)
  2. x = 2: not greater than high (4) and not greater than second (4). (1 mark)
  3. No change. (1 mark)
  4. 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:

2. For scores 90, 90, 70 the second-highest (ties counting twice) is:

3. A list with one score should:

4. Which test most likely catches a fault with ties?

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

MistakeWhy it fails
Leaving out the error caseState what happens for invalid input.
Testing only typical listsAdd ties and the smallest list.
Not counting the costState 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.