Computational Thinking
The four techniques that let you solve problems the way a computer scientist does, plus flowcharts and pseudocode for planning before you code.
The four techniques
1. Decomposition
Breaking a big problem into smaller problems that are easier to solve.
Planning a school trip decomposes into: choose a destination, book transport, collect permission slips, arrange staff, plan the timetable, handle payments.
Each of those is small enough to actually do.
2. Abstraction
Removing detail that does not matter, so you can focus on what does.
A map of the school for a fire drill needs the rooms, corridors and exits. It does not need the colour of the walls, where the sockets are, or what is on the noticeboards.
The skill is deciding what to leave out. Detail that is irrelevant for one problem may be essential for another.
3. Pattern recognition
Spotting things that are the same or similar, so a solution can be reused.
If you need to calculate the area of six different rectangles, you notice they all follow width x height and write one method rather than six.
4. Algorithmic thinking
Working out the steps needed, in the right order.
Decompose the problem, abstract away what does not matter, look for patterns you can reuse, then write the algorithm.
Step 1 of 3 Decomposition: break the problem into parts small enough to solve one at a time.
- 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.
Flowcharts
A flowchart shows an algorithm as a diagram.
| Symbol | Shape | Use |
|---|---|---|
| Terminal | Rounded rectangle | Start and Stop |
| Process | Rectangle | A calculation or action |
| Input or output | Parallelogram | Getting data in or showing results |
| Decision | Diamond | A question with Yes and No branches |
| Arrow | Arrow | Direction of flow |
Rules
- Every flowchart starts with Start and ends with Stop
- A decision diamond always has exactly two labelled exits
- Arrows show the direction, and a loop is an arrow going back up
Example: is a number even?
Start Input number Is number MOD 2 = 0? Yes -> Output "Even" No -> Output "Odd" Stop
An unlabelled diamond means the reader cannot tell which way is yes. It is the most common mistake in flowchart questions.
- Each shape has one meaning: terminals start and stop, parallelograms are input or output, rectangles are processes, diamonds are decisions.
- Flow lines show the order, and every chart starts and stops with a terminal.
- A decision has two exits, labelled Yes and No, and the two routes join up again.
- The flowchart: ovals for start and end, slanted boxes for input and output, a diamond for a decision with a yes branch and a no branch.
- The Python version has the same steps, matched by colour.
- The pseudocode is the same algorithm again. Only the notation changes.
Pseudocode and testing
Pseudocode describes an algorithm in plain, structured English. It is not a real language, so it will not run, but it lets you plan the logic without worrying about syntax.
total = 0
for i = 1 to 5
number = input("Enter a number")
total = total + number
next i
average = total / 5
print("The average is " + average)Why plan first
- Mistakes in logic are far cheaper to fix on paper than in code
- You can show your plan to someone else and get feedback quickly
- The same plan works in any programming language
- Writing the plan often reveals a step you had forgotten
Trace tables
A trace table shows the value of every variable at every step, which is how you check an algorithm actually works.
For total = 0 then for i = 1 to 3: total = total + i:
| i | total |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 6 |
Testing
Choose test data of three kinds:
- Normal: a typical value that should work, such as 25 for an age
- Boundary: right at the edge of what is allowed, such as 0 and 120
- Erroneous: something that should be rejected, such as "hello" or -5
Boundary data is the most useful, because that is exactly where mistakes hide.
Trace table trainer
Fill in a trace table row by row and have it marked as you type. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Run the program by hand, one line at a time. Line 3 is the one that repeats.
- Follow four rules: one line at a time, one column per variable, a new row for each change, and check the last row.
- Each time the loop runs, i goes up by one and total grows: 0, 1, 3, 6.
- The output is written when print runs. Here it is 6.
Key terms you must be able to define
- Decomposition
- Breaking a large problem into smaller problems that are easier to solve.
- Abstraction
- Removing detail that is not needed so you can focus on what matters.
- Pattern recognition
- Spotting similarities between problems so that a solution can be reused.
- Algorithm
- A set of step by step instructions in the correct order for solving a problem.
- Flowchart
- A diagram showing an algorithm using standard symbols joined by arrows.
- Pseudocode
- A plain English description of an algorithm, used for planning before coding.
- Trace table
- A table showing the value of each variable at every step of an algorithm.
- Boundary data
- Test data at the very edge of what is acceptable, where errors are most likely.
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
The top level here comes from applying the techniques to a specific problem, not defining them.
Use the words from the question. If the problem is about a vending machine, your decomposition should mention accepting coins, checking stock and dispensing the product, not generic phrases.
Justify what abstraction removes. Say what you took out and why it does not matter for this particular problem.
Complete every row of a trace table. Even when you can see the answer, the working is what earns credit.
- Decompose any described problem into at least four sensible sub problems
- Draw a flowchart with a decision and a loop, with both branches labelled
- Complete a trace table for a loop without skipping iterations
- Choose normal, boundary and erroneous test data for a given range
Mistakes that cost marks here
- Confusing decomposition with abstraction. Decomposition splits the problem up, abstraction removes detail.
- Using the wrong flowchart symbol, particularly a rectangle where a diamond is needed.
- Forgetting to label the yes and no branches of a decision.
- Filling in only the last row of a trace table.
- Choosing test data that is nowhere near the boundary.
The word algorithm comes from the name of a Persian mathematician, al-Khwarizmi, who died around the year 850. His book on solving equations also gave us the word algebra.
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.
- LDecomposition is breaking a problem into smaller parts
- LAbstraction is removing detail that is not needed
Decomposition means breaking a large, complex problem down into smaller sub problems, each of which is easier to understand and solve on its own. Abstraction means removing or hiding detail that is not relevant to the problem you are solving, so that you can concentrate only on what actually matters.
- LThe problem is broken into smaller sub problems
- LFirst sub problem such as entering the class name or date
- LSecond sub problem such as counting or storing the numbers
- LThird sub problem such as displaying or saving a report
The overall problem would be broken into several smaller sub problems that can each be solved separately. One sub problem is collecting the input: asking for the date and the class, and entering how many students in that class have a packed lunch. A second is validating and storing that data, checking the number entered is sensible and saving it so it is still there tomorrow. A third is calculating totals, adding up the numbers across all the classes to get a daily figure. A fourth is producing output, displaying the daily total on screen and perhaps saving a weekly summary to a file. Each of these parts is small enough to write and test on its own, and they can then be joined together into the finished program.
- LAfter i = 1 total is 2
- LAfter i = 2 total is 6
- LAfter i = 3 total is 12
- LFinal value of total is 20
When i is 1, i times 2 is 2, so total becomes 0 plus 2 which is 2. When i is 2, i times 2 is 4, so total becomes 2 plus 4 which is 6. When i is 3, i times 2 is 6, so total becomes 6 plus 6 which is 12. When i is 4, i times 2 is 8, so total becomes 12 plus 8 which is 20. The final value of total is therefore 20.
- LThe diamond represents a decision with two labelled branches
- LThe parallelogram represents input or output
The diamond represents a decision. It contains a question with a true or false answer and always has exactly two exits, one labelled Yes and one labelled No, so the flow of the algorithm splits depending on the answer. The parallelogram represents input or output, meaning either data being entered into the system, such as a user typing a number, or results being displayed, such as a message shown on screen.
- LNormal data such as 57
- LExplains that normal data checks the program works with a typical value
- LBoundary data such as 0 or 100
- LExplains that boundary data tests the exact edge of the allowed range
- LErroneous data such as the word hello
- LExplains that erroneous data checks the program rejects the wrong type without crashing
Normal test data would be a mark of 57. This is a typical value well inside the allowed range, and it tests that the program accepts and processes ordinary input correctly. Boundary test data would be 0 and 100, and also 101, because these sit exactly at the edge of what is allowed. Boundary data is the most valuable kind, since the difference between a condition written as less than 100 and one written as less than or equal to 100 only shows up at exactly that value, and off by one errors are extremely common. Erroneous test data would be entering the word hello. This is the wrong type of data entirely and should never be accepted, so the test checks that the program rejects it with a helpful message rather than crashing when it tries to treat text as a number.