Specialty Digest

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

Online Courses / University Track / Computing Foundations

Module 8 · Capstone

Capstone lab: design, test and cost an algorithm

Design, trace, test and cost an algorithm for a new problem, using the full path from the course.

  • 50 minutes
  • 16 marks
  • Self-marked

50 minutes. Self-marked against the rubric. 16 marks. In the full course this counts toward the labs and cases share (15% of the course grade). Write your answers in the boxes, then open the model answer and tick each mark you earned honestly. Nothing is sent or stored.

Scenario (invented)

A running club (invented) records lap times in seconds for each runner in a list. The coach wants the second-fastest time, meaning the second-smallest value, where two equal fastest times count twice (so 52, 52, 60 gives 52). The list is at least two times long, otherwise the program must report an error.

Tasks

Task 1 (3 marks)

State the problem exactly: the input, the output, and what happens for invalid input.

Private: nothing you type here is sent or stored.

Task 2 (5 marks)

Write the steps of your algorithm in plain language or numbered pseudocode, using conditions.

Private: nothing you type here is sent or stored.

Task 3 (3 marks)

Trace your algorithm on 61, 52, 58, 52. Give fastest and second after each time.

Private: nothing you type here is sent or stored.

Task 4 (5 marks)

Give six test cases with expected answers, including ties and an invalid list. State how many comparisons your algorithm makes at most for a list of n times.

Private: nothing you type here is sent or stored.

Rubric and model answer

Task 1: state the problem (3 marks)

Model: Input: a list of lap times in seconds. Output: the second-smallest time, counting equal fastest times twice. If the list has fewer than two times, report an error.

Task 2: design the steps (5 marks)

Model: If fewer than two times, report an error. Let fastest be the smaller of the first two times and second be the larger. For each later time x: if x < fastest, set second to fastest and fastest to x; otherwise if x < second, set second to x. Report second.

Task 3: trace (3 marks)

Model: first two 61, 52: fastest 52, second 61. x = 58: not < 52, but < 61, so second 58. x = 52: not < 52, but < 58, so second 52. Answer: 52.

Task 4: test and cost (5 marks)

Model: tests: 52, 60, 55 → 55; 52, 52, 60 → 52; 60, 55, 52 → 55; 52, 55, 60 → 55; 70, 70 → 70; 60 → error. Cost: one comparison for the first two and at most two for each later time, so at most 1 + 2(n − 2) comparisons for n ≥ 2, a linear cost.

Marks so far: 0 of 16