Computer science · 02 / 06
Algorithms: inputs, steps, output
High school foundations · Worked example and 4 exercises with solutions, at your pace.
The principle, simply
An algorithm specifies operations for a family of problems. Separate inputs, processing and output. A condition chooses a branch; a loop repeats operations. Trace variables on a small example and then test a boundary case. One successful example does not establish correctness everywhere.
- 01Inputs
- 02Initialisation
- 03Steps and conditions
- 04Output and tests
WORKED EXAMPLE
From principle to reasoning
To sum values, start at total = 0 and add each item. A trace table records each value and the updated total.
Solve a problem in this subject
- Specify the contract
Define inputs, types, outputs and forbidden cases. State whether a search algorithm requires sorted data.
- Trace a small example
Tabulate variables, tested conditions and actions using a small hand-checkable example.
- Test boundaries
Consider empty inputs, one item, duplicates, missing values and numeric limits where relevant. Define the output or explain rejection.
- Justify
Explain termination and correctness. Distinguish operation counts, measured time and memory use.
YOUR TURN
01 · Try before checking
Why not initialise total to the first value and then loop over the entire list?
One hint
Check whether the first item is counted twice.
Reveal and understand the solution
It is counted once in initialisation and again in the loop. Match initialisation with loop bounds.
Compare method, conditions and answer; identify the exact part to revisit.
IMPROVE THROUGH PRACTICE
Three additional challenges with solutions
Start with the first challenge. Write your method before opening a hint; use the solution to find the first step that needs work.
Trace s = 0; for x in [2,5,1], s = s + x. Find final s.
A hint to get started
Record the accumulator after each iteration.
Step-by-step solution
- Successive values are 2, 7 and 8.
- Final s is 8.
- Zero is the additive identity.
Which step did you miss? Retry without help, then explain why the method works.
Why does initialising a maximum to 0 fail for [−5,−2,−8]?
A hint to get started
No element exceeds zero.
Step-by-step solution
- The algorithm would retain 0, which is not in the list.
- The actual maximum is −2.
- Start with the first element of a nonempty list and handle an empty list separately.
Which step did you miss? Retry without help, then explain why the method works.
How should a mean algorithm be tested?
A hint to get started
Include boundary cases and hand-computable results.
Step-by-step solution
- Test a short list, one value and negative values.
- Define behaviour for an empty list, whose mean is undefined.
- Compare with independent arithmetic, not merely absence of errors.
Which step did you miss? Retry without help, then explain why the method works.
The trap to avoid
Test empty lists, boundary values and termination.
Without notes, can you…
- Explain the principle in your own words?
- Rebuild the diagram and its connections?
- Solve the exercise and justify the method?
Choosing a state saves it in this browser. This is your assessment, not a grade.