Write efficient pseudocode

11.3 Structured Programming

Objective

Develop the ability to write clear, maintainable and efficient pseudocode that follows the principles of structured programming and satisfies the Cambridge AS & A‑Level Computer Science (9618) syllabus.

1. What is Structured Programming?

Structured programming restricts programs to three fundamental control structures – sequence, selection and iteration. It promotes:

• Top‑down design
• Single‑entry, single‑exit blocks
• Modular, hierarchical solutions
• Readability and ease of testing
• Efficient use of time and space

2. Core Principles

3. Programming Basics (Syllabus 11.1)

Cambridge pseudocode uses a fixed set of keywords for declarations and I/O. The table below shows the exact syntax for each data type required by the syllabus.

/* constants */
CONSTANT MAX_SIZE ← 100
CONSTANT PI       ← 3.14159
/* variables – specify the data type */
INTEGER  count, total
REAL     average
CHAR     grade
STRING   name
BOOLEAN  found
DATE     today
/* input & output */
INPUT count               // reads an INTEGER from the keyboard
OUTPUT "Result = ", total // writes to the screen
OUTPUTLN "Done."         // adds a newline

4. Control Constructs (Syllabus 11.2)

The three basic structures plus the additional constructs required by the syllabus.

statement1
statement2
statement3

IF condition THEN
statements
ELSE
statements
ENDIF

CASE variable OF
value1: statements
value2: statements
…
OTHERWISE: statements
ENDCASE

FOR i FROM 1 TO n DO
statements
ENDFOR

WHILE condition DO
statements
ENDWHILE

REPEAT
statements
UNTIL condition

When to use which loop?

• WHILE – when the number of iterations is not known beforehand and the loop may execute zero times.
• REPEAT‑UNTIL – when the loop must execute at least once (e.g., menu selection).
• FOR – when the exact number of repetitions is known or can be calculated.

Nested vs. Flat Control Flow (AO2 tip)

Deeply nested structures often lead to “spaghetti” code that is hard to read and test. The table shows a common nested pattern and a flatter, equivalent version.

FOR i FROM 1 TO n DO
IF condition1(i) THEN
FOR j FROM 1 TO m DO
IF condition2(i,j) THEN
… // many statements
ENDIF
ENDFOR
ENDIF
ENDFOR

FOR i FROM 1 TO n DO
IF NOT condition1(i) THEN
CONTINUE          // skip to next i
ENDIF
FOR j FROM 1 TO m DO
IF NOT condition2(i,j) THEN
CONTINUE      // skip to next j
ENDIF
… // same statements
ENDFOR
ENDFOR

Using CONTINUE (or an early RETURN in a function) reduces indentation depth, improves readability and makes the logical flow easier to analyse.

5. Writing Efficient Pseudocode

Efficiency is about expressing the algorithm so that its computational cost is obvious and unnecessary work is avoided.

1. Identify the most expensive operations (nested loops, recursion, repeated scans of large data structures).
2. Choose data structures that give the best average‑case performance for the required operations (arrays for indexed access, dictionaries for key‑based look‑up, etc.).
3. Prefer count‑controlled FOR loops or pre‑condition WHILE loops with a clear bound over indefinite loops.
4. Store intermediate results instead of recomputing them inside a loop.
5. Analyse each part of the algorithm using Big‑O notation and state the overall time and space complexity.

6. Modular Design (Syllabus 11.3)

6.1 Procedures vs. Functions

6.2 Parameter‑passing conventions

• IN – by value; the module receives a copy.
• OUT – by reference; the module must assign a value before returning.
• INOUT – by reference; the module may read and modify the argument.

Cambridge pseudocode indicates the mode in the header:

PROCEDURE SortArray(INOUT arr[1..n])   // INOUT = by reference
FUNCTION MaxValue(IN arr[1..n]) RETURNS INTEGER   // IN = by value

6.3 Recommended module template

/*--------------------------------------------------------------
Module:   ModuleName
Purpose:  brief description of what the module does
Input:    list of parameters (IN, OUT, INOUT)
Output:   result (if a function) or changes to parameters
--------------------------------------------------------------*/
PROCEDURE ModuleName(IN param1, INOUT param2)
// local variable declarations
INTEGER i, total
// algorithm
…
RETURN          // only for functions
ENDPROCEDURE

6.4 Structure charts & state‑transition diagrams

Although not written in pseudocode, the syllabus expects students to interpret:

• Structure charts – hierarchical boxes showing modules and the data flow between them.
• State‑transition diagrams – nodes representing system states and labelled arrows for events that cause transitions.

These visual tools help plan the modular decomposition before the pseudocode is written.

7. Example: Finding the Second Largest Number (Linear‑time algorithm)

FUNCTION FindSecondLargest(IN list[1..n]) RETURNS INTEGER
// Pre‑condition: n ≥ 2 and the list contains at least two distinct values
INTEGER max        ← list[1]
INTEGER secondMax  ← -∞
FOR i FROM 2 TO n DO
IF list[i] > max THEN
secondMax ← max
max       ← list[i]
ELSE IF list[i] > secondMax AND list[i] ≠ max THEN
secondMax ← list[i]
ENDIF
ENDFOR
RETURN secondMax
ENDFUNCTION

Analysis

• Each element examined once → Time complexity O(n).
• Only a constant number of extra variables → Space complexity O(1).
• No nested loops or recursion, satisfying the single‑entry, single‑exit rule for the loop.

8. Common Pitfalls and How to Avoid Them

• Unnecessary nested loops – often replaceable by a single pass with auxiliary variables.
• Repeated calculations inside loops – move invariant work outside the loop.
• Excessive use of global variables – prefer parameters (IN, OUT, INOUT) to keep modules independent.
• Missing termination condition – every loop must have a clear, reachable exit condition.
• Confusing procedures with functions – only functions return a value.
• Deep indentation (spaghetti code) – use early CONTINUE or RETURN to flatten control flow.

9. Summary Checklist (AO2)

1. Am I using only sequence, selection (IF/ELSE, CASE) and iteration (FOR, WHILE, REPEAT‑UNTIL)?
2. Does each loop have a single, well‑defined exit condition?
3. Are modules small, with a single, well‑specified purpose?
4. Have I identified the most costly operations and minimised them?
5. Is the algorithm’s time and space complexity stated and justified?
6. Have I chosen the appropriate parameter‑passing mode (IN, OUT, INOUT)?
7. Is the indentation level no deeper than three levels (helps avoid spaghetti code)?

10. Self‑Assessment Questions

1. Write pseudocode to compute the factorial of a non‑negative integer using a FOR loop. State its time complexity.

   FUNCTION Factorial(IN n) RETURNS INTEGER
   // Pre‑condition: n ≥ 0
   INTEGER result ← 1
   FOR i FROM 2 TO n DO
   result ← result * i
   ENDFOR
   RETURN result
   ENDFUNCTION

   Time complexity: O(n) (single linear pass).

2. Explain why the following pseudocode is inefficient and rewrite it to improve efficiency.

   FOR i FROM 1 TO n DO
   FOR j FROM 1 TO i DO
   sum ← sum + array[j]
   ENDFOR
   ENDFOR

   Inefficiency: The inner loop repeatedly sums the same prefix of the array, giving a quadratic O(n²) runtime.

   Improved version (single pass):

   INTEGER prefixSum ← 0
   FOR i FROM 1 TO n DO
   prefixSum ← prefixSum + array[i]
   sum       ← sum + prefixSum
   ENDFOR

   Now the algorithm runs in O(n) time and uses only O(1) extra space.

3. Given a list of n numbers, describe a structured‑programming approach to determine whether the list is sorted in ascending order. Provide the pseudocode and its complexity.

   FUNCTION IsSorted(IN list[1..n]) RETURNS BOOLEAN
   // Pre‑condition: n ≥ 1
   FOR i FROM 2 TO n DO
   IF list[i] < list[i‑1] THEN
   RETURN FALSE
   ENDIF
   ENDFOR
   RETURN TRUE
   ENDFUNCTION

   Time complexity: O(n). Space complexity: O(1).

4. Convert the nested loop from question 2 into a “flat” version using CONTINUE (or an early RETURN) and comment on how this improves readability.

   FOR i FROM 1 TO n DO
   IF i = 1 THEN
   CONTINUE          // nothing to add for the first element
   ENDIF
   sum ← sum + prefixSum   // prefixSum already holds Σ_{k=1}^{i‑1} array[k]
   prefixSum ← prefixSum + array[i]
   ENDFOR

   The flat version removes the inner loop, reduces indentation depth, and makes the invariant (prefixSum holds the sum of the processed prefix) explicit.