7.1

Topic 7

Algorithm design and problem-solving

  • IGCSE Computer science 0478
  • 8 min read
  • Syllabus 2026, 2027 and 2028

Objectives

  1. 1

    Understand the program development life cycle, limited to: analysis, design, coding and testing

  2. 2

    • aUnderstand that every computer system is made up of sub-systems, which are made up of further sub-systems
    • bUnderstand how a problem can be decomposed into its component parts
    • cUse different methods to design and construct a solution to a problem
  3. 3

    Explain the purpose of a given algorithm

  4. 4

    Understand standard methods of solution

  5. 5

    • aUnderstand the need for validation checks to be made on input data and the different types of validation check
    • bUnderstand the need for verification checks to be made on input data and the different types of verification check
  6. 6

    Suggest and apply suitable test data

  7. 7

    Complete a trace table to document a dry-run of an algorithm

  8. 8

    Identify errors in given algorithms and suggest ways of correcting these errors

  9. 9

    Write and amend algorithms for given problems or scenarios, using: pseudocode, program code and flowcharts

Cambridge IGCSE Computer Science 0478 syllabus 2026-2028, 7.1 Algorithm design and problem-solving (copied for internal use as permitted by Cambridge)

Detailed · Deep study

1The program development life cycle

Fig. 1Four stages.
StageTasks
analysisabstraction (removing unnecessary detail to focus on what matters); decomposition of the problem; identification of the problem and the requirements (what the solution must do)
designdecomposition into sub-systems; structure diagrams, flowcharts and pseudocode showing how the solution will work
codingwriting the program code, with iterative testing – each module is tested and corrected as it is written
testingtesting the completed program code using test data to make sure it works as required

2Sub-systems and decomposition

Every computer system is made up of sub-systems, which are made up of further sub-systems. Decomposition breaks a problem into its component parts so each can be solved separately: inputs (data entered), processes (calculations and decisions), outputs (results shown or printed) and storage (data kept for later).

Fig. 2Decomposing a library system.

Solutions can be designed and constructed using structure diagrams (the hierarchy of sub-systems), flowcharts (the flow of control through an algorithm) and pseudocode (structured, English-like statements).

Fig. 3Standard flowchart symbols.
Fig. 4A flowchart with a loop.

3The purpose of an algorithm

To explain the purpose of an algorithm, state what it does overall (e.g. "it outputs the total and average of ten marks") and describe the processes involved: the inputs, the loop, what is calculated, what is output.

4Standard methods of solution

Linear search checks each item in a list in turn, from the first, until it finds the item or reaches the end.

DECLARE Names : ARRAY[1:30] OF STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
OUTPUT "Enter the name to find"
INPUT SearchName
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 30 DO
    IF Names[Index] = SearchName
      THEN
        Found ← TRUE
      ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT SearchName, " found at position ", Index
  ELSE
    OUTPUT SearchName, " not found"
ENDIF
Linear search: check each element in turn until the item is found or the end of the list is reached.

Bubble sort compares each pair of neighbouring items and swaps them if they are in the wrong order. After each pass the largest remaining item has "bubbled" to the end. Passes repeat until a pass makes no swaps.

DECLARE Numbers : ARRAY[1:6] OF INTEGER
Top ← 6
REPEAT
    Swap ← FALSE
    FOR Index ← 1 TO Top - 1
        IF Numbers[Index] > Numbers[Index + 1]
          THEN
            Temp ← Numbers[Index]
            Numbers[Index] ← Numbers[Index + 1]
            Numbers[Index + 1] ← Temp
            Swap ← TRUE
        ENDIF
    NEXT Index
    Top ← Top - 1
UNTIL NOT Swap OR Top = 1
Bubble sort into ascending order: compare neighbouring pairs and swap them if they are in the wrong order; repeat passes until no swaps are made.

Totalling adds each value to a running total; counting adds 1 each time something happens. To find the maximum or minimum, keep the largest/smallest so far and compare each value with it. The average is the total divided by the number of values.

Total ← 0
PassCount ← 0
Highest ← Marks[1]
Lowest ← Marks[1]
FOR Index ← 1 TO 30
    Total ← Total + Marks[Index]               // totalling
    IF Marks[Index] >= 50
      THEN
        PassCount ← PassCount + 1              // counting
    ENDIF
    IF Marks[Index] > Highest
      THEN
        Highest ← Marks[Index]                 // maximum
    ENDIF
    IF Marks[Index] < Lowest
      THEN
        Lowest ← Marks[Index]                  // minimum
    ENDIF
NEXT Index
Average ← Total / 30                           // average
OUTPUT "Total ", Total, ", passes ", PassCount
OUTPUT "Highest ", Highest, ", lowest ", Lowest, ", average ", Average
Totalling, counting, maximum, minimum and average for 30 marks stored in an array.

5Validation and verification

Validation is an automatic check by the computer that data entered is reasonable and meets set rules. It is needed because invalid data would give wrong results or make the program fail. Validation cannot tell if data is correct – only that it is sensible.

Validation checkWhat it checksExample
range checka value is between a lower and an upper limitmark from 0 to 100
length checkthe number of characters is exactly, or at least / at most, a given numberpassword at least 8 characters; phone number 11 digits
type checkthe data is of the correct data typeage must be an integer
presence checkdata has been entered (the field is not empty)email address must be filled in
format checkthe data follows a set patterndate as DD/MM/YYYY; postcode format
check digitthe last digit, calculated from the other digits, is correctISBN, barcode
REPEAT
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
    IF Mark < 0 OR Mark > 100
      THEN
        OUTPUT "Invalid mark - please re-enter"
    ENDIF
UNTIL Mark >= 0 AND Mark <= 100
A range check: the input is repeated until the mark is between 0 and 100 inclusive.
REPEAT
    OUTPUT "Enter a password of at least 8 characters"
    INPUT Password
UNTIL LENGTH(Password) >= 8          // length check

REPEAT
    OUTPUT "Enter your name"
    INPUT Name
UNTIL Name <> ""                     // presence check
A length check and a presence check.

Verification checks that data has been accurately copied from one source to another (e.g. from a paper form) or entered as intended. It is needed because typing errors can produce valid but wrong data.

Verification checkHow it works
visual checkthe user reads through the data on screen and compares it with the original document
double entry checkthe data is entered twice (e.g. a new password); the computer compares the two and asks again if they differ
See Topic 2 · Data transmissionCheck digits are covered in 2.2 Methods of error detection.

6Test data

TypeMeaningExample: whole-number mark from 0 to 100
normaldata that should be accepted45, 72
abnormaldata that should be rejected−5, 150, "ten"
extremethe largest/smallest acceptable value0 and 100
boundarythe largest/smallest acceptable value and the corresponding smallest/largest rejected value0 and −1; 100 and 101

7Trace tables

A trace table documents a dry run of an algorithm: working through it by hand, writing down the values of the variables, the outputs and any user prompts at each step. It is used to find the purpose of an algorithm or to find errors.

01 Count ← 0
02 Total ← 0
03 Max ← 0
04 REPEAT
05     INPUT Number
06     Total ← Total + Number
07     IF Number > Max
08       THEN
09         Max ← Number
10     ENDIF
11     Count ← Count + 1
12 UNTIL Count = 4
13 OUTPUT Total, Max
Algorithm to be dry-run with the inputs 5, 9, 3, 7.
Trace table: a value is written each time a variable changes.
NumberCountTotalMaxOUTPUT
000
5155
92149
3317
7424
24, 9

8Finding and correcting errors

01 Total ← 0
02 FOR Count ← 1 TO 10
03     INPUT Number
04     Total ← Number
05 NEXT Count
06 Average ← Total / 9
07 OUTPUT Average
This algorithm should output the average of ten numbers. It contains two errors.

Worked example

Identify the errors

Identify the two errors in the algorithm and suggest corrections.

  1. 1

    Line 04 replaces the total instead of adding to it.

    Total ← Total + Number

  2. 2

    Line 06 divides by the wrong number of values.

    Average ← Total / 10

Answerline 04 and line 06

Common errors: a variable not initialised (or reset inside a loop), the wrong operator (> instead of >=), a loop running the wrong number of times, and the wrong variable output.

9Writing and amending algorithms

Algorithms can be written as pseudocode, program code (Python, Visual Basic or Java) or flowcharts. When amending an algorithm, keep the parts that work, and add or change only the lines needed – e.g. adding validation to an input, or a counter to a loop.

See Topic 8 · ProgrammingThe pseudocode statements are covered in detail in 8.1 Programming concepts.

10Exam focus

Key words: analysis; design; coding; testing; abstraction; decomposition; structure diagram; flowchart; pseudocode; linear search; bubble sort; totalling; counting; validation; verification; normal/abnormal/extreme/boundary data; trace table; dry run.

Quick self-check

Answer in your head first, then reveal.

  1. Analysis (1); design (1); coding (1); testing (1).

  2. 10 and 11, or 18 and 19 (2).

  3. Validation checks data is reasonable/meets rules (1); verification checks data has been copied/entered accurately (1).

  4. Compare neighbouring items (1); swap if in wrong order (1); repeat through the list (1); until a pass with no swaps (1).

  5. Any two: presence; format; range; type (2).

Finished this subtopic? Track it on your subject page.