B1.1 Approaches to computational thinking

Computational thinking

What computational thinking is

People often assume that computer science is the same as programming. Programming is one way of expressing a solution, but the harder work is deciding what the solution should do and how it should do it. That work is a way of thinking, and it can be done with a pencil, a whiteboard or a conversation.

The word "computer" in the definition matters. Before electronic machines existed, a "computer" was a person who carried out calculations by following written instructions. A recipe, a fire-evacuation plan and the instructions for assembling furniture are all solutions expressed so that someone else can carry them out without having to think of the method themselves. Computational thinking is the skill of producing such instructions for problems where no obvious method exists.

The term was first used by the mathematician and educator Seymour Papert in 1980. It reached a wide audience in 2006, when Jeannette Wing published an essay called "Computational Thinking" in Communications of the ACM, arguing that it is a basic skill for everyone, not only for computer scientists. Her everyday examples included a child packing a school backpack in the morning with the things needed for the day, which she called prefetching and caching (fetching data before it is needed and keeping it close at hand), and retracing one's steps to find lost mittens, which she called backtracking.

The computational thinking process

Computational thinking is usually described as a process with six stages. It begins with a clear statement of the problem and ends by checking the solution against that statement. The cycle of the process shows how the stages connect, and that the last stage feeds back into the first.

In practice the stages overlap. While decomposing a problem a designer often spots a pattern; while designing an algorithm they may realise that the abstraction removed a detail that matters, and go back a step. The order in the table is the order in which each stage first becomes the main focus, not a rule that the stages happen once each.

Testing and evaluation close the loop. Testing runs the solution with chosen data (normal, boundary and erroneous data, all taught in subtopic B2.1, Programming fundamentals) and compares the results with what the specification says should happen. Evaluation weighs the whole solution against each success criterion and decides whether it is finished, needs adjusting, or shows that the original specification was wrong.

Problem specification

Why a problem is specified first

A problem described in everyday speech is almost always ambiguous. "The library needs a better way to deal with overdue books" could mean sending reminders, charging fines, blocking new loans, producing reports for the librarian, or all four. Two developers given that sentence would build two different systems, and neither might be what the librarian wanted.

A specification removes that ambiguity before design starts. It records what the solution must do, what it must not do, the limits it must work within and the test that will decide whether it worked. Errors found at this stage cost almost nothing to fix: changing a sentence is cheaper than rewriting a program that has already been built, tested and delivered.

The parts of a specification

A complete specification has six parts. Each answers a different question, and each can be checked separately.

A good problem statement is one or two sentences long and describes the problem, not a solution. "The school librarian has no quick way to find which books are overdue, so overdue books are chased late or not at all" is a problem statement. "Build an app with a red warning button" is a solution, and it closes off better options before they have been considered.

Constraints are usually fixed by the client, the organisation or the law, so the designer works within them instead of changing them. Common types are time (a deadline), cost (a budget), hardware (the computers or phones that will run the solution), software and platform (an existing operating system or database), legal and ethical rules (data protection, accessibility, copyright) and the users themselves (their age, language and technical skill). Some writers separate limitations (what the solution will deliberately not do, such as "the system will not handle payments") from constraints; both set the boundary of the problem. A constraint in a problem specification is a different idea from an integrity constraint in a database (subtopic A3.1, Database fundamentals).

Objectives say what the solution must do. They are written as actions ("The system must list every overdue book with the borrower's name and form") and are usually numbered so that each can be traced through design and testing. Broad aims such as "improve the library" are too vague to act on; they become useful only when broken into specific objectives.

An input specification is precise enough for a programmer to write validation from it. "Loan length: whole number of days, 1 to 28 inclusive, entered by the librarian" can be turned directly into a check; "the loan period" cannot. Each input should state its unit wherever a unit applies: a number without a unit can be read in more than one way.

Outputs include screens, printed reports, files, messages sent to other programs and signals sent to devices. When the output of one program is the input of another, the output specification of the first and the input specification of the second must match exactly; that shared agreement is often called an interface specification.

Success criteria are also called evaluation criteria, because they are what the final evaluation checks. Each objective should have at least one criterion, and each criterion should be testable by someone who has never met the client: they run the test, read the result and record pass or fail without needing anyone's opinion.

The six parts work together. The table applies each one to the overdue-books problem and shows a weak and a strong version side by side.

Telling inputs, constraints and objectives apart

The parts of a specification are easy to blur. An input is data that enters the solution while it runs. A constraint is a condition on the whole project, fixed before any data exists. An objective is something the solution does. A useful test is to ask whether the item has a value that changes each time the solution is used: if it does, it is probably an input; if it is true for every run, it is probably a constraint.

Case study: the Mars Climate Orbiter

The Mars Climate Orbiter was a NASA probe launched on 11 December 1998 to study the Martian climate and to relay signals from a lander. On 23 September 1999, as it fired its engine to enter orbit, it passed behind Mars 49 seconds earlier than expected and was never heard from again. It had approached far too close to the planet and was destroyed or thrown back into space.

The cause was a mismatch at the boundary between two pieces of ground software. A program supplied by the spacecraft's builder, Lockheed Martin, calculated the impulse produced by each firing of the small thrusters and wrote the results to a file. A second program, run by NASA's navigation team, read that file to work out where the spacecraft was. The written interface specification between the two said the impulse must be given in newton-seconds (an SI unit). The first program produced it in pound-force seconds, a US customary unit, so every value was too small by a factor of about 4.45.

Source: NASA Mars Climate Orbiter Mishap Investigation Board, Phase I report, 10 November 1999; mission figures from NASA.

The small errors added up over the nine-month flight. Each thruster firing nudged the real path a little more than the navigation software believed, so the predicted position drifted away from the true one. Navigators noticed that the measured and predicted positions disagreed, but the concerns were not followed up through the formal process, and a planned final correction burn was not carried out.

The fault lay at the interface between two programs, not in the logic of either one. A correct interface specification existed and named the unit, but nothing checked that the output of one program actually met the input specification of the other. Three computational thinking lessons follow from the loss.

• Outputs and inputs must state units. An output specification such as "impulse, in N·s, to two decimal places" leaves no room for a different reading.

• Interfaces between sub-problems need testing. Decomposition split the navigation problem into separately built parts. Each part worked alone, and the link between them was not checked with real data before the navigators relied on it.

• Success criteria must be checked against real data. A criterion such as "predicted and measured positions agree to within a set distance", checked after every firing, would have recorded the drift as a failed test that had to be resolved before the next manoeuvre.

The fundamental concepts of computational thinking

Four concepts do most of the work between specifying a problem and testing its solution. Each is a different kind of mental move, and solving a real problem uses all four, often several times over.

Decomposition

Large problems are hard to solve because too much has to be held in mind at once. Breaking them into parts reduces each part to something one person can understand, design and test in a reasonable time.

Decomposition is applied repeatedly. The whole problem is split into a few large parts; each part that is still too complex is split again, and so on, until every remaining sub-problem is small enough to solve directly. This approach is called top-down design, because it starts with the whole problem at the top and works down to the details.

The decomposition diagram for a school cafeteria pre-order app shows the whole system at the top, four main sub-problems on the second level, and the tasks that make up each sub-problem below them.

The diagram shows structure, not order. "Take orders" appears beside "Show the menu", but nothing in the diagram says which happens first; a flowchart is needed to show the order of steps. The bottom-level boxes are typical of a good decomposition: each has a single clear job, and each could be given to a different member of a team.

Decomposition brings several benefits.

• Manageability: each sub-problem is small enough to understand completely.

• Teamwork: different people can work on different parts at the same time.

• Testing: each part can be tested on its own before the parts are joined, so faults are easier to locate.

• Reuse: a part such as "Log in" may already exist in another system, or be reused in the next one.

• Maintenance: a change to one part (for example, a new allergen rule) affects only that part.

It also has costs. Every split creates an interface, a point where one part passes data to another, and each interface must be specified and tested, as the Mars Climate Orbiter showed. Splitting too far produces dozens of tiny parts whose connections are harder to follow than the original problem. Some problems also resist clean decomposition, because their parts depend heavily on each other: the "Check balance" task, for instance, needs data from "Top up balance" in a different branch.

In code, each bottom-level task usually becomes a subprogram (a function in Python, a method in Java). A program built this way is easier to read and to change, an idea developed as modularisation in subtopic B2.3, Programming constructs.

Pattern recognition

Once a problem has been broken into parts, many of the parts turn out to resemble each other, or to resemble problems that have been solved before. Recognising those similarities saves designing the same thing twice and allows a proven method to be reused.

Patterns appear in three places.

• Within one problem. The quiz app asks ten questions the same way, so one set of steps can be repeated ten times. Repetition inside a problem becomes iteration (a loop) in an algorithm, and a task that appears in several places becomes a subprogram called from each place.

• Between problems. "Find a book by its ID", "find a student by name" and "find whether a password is on a list of banned passwords" are all the same problem: search a collection for a value. Once the pattern is recognised, an existing method such as linear search (subtopic B2.4, Programming algorithms) can be reused instead of designing a new one for each case.

• In data. Trends, cycles and unusual values in data are also patterns. A shop that sees sales rise every Friday can predict next Friday's demand; a bank that sees a card used in two countries an hour apart can flag possible fraud.

Pattern recognition is what turns specific examples into a general method. By working through several small cases, writing down what happens and looking for what stays the same, a designer can produce a rule that works for any case, including ones too large to try by hand.

Abstraction

Every real situation contains far more detail than any solution can use. Abstraction is the decision about which details to keep. What counts as "essential" depends entirely on the purpose: the same city looks very different on a map for drivers, a map for cyclists and a map for the water company.

Abstraction produces a model: a simplified representation that keeps only what the solution needs. A school database does not store a student's height, favourite song or the colour of their bag, because none of those help it record attendance and grades. A computer game models a ball's position and speed but not the stitching on its surface. Choosing variables for a program is a small act of abstraction: each variable is a detail judged worth keeping.

Abstraction also works in levels. A driver uses the steering wheel, pedals and indicators without knowing how the engine works; a mechanic works one level down. Computing is built from such levels: a Python programmer writes print("Hello") without handling the machine code it becomes, and the operating system hides the details of each disk drive behind the idea of a "file". Each level hides the complexity of the one below, so that people can work on one level at a time.

Generalising is a form of abstraction too. The tournament rule "matches = $n - 1$" ignored the names of the players, the scores and the order of the matches, and replaced the specific numbers 2, 4 and 8 with the general $n$.

Harry Beck's London Underground diagram

One of the most widely cited examples of abstraction is the London Underground diagram. Earlier maps of the network drew the lines on top of a street map, so stations in the centre were crammed together and those in the suburbs were spread far apart. Harry Beck, an engineering draughtsman used to drawing electrical circuit diagrams, realised that passengers below ground were not concerned with geography. They wanted to know which line to take and where to change trains.

Beck drew the diagram in 1931 using only straight lines at horizontal, vertical and 45° angles, with stations spaced roughly evenly. London Underground's publicity department first rejected it as too radical, but after a trial print of 500 copies in 1932 it was issued to the public in January 1933 with 700,000 copies, and a large reprint was needed within a month. Every London Underground map since has kept Beck's approach.

The diagram shows both the strength and the limit of abstraction. For planning a journey by train it is better than an accurate map, because it removes everything that does not help with that task. For walking it is misleading, because the true distances it removed are exactly what a walker needs: some stations that look far apart on the diagram are a few minutes' walk from each other at street level.

From a road map to a graph

Route-finding software applies the same idea to roads. A road map contains bends, rivers, forests, buildings and road names. To find the shortest route between towns, almost all of that can go: what matters is which towns are joined directly and how long each road is. The road map and its abstraction show the towns becoming dots (nodes), the roads becoming straight lines (edges), and each road's length becoming a number on its line.

Edsger Dijkstra designed his shortest-path algorithm in 1956, by his own account in about twenty minutes while sitting at a café in Amsterdam, and published it in 1959. To demonstrate it on the ARMAC computer at the Mathematical Centre in Amsterdam, he used a simplified transport map of 64 Dutch cities, a number chosen so that each city could be stored as a 6-bit code ($2^{6} = 64$). Reducing the country to cities, the roads between them and their lengths made the problem small enough for the machine, and the search steps were then designed to work on that model.

Algorithmic design

Decomposition, pattern recognition and abstraction prepare a problem for the final step: designing the exact instructions that solve it.

To count as an algorithm, a set of instructions needs five properties.

1. Precise: every step has one meaning. "Add a bit of salt" is not precise; "add 5 g of salt" is.

2. Finite: it always stops after a finite number of steps, including when the input is unusual.

3. Defined inputs: it states what data it starts with (possibly none).

4. Defined outputs: it produces at least one result.

5. Effective: each step can actually be carried out, by hand or by machine, with the resources available.

An algorithm can be written in several forms: numbered steps in plain language, a flowchart, or code in a programming language. The method stays the same whichever form is used to write it down, so the same algorithm for finding the largest number in a list can appear as five numbered steps, as a flowchart and as a Python function.

Algorithmic design has four steps, much like the scientific method of observing, hypothesising and testing.

1. Explore the problem with different values. Work through small examples by hand, changing the inputs, to see how the problem behaves.

2. Record the steps. Write down exactly what was done for each example. This is a first, specific draft of the algorithm.

3. Recognise patterns and generalise. Find the steps that recur across the examples and rewrite them for any input, not just the ones tried.

4. Test and validate. Run the general algorithm on many inputs, including unusual ones, and refine it. Testing can show that an algorithm fails, but passing a set of tests never proves it works for every possible input; a logical argument (like the "every match eliminates one player" reason in the tournament rule) is what gives confidence in the general case.

Refinement also considers efficiency: how much time (number of steps) and space (memory) the algorithm needs. Different algorithms can solve the same problem at very different costs. Adding the whole numbers from 1 to $n$ can be done with a loop that performs $n$ additions, or with the formula $\frac{n(n+1)}{2}$, which takes the same three operations however large $n$ is.

Both versions print the same results, but for $n = 1{,}000{,}000$ the loop performs a million additions while the formula performs one multiplication, one addition and one division.

The Java version stores the result in a long, because 500,000,500,000 is larger than the biggest value a Java int can hold (2,147,483,647); Python's integers grow as needed, so the Python version needs no such choice. Comparing algorithms by how their number of steps grows with the input is formalised as Big O notation in subtopic B2.4, Programming algorithms.

Applying computational thinking to problems in computer science

Computational thinking without a computer

Computational thinking is a toolkit for solving problems, and many of its uses involve no programming at all. A school building its end-of-term test timetable decomposes it into rooms, times and subjects, abstracts each student to the list of tests they sit, recognises the pattern "two tests for the same student cannot overlap", and designs a procedure for placing tests one by one. A hospital planning its emergency department does the same with patients, beds and staff. The result may be a spreadsheet, a set of rules on paper or a program, and the same four concepts produce each of them.

The value of the concepts lies in what each one does to the problem. Decomposition makes a large problem manageable. Pattern recognition saves effort and allows prediction. Abstraction makes a problem simple enough to reason about. Algorithmic design makes the solution exact and repeatable, so that it gives the same answer whoever, or whatever, carries it out.

The table applies all four concepts to five areas of computer science.

Software development

Software development is where decomposition is most visible. A large system is split into separate modules, each module into subprograms, and each subprogram is designed, written and tested on its own. Pattern recognition means a developer who needs to sort a list or check a password does not invent a new method but reuses a well-tested one, often from a library. Abstraction decides which data the program stores and hides the internal details of each module behind a simple set of operations, so other parts can use it without knowing how it works. Algorithmic design then produces the steps for each subprogram, and testing against the success criteria decides when the software is ready.

Data analysis

A data analyst answering a question such as "which bus routes are most often late?" decomposes the job into collecting data, cleaning it, analysing it and presenting results. Abstraction keeps only the fields that bear on the question (route number, scheduled and actual arrival times) and ignores the rest (driver name, bus colour). Pattern recognition is the analysis itself: finding that one route is late every weekday morning, or that delays rise when it rains. Algorithmic design makes the analysis repeatable: the same cleaning and calculation steps can be run every month on new data and give comparable results.

Machine learning

In machine learning (subtopic A4.1, Machine learning fundamentals), pattern recognition is the purpose of the whole system: a model is trained to find patterns in training data that let it make predictions about new data. Abstraction appears as the choice of features, the measurable properties that represent each example. A system that predicts house prices might use floor area, number of rooms and location, and ignore wallpaper and the owner's name. Decomposition splits the project into collecting data, preparing it, training, and evaluating the model on data it has not seen, and the training procedure itself is an algorithm.

Database design

Designing a relational database (subtopic A3.2, Database design) starts with decomposition: the data for a school is split into separate entities such as students, classes and teachers, each stored in its own table. Abstraction chooses the attributes worth storing for each entity. Pattern recognition finds data that is repeated, for example a teacher's email address typed into every lesson record, and the process of normalisation removes that repetition by storing each fact once. Algorithmic design produces the queries that join the tables back together to answer questions.

Network security

Security teams decompose a network into zones (the public web server, staff computers, the finance system) and set different rules for each, so that a break-in to one zone does not expose the others. A firewall (subtopic A2.4, Network security) applies an algorithm to each packet: compare its source, destination, port and protocol with an ordered list of rules and allow or block it. Those four fields are an abstraction of the packet, chosen because they are enough to make the decision. Pattern recognition detects attacks, either by matching traffic against the known "signatures" of earlier attacks or by noticing traffic that differs from the network's normal pattern, such as one computer suddenly contacting thousands of addresses.

Flowcharts

What a flowchart shows

Numbered steps are easy to write but hard to follow when an algorithm branches or repeats. A flowchart draws the algorithm as a diagram, so the paths it can take are visible at a glance.

Six standard symbols cover every flowchart. The chart of symbols shows each shape with its name, a typical label and its purpose.

Every flowchart has exactly one Start terminator, with one flowline leaving it. Most flowcharts also have a single End; where an algorithm can finish in more than one way, the paths are usually joined into one End to keep the chart tidy.

A process box holds one action or a short group of actions done in sequence, such as total = total + value or i = i + 1. The = sign in a flowchart process means "becomes": the right-hand side is worked out first, then stored in the variable on the left.

Inputs come from a user, a file or a sensor; outputs go to a screen, a printer, a file or another program. The text in the shape says which: "Input n" or "Output total". Using a rectangle for an input, or a parallelogram for a calculation, gives the wrong meaning to the step.

The question in a decision is a condition that is either true or false, such as count < n ?. One exit is labelled Yes (or True) and the other No (or False), and every decision must have both labels. Decisions are how a flowchart shows both selection (choosing between two paths) and loops.

Flowlines normally run from top to bottom and left to right, but a flowline can point in any direction; the arrowhead, not the position, decides the order. A flowline that leads back up to an earlier symbol creates a loop.

Connectors keep large charts readable. Instead of a long flowline crossing other lines, the flow leaves at a connector marked "A" and resumes at the other connector marked "A". The same idea is used to continue a chart on another page.

Sequence, selection and iteration in a flowchart

Every algorithm is built from three structures, each with a recognisable shape in a flowchart.

• Sequence: symbols joined one after another by flowlines, carried out in order. Starting, inputting n and setting total = 0 is a sequence.

• Selection: a decision whose two exits lead to different symbols and then rejoin. The flow takes one path or the other, never both, on each pass.

• Iteration: a decision with one exit that leads to a set of steps and then back, by a flowline or a connector, to the decision. The steps repeat until the condition sends the flow out along the other exit.

A loop in a flowchart is therefore a decision plus a flowline that points backwards. If the steps inside the loop never change anything the decision tests, the condition never changes and the loop never ends, which breaks the "finite" property of an algorithm.

Tracing flowcharts with trace tables

Tracing and trace tables

The structure of a flowchart can be seen at a glance, but its output for particular data is found only by tracing it. Tracing means acting as the computer: start at Start, follow each flowline, carry out each step exactly as written and keep a record.

The record is kept in a table with a column for every variable, and the table makes errors easy to spot because every change is visible.

The standard conventions for a trace table are:

1. One column for each variable, in the order the variables first appear.

2. Optional columns for each decision's condition (recording Yes or No, or True or False) and one column for output.

3. A new row each time a value changes or a decision is tested, working strictly in the order the flowchart is followed.

4. Blank cells mean "unchanged"; the current value of a variable is the last value written in its column.

5. Output is copied exactly as the flowchart would produce it, and only when an output symbol is reached.

The total of n numbers

The flowchart for adding up $n$ numbers inputs $n$, sets two variables to 0, and then repeats an input-and-add step while the counter is less than $n$. The loop is formed by the decision count < n ? and the flowline that returns to it from the bottom of the loop.

A trace with $n = 4$ and the values 5, 2, 8 and 3 records each step in order. The condition column shows the comparison actually made, so the exit from the loop can be checked.

The loop body ran four times, once for each value, and the decision was tested five times: four Yes answers and the final No that ends the loop. A loop that runs $n$ times always tests its condition $n + 1$ times.

Each symbol of the flowchart maps onto a line of code. The decision and its backward flowline become a while loop, the process boxes become assignments, and the parallelograms become input and output statements.

Run with the same inputs, both programs produce the result the trace predicted.

The largest value in a list

Finding the largest value combines a loop with a decision inside it. The flowchart sets largest to the first item, then compares every other item with it, replacing largest whenever a bigger item is found. Items are numbered from 0, so items[0] is the first item and items[i] is the item at position i.

Starting largest at the first item, not at 0, is a deliberate design choice. If every item in the list were negative, such as [−3, −8, −1], a starting value of 0 would never be replaced, and the flowchart would output 0, a value that is not even in the list.

Linear search, with a connector

A linear search checks the items of a list one at a time until it finds the target or runs out of items. Its flowchart has two exits from the loop: one when the target is found and one when every item has been checked. Instead of a long flowline from i = i + 1 back to the loop's decision, the flowchart uses a pair of connectors labelled A.

The two decisions do different jobs. i < n ? guards the loop, making sure the search never looks past the last item; items[i] = target ? is the actual comparison. The order matters: testing items[i] when i equals n would look for an item that does not exist, which in a program causes an index error.

The function returns the position instead of printing a message, and uses −1 to mean "not found". It finds 31 at position 2 and the first 7 at position 1, and reports −1 for 5.

A harder trace: nested decisions

The final flowchart applies a rule to a whole number $n$ until it reaches 1: if $n$ is even it is halved, and if it is odd it becomes $3n + 1$. It counts the steps taken. A decision inside the loop chooses between the two rules, and both paths rejoin before steps is increased.

Exam focus

Computational thinking is examined on Paper 2, most often in the compulsory question on algorithmic thinking that needs no code to be read or written. That question typically gives a real-world problem and asks you to specify it, apply the concepts of computational thinking to it, and follow or describe an algorithm, often presented as a flowchart.

The command terms set the depth.

• Construct (AO3) a problem specification: each heading must be filled with detail specific to the scenario; typically 4–6 marks.

• Describe (AO2) a concept of computational thinking: a precise meaning plus an example; typically 2 marks.

• Explain (AO3) how a concept helps solve a given problem: the concept, how it is applied in the scenario, and its effect; typically 2–4 marks.

• Identify (AO2) a flowchart symbol or a part of an algorithm: a single correct choice; 1 mark.

• Trace (AO2) a flowchart: a trace table or written record of every variable and output, in order; typically 3–6 marks.

In the trace, the boundary value 14.0 is the step most likely to go wrong. The condition is "less than", so a time equal to the limit does not qualify; read the comparison sign in every decision before tracing, and record the comparison itself (14.0 < 14.0: No) so the reasoning is visible.

When a question asks you to describe a concept, give its meaning and an example; when it asks you to explain how a concept helps, add the effect on the problem, linked by "so" or "because". A definition alone answers neither fully.

Practice questions

1. State the name and shape of the flowchart symbol used to test a condition. [2]

2. Distinguish between decomposition and abstraction. [2]

3. Outline what is meant by pattern recognition, with an example from data analysis. [2]

4. A specification contains the success criterion "The app should be fast and easy to use." Identify why it is a weak criterion and rewrite it as two measurable criteria. [3]

5. A school wants an online system for booking parent–teacher meetings. Construct a problem specification for the system, with at least one point under each of the six headings. [6]

6. Trace the flowchart for the largest value with items = [−3, −8, −1, −5] and n = 4, and state the output. Then explain why setting largest to 0 at the start, instead of items[0], would give the wrong output for this list. [5]

7. Trace the flowchart that halves $n$ when it is even and replaces it with $3n + 1$ when it is odd, for the input $n = 5$, and state the output. [3]

8. A knockout chess tournament has 64 players. State the number of matches needed and explain your answer using pattern recognition. [3]

9. Explain how computational thinking could be applied to protecting a school network from attack. [4]

10. Explain why computational thinking does not necessarily involve programming, with an example. [2]

Summary

• Computational thinking is a toolkit for formulating problems and expressing solutions so that a human or a machine can carry them out; it does not require programming.

• The process runs from problem specification, through decomposition, pattern recognition, abstraction and algorithmic design, to testing and evaluation, and repeats until the goals are met.

• A problem specification has a problem statement, constraints, objectives, input and output specifications and success criteria; criteria must be measurable, and inputs and outputs need types, formats, ranges and units.

• Decomposition breaks a problem into smaller parts (shown in a decomposition diagram); pattern recognition finds what repeats within or between problems or in data; abstraction removes detail that does not matter for the purpose; algorithmic design creates exact, finite steps.

• An algorithm is precise, finite, has defined inputs and outputs, and is effective; different algorithms for the same problem can differ greatly in efficiency.

• In software development, data analysis, machine learning, database design and network security, each concept is useful because of its effect: smaller problems, reused solutions, simpler models and exact, repeatable steps.

• Flowcharts use six symbols: terminator, process, input/output, decision, flowline and connector; a loop is a decision plus a flowline (or connector pair) leading back to it.

• Tracing records every variable change, every decision and every output in a trace table, in the order the flowchart is followed.

Self-check

• To do:

  I can write a one- or two-sentence problem statement that describes a problem, not a solution.

• To do:

  I can sort statements into inputs, constraints, objectives, outputs and success criteria, and justify each choice.

• To do:

  I can turn a vague requirement into a measurable success criterion.

• To do:

  I can explain how the Mars Climate Orbiter was lost through a mismatch between an output and an input specification.

• To do:

  I can draw a decomposition diagram with at least three levels for a familiar system.

• To do:

  I can describe decomposition, pattern recognition, abstraction and algorithmic design, each with an example.

• To do:

  I can explain the difference between abstraction and decomposition, and between abstraction in computational thinking, OOP and ADTs.

• To do:

  I can find a general rule from small cases and explain why it always holds.

• To do:

  I can state the five properties of an algorithm and write an algorithm as precise numbered steps.

• To do:

  I can explain how each concept of computational thinking is applied in software development, data analysis, machine learning, database design and network security.

• To do:

  I can name and draw the six standard flowchart symbols and say what each represents.

• To do:

  I can find the loops and selections in a flowchart, including loops joined by connectors.

• To do:

  I can trace a flowchart with nested decisions in a trace table and state its output.

• To do:

  I can predict how changing a condition (such as < to ≤) changes a flowchart's output.

Markscheme (c)

Each row shows the values at the moment the outer decision is tested. For example, on the second row $n = 3$ is odd, so the next value is $3 \times 3 + 1 = 10$.

Output: 8.

(b) With $n = 1$ the first test n ≠ 1 ? is No, so the loop body never runs and the output is 0.

(c) For every whole number of 1 or more, n ≠ 1 and n > 1 give the same answer: both are false only when $n = 1$. Halving an even number of 2 or more, or applying $3n + 1$, never produces 0 or a negative number, so the two conditions agree on every pass and the output does not change. (They would differ for an input of 0, which loops for ever with n ≠ 1 because 0 halves to 0.)