Practice question · Sort into groups
An algorithm says HOW to compute; a specification says only WHAT the answer is. Sort each item.
Groups: Algorithm · Specification only
- Scan the list keeping the largest value seen so far, then report it
- Replace (a, b) by (b, a mod b) until b is 0, then report a
- The gcd of a and b is their largest common divisor
- The prime factorisation is the unique product of primes equal to n
- Test each of 2, 3, ..., n-1 as a divisor of n; if none divides, report n prime
Hints
- Ask of each item: could a machine follow this and halt with an answer?
- A perfectly precise description of the answer can still tell you nothing about producing it.
Show the answer
Algorithm: Replace (a, b) by (b, a mod b) until b is 0, then report a, Test each of 2, 3, ..., n-1 as a divisor of n; if none divides, report n prime, Scan the list keeping the largest value seen so far, then report it
Specification only: The gcd of a and b is their largest common divisor, The prime factorisation is the unique product of primes equal to n
Why
a1, a3 and a5 give concrete terminating procedures. a2 and a4 characterise the answer without saying how to find it, the classic confusion of this lesson. A definition becomes an algorithm only when it is turned into steps.
Practise Algorithms and Computational Thinking
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Algorithms and Computational Thinking
- Order the steps of the algorithm that finds the largest value in a list.
- A recipe is a precise sequence of steps and is not an algorithm in the strict sense. Which requirement does…
- Select every procedure below that FAILS to be a genuine algorithm.
- A specification says WHAT the answer must be; an algorithm says HOW to get it. Why is the distinction worth…