Algorithms
Computational Thinking
Contents
Computational thinking is a set of techniques for tackling a problem in a structured way, so you can produce a solution clear enough for a person or a machine to follow. It does not mean thinking like a computer: the same approach helps when you are the one following the plan, such as organising a school fundraiser.
The three principles
There are three principles, and they work as a set. Each one does a different job on the problem.
| Principle | What it does to the problem |
|---|---|
| Abstraction | Keeps the details the solution needs and ignores the rest |
| Decomposition | Splits the problem into smaller parts that can each be solved |
| Algorithmic thinking | Works out the precise steps of the solution and the order they go in |
The three are used together to define a problem and then to refine the solution. Defining means pinning down exactly what has to be solved; refining means improving the solution once you can see how it would work in practice.
Using them together
Suppose you are writing a program that works out what each pupil owes for a school camping trip. You start by deciding which details actually affect the answer, then deal with each part separately, then set out the steps in order: read the number of nights, multiply by the cost per night, add any extras, display the price.
Going through the steps in order often shows up a gap. Here you notice a one-off deposit is charged per pupil, so you go back, keep that extra detail and split the pricing part again into the nights and the deposit. A programmer may move between the three principles several times while working on the same problem, which is why they are described as a set of techniques rather than three separate stages that are each finished once.
Decomposition means taking one large, complex problem and dividing it into smaller problems that can be handled separately. Instead of keeping a huge job in your head, you deal with a set of small jobs and then combine their solutions.
Imagine you are asked to write a program for a bike-hire scheme at a country park. It has to keep track of the bikes, hire them out, charge customers and report on the day, which is a lot to design in one go, so you decompose it into sub-problems:
- store the details of each bike
- hire a bike out to a customer
- work out the cost of a hire
- record a bike being returned
- print a summary of the day's hires
Each of these is a smaller problem that can be solved separately, and solving all five and putting the results together solves the whole problem.
Breaking a sub-problem down again
If a sub-problem is still too big, decompose it again. Working out the cost of a hire could become: find how many hours the bike was out, multiply that by the hourly rate, then take off the member discount if the customer has a membership number. Keep going until no piece feels too large to handle alone. A useful test is that you can list the steps for that piece without needing to know how any other part of the program works.
Combining the parts
Decomposition is not finished once the parts are solved, because they must fit together into one working program. The part that hires a bike out needs the stored bike details, and the summary needs the records of each hire, so you have to decide what information passes between the parts.
A description of someone dividing a job into separate pieces that can each be solved on their own and then put back together is describing decomposition. It is more than listing the sections of a program that already exists.
Decomposition breaks a problem into smaller sub-problems, and the benefits come from those parts: one huge problem is hard to hold in your head, while several small ones are manageable.
Each sub-problem is simpler to understand, write and test. You concentrate on one small job at a time: in a cinema booking program, getting the seat prices right is something you can finish and check before you touch anything else.
Different people can work on different sub-problems at the same time. One programmer could build the seat picker while another builds the card payment, so the project is finished sooner.
A finished sub-problem can be reused in another program. The payment section written for the cinema could go into a swimming pool booking system with little change, so nobody solves that problem a second time.
Decomposition also makes it clearer what the whole solution has to cover, because the sub-problems are a checklist of everything the finished program must do. And when something goes wrong, faults are easier to find: if a ticket prints the wrong price but the seat map looks right, you test the pricing part on its own instead of searching the whole program.
| Benefit | Why it helps | In a cinema booking program |
|---|---|---|
| Simpler to understand, write and test | You focus on one small job at a time | The pricing part is tested before payment is added |
| Work in parallel | Several people make progress at once | One builds the seat picker, another builds payment |
| Reuse | A solved part can be dropped into another program | The payment section suits a pool booking system too |
| See the whole problem | The sub-problems list everything the solution must do | You can check no job has been forgotten |
| Find faults | Each part can be checked separately | A wrong ticket price points to the pricing part only |
Abstraction means setting aside the parts of a problem that do not affect the answer, so you can give your attention to the parts that do. It does not mean removing every detail or making the problem vague: if a climbing-wall program ignored the route number, it could not say which route was climbed, so the solution would fail. Keep enough detail for the solution to work and ignore the rest.
Choosing which details matter
Deciding what to leave in is a key part of abstraction. You keep a detail only when the finished solution depends on it. Imagine a program for a climbing wall that records the routes each climber has finished.
| Detail in the real world | Kept or ignored | Why |
|---|---|---|
| Membership number | Kept | The program must know whose record it is |
| Route number | Kept | The record has to say which route was climbed |
| Date the route was climbed | Kept | The record shows when each route was finished, and results are shown in date order |
| Hair colour | Ignored | Nothing in the solution uses it |
| Brand of climbing shoes | Ignored | It makes no difference to which routes were finished |
Stand-ins for real things
Abstraction also includes representing real things with simpler models. A variable such as lives in a game is a simpler model of the player's remaining lives: it holds a number and nothing else about the player. Creating that stand-in is abstraction, not decomposition, because nothing has been split into smaller parts; the real thing has been swapped for something the program can work with more easily.
Abstraction pays off because a solution that carries only the details it needs is quicker to work with at every stage. Take a program that lets people book a swimming session at a leisure centre. The programmer keeps the swimmer's name, the session time and whether the swimmer has paid, and ignores details such as how many lengths the swimmer swam last week or what they ate for lunch.
Simpler to understand and solve. With only those three pieces of data to think about, you can describe the booking problem in a sentence: find the session, take the payment and record the swimmer. There are fewer things to hold in your head, so it is easier to see what the program must do and to work out how to do it.
Less to design and program. Every detail you keep has to be stored, checked and displayed. Ignoring how many lengths the swimmer swam last week means there is no field for it on the input screen, no validation rule for it and no column for it in the saved data. The program has fewer variables, fewer decisions and fewer lines to write and test, so it is finished sooner.
Concentrates on what the user actually needs. The receptionist booking a swimmer needs to know that the session is paid for. They do not need to know how many lengths the swimmer managed last week or the temperature of the pool water. Leaving those details out keeps the screens and the stored records focused on the job the user is doing.
The benefit comes from the particular detail that is left out and the work it saves. Saying that the booking program ignores how many lengths the swimmer swam last week shows why the program is simpler; a general statement about removing detail does not.
Algorithmic thinking means deciding on the series of actions that will take you from the problem to the answer, putting those actions in the right order, and making each one precise enough that somebody else could follow it exactly and get the same result. An algorithm is a set of instructions, carried out in order, that produces a solution to a problem. The actions are the plan behind a solution; writing program code is one way of putting that plan into action, but the thinking itself comes first.
Precise steps, in the right order
Every step must say exactly what to do. "Find the average" is not a step, because two people could do it in two different ways. "Add the five test scores together, then divide the total by 5" is a step, because there is only one thing to do. Order matters just as much: dividing by 5 before the scores have been added up gives a nonsense answer.
Repetition and decisions
Algorithmic thinking also means spotting the parts of a solution that happen more than once, and the points where a choice has to be made.
Imagine a program that counts the free seats in a row at the cinema. The step "look at the next seat and add 1 to the total if it is free" is repeated for every seat. Repeating steps like this is iteration. After the count, the algorithm chooses between two messages: if the total is 10 or more it says "plenty of space", otherwise "almost full". Making a choice like this is selection. Writing the solution out as steps shows where each loop starts and ends, and exactly what each decision tests.
Why every step must be stated
A processor follows each instruction in turn, in the order it is given, and cannot fill in a gap. A person can guess what was meant; a processor cannot. Leaving out a step, or describing one vaguely, means the program will do the wrong thing, so algorithmic thinking forces you to be exact before any code is written.
When a situation describes a problem, ask what the description is mainly doing. The table shows how to match the description to a computational thinking principle.
| What the description does | Principle |
|---|---|
| Breaks one large problem into smaller sub-problems that can each be solved on its own | Decomposition |
| Removes or ignores unnecessary detail and keeps only the details that are needed | Abstraction |
| Works out the precise steps of a solution and their order, including where steps repeat or a decision is needed | Algorithmic thinking |
Applying all three
Suppose you plan a program for a school garden watering rota. You use decomposition to split it into smaller jobs: storing volunteers, building the weekly rota and sending reminders. You use abstraction to keep the details the rota needs, such as each volunteer's name and the days they are free, and ignore details it does not need, such as the colour of their wellingtons or which pets they own. You use algorithmic thinking to order the steps: for each day, check each volunteer in turn; if they are free that day, add them to the rota; repeat for every day. Algorithmic thinking is the ordered steps, not the program code itself.
Decomposition and abstraction are not the same. Splitting the work into separate jobs is decomposition; deciding which information each job needs is abstraction. A simpler model, such as a variable storing whether a volunteer is free, is also abstraction.
Showing the principle
When you explain a principle, name it and point to the part of the situation that shows it. For example, say that splitting the watering rota into storing volunteers and building the rota is decomposition, rather than only saying that a big problem is broken into small ones. To apply computational thinking, state sensible smaller jobs, say which details to keep and which to remove, and list the steps in order, marking where steps repeat and where a decision is needed.
Computational thinking does not stop once the first version of a solution has been designed. Testing that version against the real problem shows where it falls short, and the problem and its solution are then refined so that they deal correctly with what testing revealed. Two common ways to refine a solution are breaking a stubborn part into smaller sub-problems and putting back a detail that testing showed the solution needs.
Decomposing a part further
A program for a school lost-property desk recorded each item handed in and printed how many items arrived each day. The tally section had been treated as a single job, but it kept going wrong: some days were missed and the weekly total never matched the daily ones. The section was still too big to get right, so it was broken down again into smaller sub-problems: count the items for each day, add the daily counts into a weekly total, and print each line of the tally. Each sub-problem could then be solved and tested on its own. Decomposition is not finished after one pass: an awkward part can always be split again.
Putting a detail back
Abstraction keeps only the details the solution needs, but early on you can judge that wrongly. The lost-property program left out where each item was found, because that seemed unrelated to counting items. Testing showed that the desk's report has to say which part of the school the item came from, so the location was added to the data kept. A detail should only be removed if the solution genuinely never needs it.
Testing decides
Testing is what tells you which parts need more work and which details really matter. Refining after testing, rather than guessing in advance, means the finished solution answers the real problem.