Show understanding that an algorithm is a solution to a problem expressed as a sequence of defined steps

9.2 Algorithms

Learning Objective (AO1)

Demonstrate that an algorithm is a solution to a problem expressed as a finite, well‑defined sequence of steps.

What Is an Algorithm?

  • Definition: A finite, unambiguous set of instructions that, when followed, solves a specific problem or performs a defined task.

  • Essential properties (AO1):

    • Finite: The procedure terminates after a limited number of steps.

    • Unambiguous (deterministic): Each step has exactly one meaning and produces a single possible outcome.

    • Effective (executable): Every step is simple enough to be carried out by a human with pencil and paper.

Key Characteristics (AO2 – analysis)

CharacteristicWhat It MeansWhy It Matters for Exams
CorrectnessProduces the required output for all valid inputs.Ensures the answer marks the highest marks in AO2.
EfficiencyHow quickly it runs (time) and how much extra memory it needs (space).Used when comparing two possible solutions.
GeneralityWorks for any input that satisfies the problem’s constraints, not just a single example.Shows understanding of abstraction – a common AO2 requirement.
DeterminismGiven the same input, the algorithm always follows the same sequence of steps and yields the same result.Important when justifying correctness.

Representing Algorithms (AO3 – design)

1. Pseudocode (Cambridge style)

Pseudocode mixes natural language with programming constructs. The assignment arrow ← is used for clarity.

// Find the maximum value in an array A[1..n]
INPUT: array A, integer n
max ← A[1]
FOR i ← 2 TO n DO
IF A[i] > max THEN
max ← A[i]
END IF
END FOR
OUTPUT max

2. Flowchart

Flowcharts use standard symbols (oval = Start/End, parallelogram = Input/Output, rectangle = Process, diamond = Decision). The diagram below follows the Cambridge conventions.

+-------------------+
|      Start        |
+----------+--------+
|
+----------v--------+
| Input A[1..n]     |
+----------+--------+
|
+----------v--------+
| max ← A[1]        |
+----------+--------+
|
+----------v-------------------+
| i ← 2                        |
+----------+-------------------+
|
+----------v-------------------+
| i ≤ n ? --------------------+--- No --->+-----------------+
+----------+-------------------+          | Output max     |
| Yes                              +-----+
+----------v-------------------+
| A[i] > max ? ---------------+--- Yes -->+-----------------+
+----------+-------------------+          | max ← A[i]      |
| No                                 +-----+
+----------v-------------------+
| i ← i + 1                    |
+----------+-------------------+
|
+----------v-------------------+
| Repeat loop (back to i ≤ n) |
+------------------------------+

3. Mathematical Notation (optional)

Useful for concise description of well‑known algorithms.

gcd(a, b) =
a               if b = 0
gcd(b, a mod b) otherwise

Step‑wise Refinement (high‑value AO3 technique)

  • Break a large problem into smaller sub‑procedures.

  • Design each sub‑procedure independently, then combine them.

  • Benefits:

    • Clearer structure charts (Paper 4).

    • Easier testing and debugging.

    • Re‑use of sub‑algorithms in different contexts.

Example Algorithms

Linear Search (unsorted list)

  1. i ← 1

  2. WHILE i ≤ n DO

    1. IF L[i] = x THEN OUTPUT “found at position i”; STOP.

    2. ELSE i ← i + 1.

  3. OUTPUT “not found”.

Complexity: Time = O(n), Space = O(1).

Binary Search (sorted list)

INPUT: sorted array L[1..n], target x
low  ← 1
high ← n
WHILE low ≤ high DO
mid ← ⌊(low + high) / 2⌋
IF L[mid] = x THEN
OUTPUT mid
STOP
ELSE IF L[mid] < x THEN
low ← mid + 1
ELSE
high ← mid - 1
END IF
END WHILE
OUTPUT “not found”

Complexity: Time = O(log n), Space = O(1).

Analyzing Algorithms (AO2)

  • Time complexity – growth of running time as a function of input size .

  • Space complexity – additional memory required beyond the input.

AlgorithmTime (Big‑O)Space (Big‑O)Typical exam comment
Linear searchO(n)O(1)Best‑case O(1) if first element matches; worst‑case O(n).
Binary searchO(log n)O(1)Requires the list to be sorted – a point to mention for correctness.
Maximum in an array (single pass)O(n)O(1)Only one loop, no extra data structures.

Why Algorithms Matter (Connecting AO1‑AO3)

  1. Problem solving: Translate a problem statement into a concrete sequence of steps.

  2. Design & communication: Use pseudocode, flowcharts, or structure charts to convey the solution to peers and to the computer (AO3).

  3. Evaluation: Analyse correctness, efficiency and suitability of alternative solutions (AO2).

Summary Checklist (Self‑assessment)

  • Can you define an algorithm and list its three essential properties (finite, unambiguous, effective)?

  • Do you recognise the four key characteristics (correctness, efficiency, generality, determinism) and link them to AO2?

  • Are you able to write a short algorithm in Cambridge‑style pseudocode, using the ← assignment arrow?

  • Can you produce a correctly labelled flowchart for the same algorithm?

  • Do you know how to state time and space complexity using Big‑O notation?

  • Are you familiar with step‑wise refinement as a method for breaking down complex problems?