Write algorithms with decision-making (branching, looping)

4. Algorithms and Flowcharts

Learning Objective

Write clear, correct algorithms that use decision‑making (branching and looping), include procedures/sub‑routines, and represent them accurately with flowcharts. All structures must be presented using the Cambridge standard notation.

1. What Is an Algorithm?

• Finite – it terminates after a limited number of steps.
• Ordered – the steps are performed in a specific sequence.
• Clear and unambiguous – every instruction can be understood without interpretation.
• Effective (executable) – each step can be carried out with the resources available.
• Correct – produces the required output for all valid inputs.

2. Operators Used in Decision‑Making

3. Pseudocode Conventions (Cambridge Syllabus 4.1)

• All keywords are written in UPPERCASE (e.g. IF, THEN, ELSE, ENDIF, WHILE, DO, ENDWHILE, REPEAT, UNTIL, FOR, TO, STEP, ENDFOR, CASE, ENDCASE, PROCEDURE, FUNCTION, CALL, RETURN).
• Indentation reflects block structure – each new level is indented one tab (or four spaces).
• Variables must be given meaningful names and initialised before they are used.
• Optional comments are placed after a double slash //.
• Procedures perform actions without returning a value; functions (or procedures that use RETURN) produce a result.

4. Flowchart Symbols (Standard Cambridge Set)

5. Decision‑Making (Branching)

• IF … THEN – executes the following block only when the condition is true.
• IF … THEN … ELSE – chooses between two alternative blocks.
• ELSE IF … – adds further alternatives to an IF‑ELSE chain.
• Nested IF – an IF statement inside another IF (useful for multiple levels of testing).
• CASE … OF … ENDCASE – selects one of many alternatives; equivalent to a series of IF … ELSEIF … but clearer when testing a single variable.
• Nested CASE – a CASE block inside another CASE or IF block.

Example: Grade Assignment Using CASE

FUNCTION AssignGrade(score) RETURNS CHAR
    CASE score OF
        90 TO 100: grade ← 'A'
        80 TO 89 : grade ← 'B'
        70 TO 79 : grade ← 'C'
        60 TO 69 : grade ← 'D'
        0  TO 59 : grade ← 'F'
    ENDCASE
    RETURN grade
ENDFUNCTION

6. Looping (Repetition)

Three loop structures are required by the syllabus. All use UPPERCASE keywords.

• WHILE … DO … ENDWHILE – condition tested before each iteration (pre‑test loop).
• REPEAT … UNTIL … ENDREPEAT – condition tested after each iteration (post‑test loop); guarantees at least one execution.
• FOR counter ← start TO end STEP step DO … ENDFOR – counter‑controlled loop; the number of iterations is known beforehand.

Nested Loops

Loops may be placed inside other loops to handle two‑dimensional data such as tables, matrices, or grids.

Example: Multiplication Table (Nested FOR Loops)

PROCEDURE PrintTable(max)
    FOR i ← 1 TO max DO
        FOR j ← 1 TO max DO
            OUTPUT i * j, " "
        ENDFOR
        OUTPUT NEWLINE
    ENDFOR
ENDPROCEDURE

7. Procedures and Functions

A procedure groups statements that perform a specific task but does not return a value. A function (or a procedure that uses RETURN) produces a result that can be used by the calling algorithm.

Pseudocode Syntax

PROCEDURE ProcedureName(param1, param2, …)
    // body of the procedure
ENDPROCEDURE

FUNCTION FunctionName(param1, param2, …) RETURNS datatype
    // body of the function
    RETURN result
ENDFUNCTION

CALL ProcedureName(arg1, arg2, …)
value ← CALL FunctionName(arg1, arg2, …)

Flowchart Representation

• Use a rounded rectangle labelled with the procedure or function name to indicate a call.
• The sub‑routine itself is drawn on a separate page (or a separate part of the diagram) with its own start‑oval and end‑oval, linked by a connector.

Example: Calculate the Average of Three Numbers (Function)

FUNCTION CalcAverage(a, b, c) RETURNS REAL
    sum ← a + b + c
    avg ← sum / 3
    RETURN avg
ENDFUNCTION

// Main algorithm
INPUT x, y, z
average ← CALL CalcAverage(x, y, z)
OUTPUT "Average =", average

8. Algorithm Examples (All Required Structures)

8.1 Factorial Using a WHILE Loop

FUNCTION Factorial(n) RETURNS INTEGER
    result ← 1
    counter ← n
    WHILE counter > 0 DO
        result ← result * counter
        counter ← counter - 1
    ENDWHILE
    RETURN result
ENDFUNCTION

8.2 Sum Until Zero Using REPEAT…UNTIL

PROCEDURE SumUntilZero()
    total ← 0
    REPEAT
        INPUT x
        total ← total + x
    UNTIL x = 0
    OUTPUT "Total =", total
ENDPROCEDURE

8.3 Grading System Using CASE (see 5.4)

8.4 Print All Even Numbers ≤ n (FOR Loop + IF)

PROCEDURE PrintEven(n)
    FOR i ← 1 TO n DO
        IF i MOD 2 = 0 THEN
            OUTPUT i
        ENDIF
    ENDFOR
ENDPROCEDURE

8.5 Find the Maximum of a List (Procedure with RETURN)

FUNCTION MaxValue(list, size) RETURNS INTEGER
    max ← list[1]
    FOR i ← 2 TO size DO
        IF list[i] > max THEN
            max ← list[i]
        ENDIF
    ENDFOR
    RETURN max
ENDFUNCTION

// Main
INPUT size
DECLARE numbers[ size ]
FOR i ← 1 TO size DO
    INPUT numbers[i]
ENDFOR
big ← CALL MaxValue(numbers, size)
OUTPUT "Maximum =", big

8.6 Nested IF and CASE Example – Determine Discount

FUNCTION Discount(age, member) RETURNS REAL
    IF age < 18 THEN
        IF member = TRUE THEN
            discount ← 0.25   // 25 % for young members
        ELSE
            discount ← 0.10   // 10 % for non‑members
        ENDIF
    ELSE
        CASE member OF
            TRUE : discount ← 0.15
            FALSE: discount ← 0.05
        ENDCASE
    ENDIF
    RETURN discount
ENDFUNCTION

9. Flowchart Illustrations (ASCII with Branch Labels)

9.1 Factorial (WHILE) Flowchart

+-------------------+
|      Start        |
+-------------------+
          |
          v
+-------------------+
| Input n           |
+-------------------+
          |
          v
+-------------------+
| result ← 1        |
| counter ← n       |
+-------------------+
          |
          v
+-------------------+
| counter > 0 ? ----+--- No -->+-------------------+
| (Decision)        |          | Output result     |
+-------------------+          +-------------------+
          | Yes
          v
+-------------------+
| result ← result*counter |
| counter ← counter-1     |
+-------------------+
          |
          +-------------------+
          |   (back to decision)
          v

9.2 Sub‑routine Call – CalcAverage

+-------------------+          +---------------------------+
|      Start        |          |   Procedure CalcAverage   |
+-------------------+          +---------------------------+
          |                               |
          v                               |
+-------------------+          |  INPUT a, b, c          |
| INPUT x, y, z    |          |  sum ← a+b+c            |
+-------------------+          |  avg ← sum/3            |
          |                    |  RETURN avg             |
          v                    +---------------------------+
+-------------------+                     ^
| CALL CalcAverage  |---------------------|
|   (x,y,z)         |
+-------------------+
          |
          v
+-------------------+
| OUTPUT avg        |
+-------------------+
          |
          v
+-------------------+
|        End        |
+-------------------+

9.3 Nested FOR Loops – Multiplication Table

+-------------------+
|      Start        |
+-------------------+
          |
          v
+-------------------+
| INPUT max         |
+-------------------+
          |
          v
+-------------------+
| i ← 1             |
+-------------------+
          |
          v
+-------------------+
| i ≤ max ? ----+--- No -->+-------------------+
| (Decision)    |          |        End        |
+-------------------+      +-------------------+
          | Yes
          v
+-------------------+
| j ← 1             |
+-------------------+
          |
          v
+-------------------+
| j ≤ max ? ----+--- No -->+-------------------+
| (Decision)    |          | i ← i + 1          |
+-------------------+      +-------------------+
          | Yes
          v
+-------------------+
| OUTPUT i*j, " "   |
+-------------------+
          |
          v
+-------------------+
| j ← j + 1         |
+-------------------+
          |
          +-------------------+
          |   (back to j‑decision)
          v

10. Optimising an Algorithm (AO3 – Analysis & Evaluation)

• Identify inefficiencies – e.g., a linear search on a sorted list.
• Replace with a more efficient technique – e.g., use a binary search (O(log n) instead of O(n)).
• Consider space vs. time trade‑offs – storing a pre‑computed lookup table may speed up repeated calculations at the cost of extra memory.
• Document the change – explain why the new algorithm is better (faster, uses less memory, easier to understand).

Example: Optimising a Search

Original linear search:

PROCEDURE LinearSearch(arr, n, key) RETURNS INTEGER
    FOR i ← 1 TO n DO
        IF arr[i] = key THEN
            RETURN i
        ENDIF
    ENDFOR
    RETURN 0   // not found
ENDPROCEDURE

Optimised binary search (array must be sorted):

FUNCTION BinarySearch(arr, n, key) RETURNS INTEGER
    low ← 1
    high ← n
    WHILE low ≤ high DO
        mid ← (low + high) DIV 2
        IF arr[mid] = key THEN
            RETURN mid
        ELSEIF arr[mid] < key THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN 0   // not found
ENDFUNCTION

11. Editing & Error Identification (Syllabus 4.2)

Students must spot both syntactic (keyword misspelling, missing END) and logical (wrong condition, off‑by‑one) errors.

Exercise 11.1 – Logical Error (Post‑test Loop)

PROCEDURE Sum_Until_Zero()
    INPUT x
    total ← 0
    WHILE x ≠ 0 DO
        total ← total + x
        INPUT x
    ENDWHILE
    OUTPUT total
ENDPROCEDURE

• Logical error: If the first input is 0 the loop never runs; the syllabus expects a REPEAT…UNTIL structure that guarantees at least one execution.
• Correction:

PROCEDURE Sum_Until_Zero()
    total ← 0
    REPEAT
        INPUT x
        total ← total + x
    UNTIL x = 0
    OUTPUT total
ENDPROCEDURE

Exercise 11.2 – Syntactic Error (Missing ENDIF)

PROCEDURE CheckAge(age)
    IF age >= 18 THEN
        OUTPUT "Adult"
    ELSE
        OUTPUT "Minor"
    // ENDIF missing here
ENDPROCEDURE

• Syntactic error: The closing ENDIF is omitted, causing a compilation‑style error.
• Corrected version:

PROCEDURE CheckAge(age)
    IF age >= 18 THEN
        OUTPUT "Adult"
    ELSE
        OUTPUT "Minor"
    ENDIF
ENDPROCEDURE

Exercise 11.3 – Logical Error (Off‑by‑One in FOR Loop)

PROCEDURE PrintNumbers(n)
    FOR i ← 1 TO n DO
        OUTPUT i
    ENDFOR
    OUTPUT "Done"
ENDPROCEDURE

• Logical error: The requirement is to print numbers from 0 to n inclusive. The loop starts at 1, omitting 0.
• Correction:

PROCEDURE PrintNumbers(n)
    FOR i ← 0 TO n DO
        OUTPUT i
    ENDFOR
    OUTPUT "Done"
ENDPROCEDURE

12. Step‑by‑Step Guide to Drawing a Flowchart from a Problem Statement

1. Analyse the problem – list inputs, required processing, decisions, and outputs.
2. Identify reusable blocks – any group of steps that could be a sub‑routine should be marked as a procedure or function.
3. Sketch the sequence using the standard symbols (oval, parallelogram, rectangle, diamond, rounded rectangle, connector).
4. Draw loops – connect the last statement of the loop back to the decision diamond (WHILE/REPEAT) or to the counter update (FOR).
5. Label decision arrows with “Yes/No” (or “True/False”) to show the flow of each branch.
6. Check for completeness – every arrow must eventually lead to the End oval; no dangling symbols.
7. Validate against the algorithm – trace a few sample inputs through the flowchart to ensure it mirrors the pseudocode.

13. Comparing Loop Types (with Pseudocode Snippets)

WHILE count < limit DO
    // body
ENDWHILE

REPEAT
    // body
UNTIL choice = 0

FOR i ← 1 TO 10 STEP 2 DO
    // body
ENDFOR

14. Bridge to Later Topics

Mastering algorithms, decision‑making, and flowcharts provides the foundation for all subsequent Cambridge Computer Science units. In Data Structures (Topic 17) you will translate these algorithms into operations on lists, arrays, and trees. In Programming for the Web (Topic 21) the same logical structures are expressed in languages such as Python, JavaScript or PHP, where the pseudocode conventions become actual code. Understanding how to design, optimise, and debug an algorithm now will make the transition to real‑world programming far smoother.