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.