Fundamentals of algorithms: free AQA GCSE Computer Science practice questions

The mistakes that cost the most marks

These are the mistakes the topic notes single out.

• Using a binary search on unsorted data. It only works on data that is already in order, and saying so is often worth a mark on its own.
• Describing what each line of an algorithm says instead of what the algorithm achieves. Examiners want the purpose in one sentence, such as it finds the largest value in the array.
• Getting the flowchart shapes wrong. A diamond is a decision, a parallelogram is input or output, a rectangle is a process, and an oval is start or stop.
• Assuming a whole list is sorted after one bubble sort pass. Only the largest value is guaranteed to be in its final place.
• Confusing the split in merge sort with the halving in binary search. Merge sort splits every part. Binary search throws one half away.

An algorithm is the method, a program is one version of it

An algorithm is a sequence of steps that solves a problem. A program is that sequence written in a language a computer can run. The same algorithm can be coded in Python, C# or VB.NET and it is still the same algorithm. Two skills sit underneath this. Decomposition breaks a problem into smaller sub-problems that can be solved on their own. Abstraction removes the detail that does not matter so you can concentrate on what does. A timetable app that ignores the colour of each train is using abstraction, because the colour has no bearing on when the train departs.

Three ways to write an algorithm down

Structured English, pseudo-code and flowcharts. Pseudo-code is not a real language and does not have to run. Questions are often set in AQA's pseudo-code, so you need to read it fluently even though you may answer in any clear and sensible format. A flowchart uses fixed shapes joined by arrows, and a decision diamond has one arrow out for each possible answer. Tracing an algorithm, also called a dry run, means working through it by hand and writing each variable's value after every line in a trace table. If the question gives you input values, use exactly those.

Two searches, and when each one works

A linear search checks each item in turn from the start until it finds the target or runs out of items. It works on unordered data. A binary search looks at the middle item and, if that is not the target, throws away the half the target cannot be in. It only works on data that is already sorted. On large lists binary search is much faster, because each comparison halves what is left. A linear search on 1,000 items may need 1,000 comparisons. A binary search needs at most about 10. On a very short list, or on data that would have to be sorted first, a linear search can still win.

Two sorts, and what each one costs

A bubble sort passes through the list repeatedly, comparing neighbouring pairs and swapping them if they are the wrong way round. After the first pass the largest value is in its final place. It can stop early if a whole pass makes no swaps, because that means the list is already sorted. A merge sort splits the list in half over and over until every part holds one item, then merges pairs of parts back together in order. Merge sort is faster than bubble sort on large lists. It needs extra memory to hold the parts while merging, so bubble sort can be preferred when memory is tight and the list is small.

What efficiency means in an exam answer

Efficiency is about how the time or memory an algorithm needs grows as the amount of data grows. It is not about how fast one particular computer is. Two algorithms can produce the same output and still differ in efficiency. When a question asks you to compare them it wants the number of steps or comparisons, not a preference. Standard algorithms are worth memorising as patterns: find the maximum, find the minimum, count how many items match a condition, and total or average an array.