Designing and analysing an algorithm

Overview

Recall questions on what an algorithm is, analysing a problem before designing, decomposition, pre-conditions and post-conditions, expressing designs, trace tables, off-by-one and boundary testing, iterative versus recursive designs, choosing data structures and generality.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is an algorithm?

   Model answer

   A finite sequence of unambiguous steps that takes some input, carries out a defined process and produces an output, solving a problem or completing a task. It must be precise enough that it can be followed without judgement, and it must terminate rather than run forever.

2. 2

   A student says 'my program is my algorithm'. Why is that not quite right?

   Model answer

   An algorithm is the method itself, independent of any language. A program is one implementation of it. The same algorithm can be written in Python, in pseudocode, as a flowchart or in structured English, and it is still the same algorithm, so the method can be analysed and compared before a single line of code is written.

3. 3

   What are the first things you should establish when analysing a problem before designing an algorithm?

   Model answer

   What the inputs are and where they come from, what output is required and in what form, what processing turns one into the other, what data will be stored and in what structure, and what constraints apply such as how much data there will be, how fast it must run and how much memory is available.

4. 4

   Explain how decomposition helps in the design of an algorithm.

   Model answer

   Decomposition breaks a large problem into smaller sub-problems, each of which can be solved, tested and understood separately. It makes the design manageable, allows different sub-problems to be worked on independently or reused elsewhere, and means a fault can be located in one small part rather than across the whole solution.

5. 5

   What is a pre-condition, and why should an algorithm's design state it?

   Model answer

   A pre-condition is something that must be true before the algorithm is run for it to work correctly, for example that the list is already sorted or that the input value is positive. Stating it makes clear whose responsibility the check is, and prevents the algorithm being used in a situation where it will silently give a wrong answer.

6. 6

   Give three ways an algorithm can be expressed at the design stage.

   Model answer

   Structured English, pseudocode, and a flowchart. All three express the same logic; the choice is about who has to read it. Pseudocode is close enough to code to translate directly, a flowchart makes the flow of control visible, and structured English is easiest for a non-programmer to check.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.