Algorithm design and problem-solving

Cambridge IGCSE Computer Science 0478 · Paper 2 · Topic 7

The heart of Paper 2: trace tables, standard algorithms, validation and test data, and writing pseudocode all come from this unit.

1. The program development life cycle

Stage	What happens
Analysis	Identify the problem and its requirements. Use abstraction (keep only the important details) and decomposition (break the problem into smaller parts)
Design	Plan the solution using decomposition, structure diagrams, flowcharts and pseudocode
Coding	Write the program code, testing each part as it is written (iterative testing)
Testing	Test the finished program with test data to check it works as required

2. Systems and decomposition

Every computer system is made up of sub-systems, which are made up of further sub-systems. Decomposing a problem means breaking it into its component parts: inputs, processes, outputs and storage.

A structure diagram breaks a system into sub-systems, and those into further sub-systems.

3. Flowcharts

Use these standard symbols; arrows show the direction of flow.

Every flowchart starts and ends with a terminator. A decision box has two exits, labelled Yes and No.

4. Pseudocode

Pseudocode in the exam follows Cambridge’s format: keywords in capitals, ← for assignment, and THEN and ELSE indented by two spaces. Be precise: write x > y, not “x is greater than y”.

DECLARE Mark : INTEGER
CONSTANT PassMark ← 50
INPUT Mark
IF Mark >= PassMark
  THEN
    OUTPUT "Pass"
  ELSE
    OUTPUT "Fail"
ENDIF

FOR Index ← 1 TO 10          // count-controlled loop
  OUTPUT Index
NEXT Index

WHILE Mark < 0 DO            // pre-condition loop
  INPUT Mark
ENDWHILE

REPEAT                       // post-condition loop
  INPUT Mark
UNTIL Mark >= 0

5. Totalling, counting, max, min and average

These standard methods come up again and again. Learn the pattern, especially how each variable is initialised.

Total ← 0
Count ← 0
Max ← -1
Min ← 101
FOR Index ← 1 TO 10
  INPUT Mark
  Total ← Total + Mark            // totalling
  IF Mark >= 50
    THEN
      Count ← Count + 1           // counting
  ENDIF
  IF Mark > Max
    THEN
      Max ← Mark                  // maximum
  ENDIF
  IF Mark < Min
    THEN
      Min ← Mark                  // minimum
  ENDIF
NEXT Index
Average ← Total / 10              // average
OUTPUT "Average: ", Average, " Highest: ", Max, " Lowest: ", Min, " Passed: ", Count

Max starts lower than any possible value and Min starts higher than any possible value, so the first mark always replaces them.

6. Linear search

A linear search checks each item in a list in turn until the item is found or the end of the list is reached.

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

7. Bubble sort

A bubble sort compares each pair of neighbouring items and swaps them if they are in the wrong order. After each pass the largest unsorted item is in its final place. It stops when a pass makes no swaps.

Last ← 10
REPEAT
  Swapped ← FALSE
  FOR Index ← 1 TO Last - 1
    IF Numbers[Index] > Numbers[Index + 1]
      THEN
        Temp ← Numbers[Index]
        Numbers[Index] ← Numbers[Index + 1]
        Numbers[Index + 1] ← Temp
        Swapped ← TRUE
    ENDIF
  NEXT Index
  Last ← Last - 1
UNTIL Swapped = FALSE OR Last <= 1

Try it: bubble sort

Each step compares two neighbours and swaps them if they are in the wrong order.

8. Validation and verification

Validation checks that input data is sensible and reasonable. Verification checks that data has been copied or entered accurately.

Validation check	Example
Range check	A mark must be between 0 and 100
Length check	A password must have at least 8 characters
Type check	Age must be an integer
Presence check	The name field must not be empty
Format check	A date must be in the form DD/MM/YYYY
Check digit	The last digit of a barcode is calculated from the others

Verification check	How it works
Visual check	The user looks at the data on screen and compares it with the original
Double entry check	The data is entered twice and the two entries are compared

REPEAT
  INPUT Age
  IF Age < 11 OR Age > 18
    THEN
      OUTPUT "Age must be from 11 to 18. Please try again."
  ENDIF
UNTIL Age >= 11 AND Age <= 18

9. Test data

Type	Meaning	Example for 1–100
Normal	Data that should be accepted	50
Abnormal	Data that should be rejected	-5, 150, "ten"
Extreme	The largest and smallest acceptable values	1 and 100
Boundary	The largest and smallest acceptable values and the values just outside them that should be rejected	0, 1, 100 and 101

Try it: what type of test data is it?

A program accepts whole numbers from 1 to 100. Type a value to test.

10. Trace tables

A trace table records the value of each variable, and any output or user prompt, at each step of a dry run. Add a new row whenever a value changes, and work line by line; don't skip ahead.

Try it: complete a trace table

The inputs are 7, 12, 5, 12. Step through the algorithm and watch the trace table fill in.

11. Finding and correcting errors

This algorithm should output the highest of 20 positive numbers, but it has two errors.

// Should output the highest of 20 positive numbers
Max ← 1000                       // error 1
FOR Index ← 1 TO 20
  INPUT Number
  IF Number < Max                // error 2
    THEN
      Max ← Number
  ENDIF
NEXT Index
OUTPUT Max

Error 1: Max ← 1000 starts too high, so no number will replace it. Correct to Max ← 0 (or the first number input).
Error 2: Number < Max finds the smallest. Correct to Number > Max.

12. Examiner tips

Initialise variables before a loop: totals and counters to 0.
Be precise in pseudocode: use operators (>, <=), not words.
Use the right loop: FOR for a known number of repeats; WHILE or REPEAT when it depends on a condition.
Trace tables: fill in every change in order, including outputs and prompts.
Boundary data includes the rejected values just outside the range.
Validation is not verification. Validation checks data is sensible; verification checks it was entered correctly.
When stating an algorithm's purpose, say what it does overall, not line by line.
Close every structure: ENDIF, NEXT, ENDWHILE, UNTIL.

13. Practice questions

Practice: answer and check instantly

Type a short answer, then press Check or Enter.

1. At which stage of the life cycle are the problem and its requirements identified?

Show answer

Analysis.

2. Which flowchart symbol is used for a decision?

Show answer

A diamond.

3. Which validation check makes sure a mark is between 0 and 100?

Show answer

A range check.

4. Which verification check enters the data twice and compares the entries?

Show answer

A double entry check.

5. A program accepts 1 to 100. What type of test data is 100?

Show answer

Extreme (it is also boundary data).

6. Which standard method checks each item in turn until it finds a value?

Show answer

A linear search.

7. Give the list after the first pass of a bubble sort on 4 2 3 1.

Show answer

2 3 1 4: the 4 moves to the end.

8. What is output? Total ← 0, then FOR i ← 1 TO 3, Total ← Total + i, NEXT i, then OUTPUT Total.

Show answer

6 = 1 + 2 + 3.

Exam-style questions

9. Write an algorithm in pseudocode to input 10 positive numbers and output the average and the largest number. [6]

Show mark guide

Total ← 0 and Max ← 0 initialised [1] · FOR loop from 1 to 10 [1] · INPUT the number inside the loop [1] · Total ← Total + Number [1] · IF Number > Max THEN Max ← Number [1] · Average ← Total / 10 and OUTPUT Average and Max after the loop [1].

10. A program accepts ages from 11 to 18. Give one example each of normal, extreme and boundary test data, and one abnormal value. [4]

Show mark guide

Normal: any of 12–17, e.g. 15 [1] · Extreme: 11 or 18 [1] · Boundary: 10 or 19 (or 11/18) [1] · Abnormal: e.g. -3, 50 or "fifteen" [1].

14. Topic test: predict your grade

Frequently asked questions

What is a trace table?

A trace table records the values of variables and outputs as you follow an algorithm step by step. It is used to test algorithms and find logic errors.

What are the stages of the program development life cycle?

The stages are analysis, design, coding and testing. Analysis uses abstraction and decomposition, and design uses flowcharts, structure diagrams and pseudocode.

What is the difference between validation and verification?

Validation checks that data is sensible and follows rules, such as a range check. Verification checks that data has been entered or copied accurately, such as double entry.