Computational Thinking
What AQA means by an algorithm, why a program is not the same thing, and how decomposition and abstraction turn a problem you cannot see the end of into one you can actually code.
Algorithms and programs
AQA defines an algorithm as a sequence of steps that can be followed to complete a task. Learn that wording. Mark schemes accept "sequence of steps" and are far less generous with vaguer phrases such as "instructions for a computer".
Two consequences follow from that definition, and both get examined.
An algorithm does not have to involve a computer. A recipe is an algorithm. The instructions for changing a tyre are an algorithm. What makes something an algorithm is that the steps are unambiguous, they are in a definite order, and following them eventually finishes.
A computer program is an implementation of an algorithm. The algorithm is the method. The program is that method written down in a language a machine can run. The same algorithm can be implemented in Python, in C#, in VB.NET, or drawn as a flowchart, and it is still the same algorithm.
An algorithm is the method. A program is one implementation of that method in a particular programming language. Getting this the wrong way round costs a mark in one of the easiest questions on the paper.
Why this matters when you are actually coding
If you design the algorithm first you can check it works before writing a line of code. Tracing a plan on paper takes two minutes. Debugging an unplanned program takes an afternoon, because you end up guessing at what the code was supposed to do at the same time as working out what it actually does.
This is also why AQA can set a question that says "write an algorithm" and accept pseudo-code, program code or a flowchart. It is testing whether you can produce the method, not whether you can remember Python punctuation.
- Decomposition: break a big problem into small parts you can solve one at a time.
- Abstraction: keep what matters and hide the detail you do not need.
- Pattern recognition: spot what repeats, so one solution can be reused.
- Algorithms: put the solution in clear steps that a computer, or anyone, can follow.
Decomposition
Decomposition means breaking a problem down into smaller, more manageable sub problems, each of which is easier to solve than the whole.
Take "write a quiz game". As a single instruction that is unusable. Nobody can sit down and write a quiz game, because "quiz game" is not a task, it is a category. Decomposed, it becomes a list of things you could each do in twenty minutes:
- Load the questions from a file
- Pick a question that has not been asked yet
- Display the question and the four options
- Read the player's answer
- Check the answer against the correct one
- Update the score
- Repeat until the questions run out
- Display the final score and save the high score
Why decomposition earns marks
You must be able to say what it gives you, not just what it is. There are four standard benefits and any of them can be credited:
- Each sub problem is simpler, so it can be solved and tested on its own.
- Work can be split between programmers, because different people can take different sub problems at the same time.
- Errors are easier to find, because a fault shows up inside one small routine rather than somewhere in a thousand lines.
- Sub problems can be reused, since a routine that loads a file of questions will load a file of anything.
That sentence alone is one mark. The second mark comes from saying what the smaller parts let you do: solve, test, reuse or share them out.
Decomposition maps directly onto subroutines in code. Each sub problem in the list above becomes a procedure or a function, which is exactly why structured programming and decomposition are examined as the same idea in different clothes.
- Start with the whole problem at the top.
- Split it into a few main parts.
- Keep splitting until every part is small enough to solve.
- Why bother: parts can be built in parallel, tested separately and reused.
Abstraction
Abstraction means removing unnecessary detail from a problem so that only the parts needed to solve it remain.
The classic example is the London Underground map. It is geographically wrong: the distances are invented, the lines are straightened, and the river is a rough blue ribbon. All of that is deliberate. A passenger only needs to know which stations are on which line and where the lines cross. Everything else is detail that would make the map harder to use, so it is thrown away.
Abstraction in a program
Suppose you are writing a program that works out bus fares. The real world facts about a passenger include their name, hair colour, shoe size, favourite band, home address and age. For the fare calculation you need the age, the zones travelled and whether they hold a pass. Everything else is discarded. That decision is abstraction.
Abstraction is the process of removing or hiding unnecessary detail so that only the information required to solve the problem remains.
Why it is worth doing
- The program is simpler to write, because there is less to represent.
- It runs faster and uses less memory, because less data is stored and processed.
- It is easier to understand and maintain, because the code only mentions things that matter.
- It makes the solution more general, so the same fare model works for a different city.
Decomposition splits a problem into parts. Abstraction throws detail away. A question that asks for both wants two clearly different answers, and the marker will not give the same point twice.
If a question shows a scenario and asks you to give an example of abstraction, name a specific detail that has been left out and say why it does not matter. "The map does not show the real distance between stations because a passenger only needs to know the order of the stops" is a full answer. "It removes detail" is not.
Step 1 of 3 Decomposition: break the problem into parts small enough to solve one at a time.
- The real thing is full of detail: most of it is no use for the job in hand.
- The abstraction is a simple model that keeps only what the job needs.
- What stays: the stations, what connects to what, and the lines.
- What goes: the detail that does not help, such as houses, exact distances and street names.
Key terms you must be able to define
- Algorithm
- A sequence of steps that can be followed to complete a task.
- Program
- An implementation of an algorithm written in a programming language so that a computer can run it.
- Decomposition
- Breaking a problem down into smaller sub problems, each of which is easier to solve.
- Abstraction
- Removing unnecessary detail from a problem so that only the information needed to solve it remains.
- Sub problem
- One of the smaller, self contained tasks produced by decomposing a larger problem.
- Computational thinking
- The approach of solving problems using decomposition, abstraction and algorithmic thinking.
- Algorithmic thinking
- Working out the sequence of steps needed to solve a problem so that the method can be repeated reliably.
- Unambiguous
- Having only one possible meaning, which is why every step of an algorithm must be written precisely.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
This topic looks easy and is marked strictly, which is why it separates candidates.
Use AQA's definitions word for word. "A sequence of steps that can be followed to complete a task" is worth learning by heart. Paraphrasing it into "a set of rules a computer follows" loses the mark because it smuggles in the computer, which is not part of the definition.
Always give the benefit as well as the definition. Almost every question on this topic is worth two or three marks, and the extra marks are for consequences: easier to test, quicker to find errors, work can be shared, code can be reused, less memory used.
Tie the answer to the scenario in the question. If the scenario is a hospital appointment system, your abstraction example must be about appointments, not about tube maps. Generic examples that ignore the stem are the single most common reason a three mark answer scores one.
- State AQA's definition of an algorithm from memory in one sentence
- Explain the difference between an algorithm and a program without hesitating
- Give three distinct benefits of decomposition
- Give a scenario specific example of abstraction that names the detail removed and says why it can be removed
Mistakes that cost marks here
- Defining an algorithm as 'instructions for a computer'. The definition is a sequence of steps to complete a task, and it need not involve a computer at all.
- Saying a program and an algorithm are the same thing. The program is one implementation of the algorithm.
- Confusing abstraction with decomposition. Abstraction removes detail, decomposition splits the problem up.
- Giving the tube map as an abstraction example when the question is about a completely different scenario, so none of the detail relates to the stem.
- Stating a definition and stopping, when the question is worth three marks and the other two are for benefits.
The word algorithm comes from al-Khwarizmi, a ninth century scholar working in Baghdad. When his book on Indian numerals was translated into Latin the translator wrote his name as 'Algoritmi', and the word stuck to the methods rather than the man.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LA sequence of steps that can be followed to complete a task
An algorithm is a sequence of steps that can be followed to complete a task.
- LAn algorithm is the method or sequence of steps for solving the problem
- LA program is an implementation of that algorithm in a programming language
An algorithm is the method itself: the sequence of steps that solves the problem, which can be written as pseudo-code, as a flowchart or in plain English. A computer program is an implementation of that algorithm in a particular programming language, so that a computer can actually execute it. The same algorithm can therefore be implemented as many different programs.
- LThe problem is broken down into smaller sub problems
- LEach sub problem is simpler and can be solved on its own
- LDifferent programmers can work on different sub problems at the same time
- LEach part can be tested separately so errors are easier to locate
Decomposition means breaking the supermarket system down into smaller sub problems such as searching the product catalogue, managing the basket, taking payment and booking a delivery slot. Each of those sub problems is far simpler than the whole system, so a programmer can understand it, solve it and finish it without holding the entire project in their head. Because the sub problems are independent, different members of the team can work on different parts at the same time, which shortens development. Each part can also be tested on its own, so when something fails the fault is known to lie inside one small routine rather than anywhere in the finished system.
- LAbstraction is removing or hiding unnecessary detail
- LOnly the information needed to solve the problem is kept
- LA valid example is given, such as a tube map keeping station order but discarding real distances
Abstraction is the process of removing unnecessary detail from a problem so that only the information needed to solve it remains. For example, the London Underground map is not drawn to scale and shows none of the real geography above ground, because a passenger only needs to know which stations lie on which line and where the lines cross. Removing the rest makes the map far quicker to read, and in the same way removing irrelevant data from a program makes it simpler to write and less demanding on memory.
- LDecomposition breaks a problem into smaller sub problems
- LAbstraction removes detail that is not needed
- LThey are different processes that can both be applied to the same problem
The student is wrong because the two techniques do different jobs. Decomposition takes one large problem and breaks it into smaller sub problems, each of which can be solved, tested and reused on its own, so the size of the problem changes but the detail does not. Abstraction leaves the problem whole but strips out the detail that is not needed to solve it, so that only relevant information is represented. Both techniques are usually applied to the same project, and a good solution will decompose the system into subroutines while abstracting away the data that has no bearing on the result.