Algorithm Design and Problem-Solving

What you'll learn

Algorithm design and problem-solving is about planning solutions before writing code. This overview draws together that unit of CIE IGCSE Computer Science (0478): the program development life cycle (analysis, design, coding and testing), computer systems and sub-systems, decomposition, methods of representing algorithms — structure diagrams, flowcharts and pseudocode — the standard methods of solution (totalling, counting, finding maximum, minimum and average, linear search and bubble sort), validation and verification, test data, trace tables, and how to identify and correct errors in algorithms. The sub-topic guides on pseudocode, flowcharts and searching and sorting go into further detail.

This unit is assessed heavily on Paper 2, including the scenario question where you design and write an algorithm. You will be asked to complete trace tables, find errors, write pseudocode and explain the purpose of an algorithm.

Key terms and definitions

Algorithm — A sequence of steps designed to perform a task or solve a problem.

Program development life cycle — The stages of developing a program: analysis, design, coding and testing.

Abstraction — Removing unnecessary details to focus on what is important.

Decomposition — Breaking a problem down into smaller parts that are easier to solve.

Structure diagram — A hierarchical diagram showing how a system is broken down into sub-systems.

Flowchart — A diagram using standard symbols to show the steps of an algorithm.

Pseudocode — A structured, language-independent way of writing an algorithm.

Validation — An automated check that data is reasonable before it is accepted.

Verification — Checking that data has been accurately copied or entered.

Trace table — A table recording the values of variables as an algorithm runs, used to test it.

Normal, abnormal, extreme and boundary data — Types of test data used to check a program.

Core concepts

The program development life cycle

1. Analysis — understand the problem using abstraction and decomposition; identify the requirements.
2. Design — plan the solution with structure diagrams, flowcharts and pseudocode.
3. Coding — write the program in a programming language, with iterative testing of each module.
4. Testing — test the complete program with suitable test data to check it meets the requirements.

Systems, sub-systems and decomposition

Every computer system can be broken into sub-systems, each of which can be broken down further until each part performs a single task. A structure diagram shows this hierarchy. When decomposing a problem, identify its inputs, processes, outputs and storage.

Representing algorithms

Flowcharts use:

• a terminator (rounded rectangle) for START and STOP;
• a parallelogram for INPUT and OUTPUT;
• a rectangle for a process;
• a diamond for a decision with two exits (Yes/No);
• a rectangle with extra vertical lines for a pre-defined process (sub-routine);
• arrows (flow lines) to show the order.

Pseudocode in CIE style uses ← for assignment, INPUT, OUTPUT, IF … THEN … ELSE … ENDIF, CASE OF … OTHERWISE … ENDCASE, FOR … TO … NEXT, WHILE … DO … ENDWHILE and REPEAT … UNTIL. Keywords are in capitals and identifiers should be meaningful.

Standard methods of solution

Totalling:

Total ← 0
FOR Count ← 1 TO 10
    INPUT Mark
    Total ← Total + Mark
NEXT Count

Counting:

PassCount ← 0
...
IF Mark >= 50 THEN
    PassCount ← PassCount + 1
ENDIF

Maximum, minimum and average:

Max ← -1
Min ← 101
Total ← 0
FOR Count ← 1 TO 30
    INPUT Mark
    IF Mark > Max THEN Max ← Mark ENDIF
    IF Mark < Min THEN Min ← Mark ENDIF
    Total ← Total + Mark
NEXT Count
Average ← Total / 30

Initialise Max to a value lower than any possible input and Min to a value higher, or set both to the first value entered.

Linear search checks each item in turn until the target is found or the list ends:

Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 10 DO
    IF Names[Index] = SearchName THEN
        Found ← TRUE
    ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE

Bubble sort compares adjacent items and swaps them if they are in the wrong order, repeating passes until a pass makes no swaps. Using a flag (Swapped) lets the algorithm stop early when the list is sorted.

Validation and verification

Validation checks that data is reasonable before it is accepted:

• range check — between limits;
• length check — correct number of characters;
• type check — correct data type;
• presence check — not left blank;
• format check — matches a pattern;
• check digit — a calculated final digit detects errors in codes.

Verification checks that data has been copied or entered accurately:

• double entry — data entered twice and compared;
• visual check — the user compares the entry with the original.

Test data

• Normal data — valid data the program should accept and process.
• Abnormal (erroneous) data — data that should be rejected.
• Extreme data — the largest and smallest acceptable values.
• Boundary data — values on each side of a limit: the largest/smallest acceptable value and the corresponding value just outside.

For marks from 0 to 100: normal 56; abnormal −5 or "fifty"; extreme 0 and 100; boundary 0 and −1, 100 and 101.

Trace tables and errors

A trace table has a column for each variable and for output, and records how values change as the algorithm runs with given test data. It is used to check that an algorithm works and to find logic errors, where the algorithm runs but produces the wrong result (for example, using < instead of <=, initialising a total inside a loop, or using the wrong variable). You may be asked to identify the error, state its line and give the correction.

Bubble sort in pseudocode

This version sorts an array of ten numbers into ascending order and stops as soon as a pass makes no swaps:

DECLARE Numbers : ARRAY[1:10] OF INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Temp, Index, Last : INTEGER
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

Three points are commonly tested: the temporary variable (Temp) is needed so that a value is not lost during a swap; the Swapped flag lets the algorithm stop early when the list is already sorted; and reducing Last after each pass avoids comparing items already in their final position.

From flowchart to pseudocode and back

You may be given an algorithm as a flowchart and asked to rewrite it in pseudocode, or the reverse. Map each symbol to a statement: a parallelogram becomes INPUT or OUTPUT, a rectangle becomes an assignment, and a diamond becomes IF or the condition of a loop. A decision whose arrow loops back up the flowchart represents iteration: if the check happens before the repeated steps, use WHILE; if it happens after them, use REPEAT … UNTIL.

Explaining the purpose of an algorithm

A common question shows an algorithm and asks what it does. Trace it with simple test data, then describe the overall effect in one sentence — for example, "it finds and outputs the largest of the numbers entered" — rather than restating each line.

Worked examples

Example 1: Trace table

Complete a trace table for this algorithm with inputs 4, 9, 2.

Max ← 0
FOR Count ← 1 TO 3
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

Example 2: Finding an error

This algorithm should total ten numbers but outputs only the last one. Identify and correct the error.

FOR Count ← 1 TO 10
    Total ← 0
    INPUT Num
    Total ← Total + Num
NEXT Count
OUTPUT Total

Answer: Total ← 0 is inside the loop, so the total is reset every time. Move Total ← 0 to before the FOR loop.

Example 3: Writing validation

Write pseudocode to input an age and reject it until it is between 11 and 18.

REPEAT
    OUTPUT "Enter age 11 to 18"
    INPUT Age
UNTIL Age >= 11 AND Age <= 18

Example 4: Test data

A program accepts whole numbers from 1 to 20. Give boundary test data.

Answer: 1 and 0; 20 and 21.

Common mistakes and how to avoid them

• Initialising totals or counters inside a loop.
• Using = instead of ← for assignment in CIE pseudocode. = is used for comparison.
• Confusing validation and verification.
• Muddling extreme and boundary data. Extreme = largest/smallest valid; boundary = either side of a limit.
• Missing ENDIF, NEXT or ENDWHILE.
• Starting Max at a value that could be larger than real data.

Exam technique for "Algorithm Design and Problem-Solving"

• Use CIE pseudocode conventions consistently and indent your code.
• For the scenario question, break the task down, declare and initialise variables, use meaningful names, include validation, and output results with messages.
• In trace tables, write each new value on a new row in the order it changes.
• When identifying errors, give the line, the error and the correction.

Quick revision summary

• Life cycle: analysis (abstraction, decomposition), design, coding, testing.
• Represent algorithms with structure diagrams, flowcharts and pseudocode.
• Standard methods: totalling, counting, max/min/average, linear search, bubble sort.
• Validation: range, length, type, presence, format, check digit. Verification: double entry, visual check.
• Test data: normal, abnormal, extreme, boundary.
• Trace tables find logic errors; correct them by line.