Problem-Solving and Programming: Algorithms

What you'll learn

This revision guide covers the fundamental concepts of algorithms required for Pearson Edexcel International IGCSE Computer Science. You will learn how to design, represent and analyse algorithms using flowcharts, pseudocode and trace tables. The guide also covers essential standard algorithms including linear search, binary search, bubble sort and merge sort that appear regularly in examination questions.

Key terms and definitions

Algorithm — a precise, step-by-step sequence of instructions designed to solve a problem or complete a task

Pseudocode — a structured, English-like notation for writing algorithms that is independent of any programming language

Flowchart — a diagrammatic representation of an algorithm using standardised symbols connected by arrows to show the flow of control

Trace table — a table used to manually track the values of variables as an algorithm executes, line by line

Linear search — a simple searching algorithm that checks each item in a list sequentially until the target is found or the end is reached

Binary search — an efficient searching algorithm that repeatedly divides a sorted list in half to locate a target value

Bubble sort — a simple sorting algorithm that repeatedly steps through a list, comparing adjacent elements and swapping them if they are in the wrong order

Merge sort — an efficient divide-and-conquer sorting algorithm that recursively divides a list into halves, sorts them, then merges the sorted halves

Core concepts

Understanding algorithms

An algorithm is a fundamental concept in computer science. Every program is built from one or more algorithms working together to solve problems.

Key characteristics of a good algorithm:

• Unambiguous — each step must be clear and have only one meaning
• Finite — the algorithm must eventually terminate
• Input — the algorithm receives zero or more inputs
• Output — the algorithm produces at least one output
• Effective — each step must be basic enough to be carried out exactly

Algorithms can be represented in three main ways:

• Written descriptions in natural language
• Flowcharts using standard symbols
• Pseudocode using structured text

Flowchart notation

Flowcharts use standardised symbols to represent different operations. You must recognise and use these symbols correctly in examinations.

Standard flowchart symbols:

• Oval/Rounded rectangle — start/stop (terminator)
• Parallelogram — input/output operations
• Rectangle — process or assignment
• Diamond — decision (yes/no or true/false branch)
• Arrow — flow line showing direction

Flowchart rules:

• Flow lines should not cross
• Use only one flow line into a decision symbol, but two or more leaving it
• All processes should have exactly one entry point and one exit point
• Decisions must be phrased as questions with clear yes/no outcomes

When drawing flowcharts in exams, ensure symbols are large enough to contain text clearly and arrows show direction unambiguously.

Pseudocode conventions

Pseudocode bridges the gap between human language and programming code. The Pearson Edexcel specification uses specific conventions you must follow.

Variable assignment:

total ← 0
count ← count + 1

Input and output:

OUTPUT "Enter your name:"
INPUT name

Selection (IF statements):

IF age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Child"
ENDIF

Iteration (loops):

FOR loop (definite iteration):

FOR counter ← 1 TO 10
    OUTPUT counter
ENDFOR

WHILE loop (indefinite iteration):

WHILE password <> "SECRET" DO
    INPUT password
ENDWHILE

Arrays:

DECLARE scores: ARRAY[1:10] OF INTEGER
scores[5] ← 87

Note that array indices in Edexcel pseudocode can start at 0 or 1 depending on the question context — always check the specification given.

Trace tables

Trace tables track how variables change during algorithm execution. They are essential for dry-running algorithms and finding logic errors.

Structure of a trace table:

• Columns represent variables in the algorithm
• Rows represent each step of execution
• An additional column may track output

How to complete trace tables:

1. Identify all variables used in the algorithm
2. Create a column for each variable
3. Work through the algorithm line by line
4. Record the value of any variable that changes
5. Only write values when they change (leave cells blank if unchanged)
6. Track loop iterations carefully

Trace tables appear frequently in examination questions worth 3-6 marks. Accuracy is essential — one error can cascade through subsequent rows.

Linear search algorithm

Linear search is the simplest searching algorithm. It examines each element in a list sequentially until the target is found.

Characteristics:

• Works on both sorted and unsorted lists
• Time complexity: O(n) — searches all items in worst case
• Inefficient for large datasets
• Best case: item found at first position
• Worst case: item at last position or not in list

Pseudocode implementation:

found ← FALSE
position ← 0

FOR index ← 1 TO length(list)
    IF list[index] = target THEN
        found ← TRUE
        position ← index
    ENDIF
ENDFOR

IF found = TRUE THEN
    OUTPUT "Item found at position ", position
ELSE
    OUTPUT "Item not found"
ENDIF

Binary search algorithm

Binary search is significantly more efficient than linear search but requires a sorted list.

Characteristics:

• Only works on sorted lists
• Time complexity: O(log n) — much faster for large datasets
• Uses divide-and-conquer approach
• Repeatedly halves the search space

How binary search works:

1. Find the middle element of the list
2. If middle element equals target, return position
3. If target is less than middle element, search left half
4. If target is greater than middle element, search right half
5. Repeat until target found or search space is empty

Pseudocode implementation:

found ← FALSE
lower ← 1
upper ← length(list)

WHILE found = FALSE AND lower <= upper DO
    middle ← (lower + upper) DIV 2
    
    IF list[middle] = target THEN
        found ← TRUE
        position ← middle
    ELSE IF list[middle] > target THEN
        upper ← middle - 1
    ELSE
        lower ← middle + 1
    ENDIF
ENDWHILE

Note: DIV represents integer division (discarding remainder).

Bubble sort algorithm

Bubble sort is a simple but inefficient sorting algorithm that repeatedly swaps adjacent elements if they are in wrong order.

Characteristics:

• Time complexity: O(n²) — inefficient for large lists
• Makes multiple passes through the list
• After each pass, largest unsorted element "bubbles" to correct position
• Easy to understand and implement

How bubble sort works:

1. Compare first two elements; swap if in wrong order
2. Move to next pair and repeat
3. Continue to end of list (one pass complete)
4. Repeat passes until no swaps are made

Pseudocode implementation:

n ← length(list)
swapped ← TRUE

WHILE swapped = TRUE DO
    swapped ← FALSE
    FOR i ← 1 TO n - 1
        IF list[i] > list[i + 1] THEN
            temp ← list[i]
            list[i] ← list[i + 1]
            list[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    ENDFOR
    n ← n - 1
ENDWHILE

Merge sort algorithm

Merge sort is an efficient divide-and-conquer sorting algorithm frequently tested at IGCSE level.

Characteristics:

• Time complexity: O(n log n) — much more efficient than bubble sort
• Recursive algorithm (calls itself)
• Divides list into smaller sublists, sorts them, then merges
• Requires additional memory for temporary arrays

How merge sort works:

1. Divide unsorted list into n sublists (each containing one element)
2. Repeatedly merge sublists to produce new sorted sublists
3. Continue until only one sorted list remains

Key stages:

• Divide phase: Split list recursively until single elements remain
• Merge phase: Combine pairs of sorted sublists into larger sorted lists

Students must understand the merge process: comparing first elements of two sorted lists and placing smaller element into merged list, then repeating.

Worked examples

Example 1: Trace table completion (4 marks)

Question: Complete the trace table for the following algorithm:

a ← 5
b ← 10
c ← 0

WHILE a < b DO
    c ← c + a
    a ← a + 2
ENDWHILE

OUTPUT c

Solution:

a	b	c	Output
5	10	0
5	10	5
7	10	5
7	10	12
9	10	12
9	10	21
11	10	21
			21

Mark scheme notes:

• 1 mark for correct initial values
• 1 mark for each complete correct iteration (×2)
• 1 mark for correct final output

Example 2: Binary search trace (5 marks)

Question: A sorted list contains: [3, 7, 12, 18, 24, 31, 45, 52, 67]

Use binary search to find the value 31. Show the values of lower, upper and middle for each iteration.

Solution:

Iteration	Lower	Upper	Middle	list[middle]	Action
1	1	9	5	24	24 < 31, so lower ← 6
2	6	9	7	45	45 > 31, so upper ← 6
3	6	6	6	31	Found

Mark scheme notes:

• 1 mark for correct initial middle calculation
• 1 mark for correct first comparison and adjustment
• 1 mark for correct second middle calculation
• 1 mark for correct second comparison and adjustment
• 1 mark for identifying value found at position 6

Example 3: Algorithm design in pseudocode (6 marks)

Question: Write an algorithm in pseudocode that inputs 10 numbers, calculates their average, and outputs how many numbers were above the average.

Solution:

DECLARE numbers: ARRAY[1:10] OF REAL
total ← 0

FOR i ← 1 TO 10
    INPUT numbers[i]
    total ← total + numbers[i]
ENDFOR

average ← total / 10
count ← 0

FOR i ← 1 TO 10
    IF numbers[i] > average THEN
        count ← count + 1
    ENDIF
ENDFOR

OUTPUT count

Mark scheme notes:

• 1 mark for correct input of 10 numbers
• 1 mark for calculating total correctly
• 1 mark for calculating average
• 1 mark for comparison with average
• 1 mark for counting above-average values
• 1 mark for correct output

Common mistakes and how to avoid them

• Confusing assignment (←) with comparison (=) in pseudocode. Remember: ← stores a value, = tests equality in conditions. Never use = for assignment in Edexcel pseudocode.

• Forgetting ENDIF, ENDFOR, or ENDWHILE keywords. Every IF, FOR and WHILE must have its corresponding END statement. Align them vertically in your answer to check pairing.

• Off-by-one errors in loops and arrays. Check whether arrays start at 0 or 1 in the question. FOR loops are inclusive of both start and end values.

• Incomplete trace tables. Always complete every row, even if a variable doesn't change. Show your working clearly. If a value doesn't change, you can leave the cell blank but ensure the table structure is complete.

• Not checking if binary search list is sorted. Binary search only works on sorted data. If the question doesn't specify the list is sorted, you must state this assumption or use linear search.

• Mixing up searching and sorting algorithms. Linear/binary are searches (find position of item). Bubble/merge are sorts (arrange items in order). Read questions carefully to identify which is required.

Exam technique for "Problem-Solving and Programming: Algorithms"

• Command word precision. "Write an algorithm" requires formal pseudocode or a flowchart. "Describe" needs clear explanations in sentences. "Complete the trace table" requires exact values in each cell. "State" needs brief answers without explanation.

• Show incremental working for trace tables. Examiners award partial marks for correct intermediate steps even if final answer is wrong. Complete each row fully before moving to the next.

• Use the mark allocation as a guide. A 6-mark algorithm question requires approximately 6 distinct features (input, processing, output, loop structure, conditional, variable declaration). Don't write 20 lines for 3 marks or 3 lines for 8 marks.

• Draw flowcharts with a ruler. Neat diagrams score better. Make symbols large enough for clear text. Use standard symbols only — examiners deduct marks for incorrect notation.

Quick revision summary

Algorithms are step-by-step instructions that solve problems. Represent them using flowcharts (with standard symbols), pseudocode (using Edexcel conventions with ←, IF...ENDIF, FOR...ENDFOR, WHILE...ENDWHILE), or natural language. Use trace tables to manually execute algorithms and track variable values. Master four key algorithms: linear search (sequential checking), binary search (halving sorted lists), bubble sort (swapping adjacent pairs), and merge sort (divide-and-conquer approach). Binary search and merge sort are significantly more efficient for large datasets than their alternatives.