pseudocode using the three basic constructs of sequence, decision, and iteration

9.2 Algorithms – Pseudocode and the Three Fundamental Constructs

1. What Is an Algorithm?

An algorithm is a finite, well‑defined set of instructions that solves a problem or performs a computation. Every algorithm must be:

• Unambiguous – each step has a single, clear meaning.
• Finite – it terminates after a limited number of steps.
• Effective – each step can be carried out in a reasonable amount of time.

2. Algorithm Design Process (Stepwise Refinement)

Cambridge AS & A‑Level expects you to show how an algorithm is developed from a high‑level idea to detailed pseudocode.

1. Abstraction – Identify the essential features of the problem and ignore irrelevant details.
2. Decomposition – Break the problem into smaller, manageable sub‑problems.
3. Stepwise Refinement – Replace each sub‑problem with a more detailed description until you reach executable pseudocode.

During refinement you repeatedly use the three basic constructs (sequence, decision, iteration) and, where appropriate, recursion.

3. The Three Basic Constructs (and Recursion)

READ a
READ b
SET sum ← a + b
WRITE sum

IF a > b THEN
    SET max ← a
ELSE
    SET max ← b
ENDIF

SET i ← 1
WHILE i ≤ n DO
    WRITE i
    SET i ← i + 1
ENDWHILE

FUNCTION factorial(n)
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n * factorial(n‑1)
    ENDIF
ENDFUNCTION

4. Pseudocode Conventions

• Keywords are written in UPPER CASE (e.g., IF, WHILE, ENDWHILE).
• Indentation (normally 4 spaces) shows block structure.
• Variable names should be meaningful; data type is not required.
• Mathematical symbols may be written using LaTeX‑style notation, e.g., $a \le b$, $i \leftarrow i + 1$.
• Input and output are represented by READ/WRITE (or INPUT/OUTPUT).

5. Detailed Examples

5.1 Sequence – Computing the Area of a Circle

Given a radius r, compute the area $A = \pi r^2$.

READ r
SET A ← 3.14159 * r * r
WRITE "Area =", A

5.2 Decision – Grade Classification

Assign a grade based on a mark m (0–100).

READ m
IF m ≥ 80 THEN
    SET grade ← 'A'
ELSE IF m ≥ 70 THEN
    SET grade ← 'B'
ELSE IF m ≥ 60 THEN
    SET grade ← 'C'
ELSE IF m ≥ 50 THEN
    SET grade ← 'D'
ELSE
    SET grade ← 'F'
ENDIF
WRITE "Grade:", grade

5.3 Iteration – Sum of the First n Natural Numbers

Calculate $S = 1 + 2 + \dots + n$.

READ n
SET i ← 1
SET S ← 0
WHILE i ≤ n DO
    SET S ← S + i
    SET i ← i + 1
ENDWHILE
WRITE "Sum =", S

5.4 Combined Example – Finding the Maximum in a List

Given n integers stored in an array $A[1..n]$, determine the maximum value.

READ n
FOR i ← 1 TO n DO
    READ A[i]
ENDFOR

SET max ← A[1]
FOR i ← 2 TO n DO
    IF A[i] > max THEN
        SET max ← A[i]
    ENDIF
ENDFOR

WRITE "Maximum =", max

5.5 Searching Algorithms

5.5.1 Linear Search (Unsorted Array)

READ n                // size of the array
FOR i ← 1 TO n DO
    READ A[i]
ENDFOR
READ key               // value to find
SET found ← FALSE
FOR i ← 1 TO n DO
    IF A[i] = key THEN
        SET found ← TRUE
        EXITFOR
    ENDIF
ENDFOR

IF found THEN
    WRITE "Key found at position", i
ELSE
    WRITE "Key not present"
ENDIF

When to use: Small or unsorted data sets where simplicity is more important than speed.

5.5.2 Binary Search (Sorted Array)

READ n
FOR i ← 1 TO n DO
    READ A[i]          // assume A is sorted in ascending order
ENDFOR
READ key

SET low ← 1
SET high ← n
SET found ← FALSE

WHILE low ≤ high DO
    SET mid ← (low + high) DIV 2
    IF A[mid] = key THEN
        SET found ← TRUE
        EXITWHILE
    ELSE IF A[mid] < key THEN
        SET low ← mid + 1
    ELSE
        SET high ← mid - 1
    ENDIF
ENDWHILE

IF found THEN
    WRITE "Key found at position", mid
ELSE
    WRITE "Key not present"
ENDIF

When to use: Large, sorted data sets – runs in $O(\log n)$ time.

5.6 Sorting Algorithms (O(n²) Examples)

5.6.1 Insertion Sort

READ n
FOR i ← 1 TO n DO
    READ A[i]
ENDFOR

FOR i ← 2 TO n DO
    SET key ← A[i]
    SET j ← i - 1
    WHILE j ≥ 1 AND A[j] > key DO
        SET A[j+1] ← A[j]
        SET j ← j - 1
    ENDWHILE
    SET A[j+1] ← key
ENDFOR

WRITE "Sorted array:"
FOR i ← 1 TO n DO
    WRITE A[i]
ENDFOR

5.6.2 Bubble Sort

READ n
FOR i ← 1 TO n DO
    READ A[i]
ENDFOR

FOR i ← 1 TO n-1 DO
    FOR j ← 1 TO n-i DO
        IF A[j] > A[j+1] THEN
            SET temp ← A[j]
            SET A[j] ← A[j+1]
            SET A[j+1] ← temp
        ENDIF
    ENDFOR
ENDFOR

WRITE "Sorted array:"
FOR i ← 1 TO n DO
    WRITE A[i]
ENDFOR

Both algorithms have a worst‑case time‑complexity of $O(n^2)$. They are acceptable for small data sets or when teaching basic concepts.

5.7 Recursion – Factorial (Alternative to Iteration)

FUNCTION factorial(n)
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n * factorial(n‑1)
    ENDIF
ENDFUNCTION

READ n
SET result ← factorial(n)
WRITE "n! =", result

Recursion replaces explicit loops with self‑reference. The algorithm must have a base case (here, $n=0$) to guarantee termination.

5.8 Using an Abstract Data Type (ADT) – Depth‑First Search with a Stack

Assume a graph is represented by an adjacency list Adj[1..V]. The algorithm visits all vertices reachable from a start vertex s.

READ V                     // number of vertices
FOR i ← 1 TO V DO
    READ Adj[i]            // list of neighbours for vertex i
ENDFOR
READ s                     // start vertex

CREATE empty STACK S
CREATE array visited[1..V] ← FALSE

PUSH S, s
SET visited[s] ← TRUE

WHILE S is not empty DO
    POP S, v
    WRITE "Visit", v
    FOR each w in Adj[v] DO
        IF NOT visited[w] THEN
            PUSH S, w
            SET visited[w] ← TRUE
        ENDIF
    ENDFOR
ENDWHILE

6. Coverage of the Cambridge International AS & A Level Computer Science (9618) Syllabus

6.1 Data Representation – Compression

• Lossless: Run‑Length Encoding (RLE), Huffman coding.
• Lossy: JPEG (DCT + quantisation), MP3 (psychoacoustic model).
• Typical exam question: “A 500 KB text file is compressed with RLE and reduces to 350 KB. Calculate the compression ratio.”

6.2 Computer Systems – Key Concepts

• Von Neumann architecture, CPU fetch‑decode‑execute cycle.
• Primary vs. secondary storage, cache hierarchy.
• OSI model – layers relevant to exam (Physical, Data Link, Network, Transport).

6.3 Databases – Modelling & SQL

• Entity‑Relationship diagram symbols (entity, relationship, cardinality).
• Normalisation to 3NF – example with a “Students” table.
• SQL snippets: SELECT name FROM Students WHERE grade = 'A';

6.4 Web Development – Core Elements

• HTML5 skeleton, form input, CSS selector basics.
• Client‑server request/response cycle, statelessness of HTTP.
• Security: HTTPS, same‑origin policy, basic XSS mitigation.

6.5 Security – Cryptography Overview

• Symmetric: AES, block vs. stream ciphers.
• Asymmetric: RSA – key generation, encryption/decryption.
• Hash functions: SHA‑256, properties (pre‑image resistance, collision resistance).
• Emerging topic: quantum‑resistant algorithms (brief mention for AO2).

6.6 Ethics & Ownership

• Professional bodies: BCS, IEEE, ACM Code of Ethics.
• Intellectual‑property licences – GPL, MIT, proprietary.
• Ethical decision‑tree example: “Is the software being used to infringe privacy?”

6.7 Programming – Structured & Object‑Oriented Concepts

• Procedural decomposition, modularity, scope of variables.
• OOP basics: class, object, inheritance, polymorphism (illustrated with a simple Vehicle class).
• Exception handling pattern:

  TRY
      … statements …
  CATCH error
      WRITE "Error:", error
  ENDTRY

6.8 Systems Development – Project Management

• SDLC stages: Analyse, Design, Implement, Test, Maintain.
• Gantt chart sketch, risk register (probability × impact).
• Documentation: requirements specification, user manual, test plan.

6.9 Emerging Technologies – AI & Parallel Processing

• Search‑tree AI: depth‑first, breadth‑first, A* (heuristic cost).
• Virtual Machine concept – byte‑code interpretation (e.g., Java VM).
• Parallelism: multi‑threading, shared‑memory vs. distributed‑memory models.

6.10 A‑Level Advanced Topics (Units 13‑20)

• Advanced Data Representation: floating‑point IEEE‑754, colour models (RGB, CMYK).
• Advanced Algorithms: merge‑sort, quick‑sort, Dijkstra’s shortest‑path.
• Artificial Intelligence: simple neural‑net forward pass, back‑propagation outline.
• Exception Handling: try‑catch‑finally, custom exception classes.
• Concurrency: mutex, semaphore, deadlock example.

7. Evaluating Algorithms

Use the sorting and searching examples to compare efficiencies: linear search $O(n)$ vs. binary search $O(\log n)$; insertion sort $O(n^2)$ vs. merge sort $O(n\log n)$ (the latter appears in the A‑Level unit).

8. Stepwise Refinement & Flowcharts – A Mini Case Study

1. High‑level description: “Read a list of numbers and output the average.”
2. Decomposition:
   • Read the number of elements n.
   • Read the n values and accumulate their sum.
   • Divide the sum by n to obtain the average.
3. Refined pseudocode (uses sequence, iteration and decision):

   READ n
   SET total ← 0
   FOR i ← 1 TO n DO
       READ x
       SET total ← total + x
   ENDFOR
   IF n = 0 THEN
       WRITE "No data"
   ELSE
       SET avg ← total / n
       WRITE "Average =", avg
   ENDIF

4. Flowchart (optional) – linear start → input → loop (diamond) → decision (n = 0) → output.

9. Testing & Validation

• Dry‑run with at least two different input sets (including edge cases).
• Boundary testing: values at the limits of the input domain (e.g., n = 0, n = 1, maximum allowed size).
• Trace table – record variable values after each step of the algorithm.
• Loop‑termination check – ensure loop variables are updated and the condition will eventually become false.
• Unit testing for functions (e.g., factorial) – test typical, minimum and maximum inputs.

10. Common Pitfalls

• Forgetting to update the loop variable (causes infinite loops).
• Using the wrong relational operator in a decision (e.g., = instead of == or <=).
• Incorrect indentation leading to statements being placed outside the intended block.
• Not handling edge cases such as n = 0 or empty input.
• Missing a base case in recursive algorithms.
• Assuming an array is sorted when applying binary search.
• Confusing integer division (DIV) with real division (/) in pseudocode.
• Over‑using global variables – reduces readability and increases risk of side‑effects.

11. Summary

1. All algorithms can be expressed using the three fundamental constructs: sequence, decision and iteration (or recursion where appropriate).
2. Stepwise refinement, supported by clear pseudocode conventions, bridges the gap between a problem description and a working solution.
3. Understanding the full Cambridge 9618 syllabus – from data representation to AI – ensures you can answer any exam question, link concepts across units, and meet the AO1‑AO3 assessment objectives.
4. Always validate your algorithms with dry‑runs, trace tables and boundary tests to avoid infinite loops and logical errors.
5. Good coding style (meaningful names, consistent indentation, proper documentation) contributes to the readability and maintainability marks in Paper 2.