Algorithms: OxfordAQA IGCSE Computer Science Complete Notes

Why algorithms come first in the specification

Everything else in oxfordaqa igcse computer science algorithms work builds on one idea: a computer program is only an implementation of a plan, and the plan itself is the algorithm. Get comfortable separating the plan from the code that carries it out, and the rest of the programming paper becomes far more manageable. This guide works through representing algorithms, judging their efficiency, and the two pairs of algorithms named explicitly in the specification: linear and binary search, and merge sort and bubble sort. Anyone searching for algorithms oxfordaqa igcse revision will find those four named algorithms are exactly the ones worth mastering first.

Representing algorithms

An algorithm is a sequence of steps that can be followed to complete a task. It is not the same thing as a computer program; the algorithm is the reasoning, the program is one particular expression of that reasoning in a specific language. Two ideas sit underneath every algorithm you will be asked to build or interpret: decomposition and abstraction.

• Decomposition means breaking a problem into a number of sub-problems, each of which accomplishes an identifiable task and which might itself be broken down further. If you are asked to design a program that manages a class register, decomposition might split the task into reading names in, checking attendance, and producing a summary.
• Abstraction means removing unnecessary detail from a problem so that only what matters to the solution remains. A route-planning algorithm does not need to know the colour of the roads; it needs distances and connections.

Algorithms are represented in two forms on this course: pseudocode and flowcharts. Any exam question that gives you pseudocode will use the Oxford International AQA standard version, so it pays to practise reading that exact style until it feels familiar, even if you personally code in Python or another language day to day. When you write your own pseudocode, you have more freedom; any form is acceptable as long as the meaning is clear and unambiguous. You should also be able to look at a short algorithm and identify where the inputs, the processing and the outputs happen, and be able to work out the algorithm's overall purpose using a trace table or careful visual inspection.

Worked example: tracing a simple algorithm

Consider this pseudocode:

total ← 0
FOR i ← 1 TO 5
  INPUT number
  total ← total + number
ENDFOR
average ← total / 5
OUTPUT average

The input happens at the INPUT statement inside the loop; the processing is the running total being built up across five iterations; the output is the final average. A trace table with columns for i, number, total and average, filled in row by row for each pass of the loop, is the fastest way to confirm what this algorithm actually does and to catch any error in your own reasoning before you commit it to code.

Efficiency of algorithms

More than one algorithm can solve the same problem, and part of thinking like a computer scientist is recognising that some solutions are meaningfully better than others. On this course, formal comparisons of algorithmic efficiency using notation are not required; exam questions in this area only refer to time efficiency in plain terms, such as which algorithm would typically complete faster on a large data set, and why. Being able to explain in prose why one approach does noticeably less work than another, for example why checking every item one by one is slower on a large sorted list than repeatedly halving the search space, is exactly the level of reasoning expected here.

Searching algorithms

Two searching algorithms are named on the specification, and you need to know both well enough to write pseudocode for them and to compare their advantages and disadvantages.

Linear search

Linear search checks each item in a list, one after another, starting from the first, until it finds the target value or reaches the end of the list. It works on any list, sorted or not, which is its main advantage. Its disadvantage is that on a long list, it can require checking every single item before concluding that a value is not present.

Binary search

Binary search only works on a list that is already sorted. It repeatedly looks at the middle item of the remaining section of the list: if that item is the target, the search is done; if the target is smaller, the search continues in the lower half; if the target is larger, the search continues in the upper half. This halving is what makes binary search dramatically faster than linear search on a large sorted list. You should know the mechanics of the iterative version of this algorithm well enough to follow it step by step and to write pseudocode for it, since exam questions frequently ask for exactly that.

Sorting algorithms

The specification names two sorting algorithms: merge sort and bubble sort, and again asks you to compare them.

Merge sort

Merge sort is a recursive algorithm: it repeatedly splits a list in half until each piece contains a single item, and then merges those pieces back together in the correct order, comparing items as it goes. You are expected to know the mechanics of the recursive version and to be able to demonstrate how a merge sort would be carried out on a given set of data, but it is sufficient to explain the algorithm in prose; you will not be asked to write pseudocode for it. Practise demonstrating a merge sort on a short list of six to eight numbers by hand, splitting and merging step by step, until the pattern is second nature.

Bubble sort

Bubble sort repeatedly steps through a list, compares each pair of adjacent items, and swaps them if they are in the wrong order. On this course you are expected to know the version built from two nested loops, where the outer loop is controlled indefinitely by a condition that checks whether any swaps were made on the previous pass, and the inner loop is controlled definitely, running through the list once per pass. You should be able to follow and write pseudocode for bubble sort, so this is one worth practising by hand until you can produce it without hesitation.

Comparing the two

Bubble sort is simple to understand and simple to code, which is its main strength, but it does a lot of unnecessary comparison work on a large or nearly-sorted list. Merge sort is more efficient on larger data sets because it consistently splits the problem down, but it is conceptually harder to trace by hand and requires extra memory to hold the split lists during merging. A strong exam answer states both the strength and the corresponding weakness for each algorithm rather than only listing one side.

Common mistakes to avoid

A frequent error is muddling decomposition and abstraction; remember decomposition splits a problem into parts, abstraction strips away irrelevant detail from within a part. On searching, students sometimes describe binary search without stating clearly that the list must be sorted first, which loses an easy mark. On sorting, a common slip is describing bubble sort's inner loop as indefinite when it is the outer loop, driven by the swap-check, that is indefinite; get that pairing the right way round.

How the two search algorithms actually compare in practice

It helps to picture both algorithms working on the same sorted list of one hundred numbers. Linear search, in the worst case, checks all one hundred numbers before it can conclude a value is absent, because it has no way of skipping ahead. Binary search reaches the same conclusion in only a handful of comparisons, because each check eliminates roughly half of what remains. That gap grows dramatically as the list gets longer, which is exactly the kind of time-efficiency reasoning the specification expects you to be able to describe in words. The trade-off is that binary search only works because the data is already sorted; if the list were shuffled first, you would either need to sort it, which costs time of its own, or fall back to linear search. A well-built exam answer states this trade-off explicitly rather than simply asserting that binary search is always the better choice.

The same kind of reasoning applies to merge sort against bubble sort. Bubble sort's nested-loop structure means that on a list that is already nearly sorted, it can finish quickly because few swaps are needed and the outer loop's swap-check ends the process early. On a list sorted in the opposite order, however, bubble sort does a large amount of repeated comparison and swapping work. Merge sort's recursive splitting behaves far more consistently regardless of how the input is initially ordered, which is why it tends to be preferred for larger or more unpredictable data sets, at the cost of being harder to trace by hand and needing extra memory while lists are merged back together.

Self-check questions

1. Explain the difference between an algorithm and a computer program, using an example.
2. Write pseudocode for a linear search that returns the position of a target value in a list, or minus one if it is not found.
3. Write pseudocode for a binary search over a sorted list of integers.
4. Describe, in prose, how merge sort would process the list 8, 3, 5, 1.
5. Write pseudocode for bubble sort using the nested loop structure described in the specification.
6. State one advantage and one disadvantage of bubble sort compared with merge sort.

These oxfordaqa igcse computer science revision notes on algorithms are designed to be worked through actively rather than read passively: trace every example by hand before checking your answer against the explanation above. Practising like this is what turns a topic you have merely read about into one you can perform confidently under exam conditions, which is exactly what a set of oxfordaqa igcse computer science notes ought to achieve.

Where algorithms sit in the wider course

Once representing, comparing, searching and sorting algorithms feel solid, the natural next step is the broader programming topic guide, where these same ideas of decomposition, iteration and correctness get applied to full programs with data structures and file handling. Consider this page your igcse 9210 algorithms reference to return to whenever a trace table or a piece of pseudocode needs checking, and pair it with timed oxfordaqa igcse computer science practice questions so the theory here converts into speed and accuracy on the day. This is oxfordaqa igcse computer science explained the way it needs to be for the exam: every rule tied to a worked example rather than left as an abstract statement, so the next step is simply repetition.