Computational thinking

Computers can be used to help solve problems. However, before a problem can be tackled, the problem itself - and the ways in which it could be solved - needs to be understood.

Computational thinking helps with this. It allows us to take a complex problem, understand what the problem is and develop possible solutions. These solutions can then be presented in a way that a computer, a human, or both, can understand.

Three important elements of computational thinking are:

• decomposition

• abstraction

• algorithmic thinking - read more about this in the algorithm production guide

Key fact

Computational thinking involves taking a complex problem and breaking it down into a series of small, more manageable problems. Each of these smaller problems can then be looked at individually.

Complex problems and computational thinking

A complex problem is one that, at first glance, does not have an obvious, immediate solution.

Computational thinking involves taking that complex problem and breaking it down into a series of small, more manageable problems. Each of these smaller problems can then be looked at individually.

Next, simple steps to solve each of the smaller problems can be designed. Finally, these simple steps are used to program a computer to help solve the complex problem in the best way.

Thinking computationally

Thinking computationally is not programming. It is not even thinking like a computer, as computers do not, and cannot, think.

Simply put, programming tells a computer what to do and how to do it. Computational thinking enables you to work out exactly what to tell the computer to do.

For example, if you agree to meet your friends somewhere you have never been before, you would probably plan your route before you step out of your house. You might consider the routes available and which route is ‘best’ - this might be the route that is the shortest, the quickest, or the one which goes past your favorite shop on the way. You would then follow the step-by-step directions to get there.

In this case, the planning part is like computational thinking, and following the directions is like programming.

Being able to turn a complex problem into one that can be easily understood is a skill that is extremely useful.

Decomposition

Decomposition involves breaking down a complex problem or system into smaller parts that are more manageable and easier to understand. The smaller parts can then be examined and solved, or designed individually, as they are simpler to work with.

If a problem is not decomposed, it is much harder to solve. Dealing with a complex problem is much more difficult than breaking a problem down into a number of smaller problems and solving each one, one at a time. Smaller problems are easier to understand and can be examined in more detail.

For example, suppose that a crime has been committed. Solving a crime can be a very complex problem as there are many things to consider.

A police officer would need to know the answer to a series of smaller problems:

• what crime was committed

• when the crime was committed

• where the crime was committed

• what evidence there is

• if there were any witnesses

• if there have recently been any similar crimes

The complex problem of the committed crime has now been broken down into simpler problems that can be examined individually, in detail. Once the individual information has been gathered and collated, the police officer may be able to solve the crime.

Abstraction

Abstraction is the process of filtering out - essentially ignoring - the characteristics of problems that are not needed in order to concentrate on those that are needed. It is also the filtering out of specific details. From this, an idea of what is to be solved can be created.

Abstraction allows us to create a general idea of what the problem is and how to solve it. The process instructs us to remove all specific detail and any patterns that will not help us solve our problem. This helps us form our idea of the problem. This idea is known as a ‘model’.

Consider the problem of how a program might be required to calculate the area of any rectangle. All rectangles share general characteristics:

• a width

• a height

• area = width × height

When abstracting, certain details are discarded but others are kept:

• all rectangles have a width, but for the program design the actual rectangle width is not needed

• all rectangles have a height, but for the program design the actual rectangle height is not needed

• area is always width × height

To solve this problem, all the program needs to be able to do is input a width and a height, then calculate the area from those numbers. The actual numbers are irrelevant - they change with every rectangle - and so are discarded.

An example of abstraction is the London Underground map. It details tube and rail lines and the stations that are on them. That is all that is required for a passenger to be able to plan a journey from one station to another. Other details, such as real geographical location, distance between stations, depth underground and number of platforms are not included as they are irrelevant to journey planning on the Underground.

Algorithm production

An algorithm is a logical, step-by-step process for solving a problem. Algorithm production is part of algorithmic thinking, an important concept in computational thinking. This focuses on how a desired solution can be reached by identifying the steps needed to get there. You can read more about this in the computational thinking guide.

Algorithms are normally written as one of the following:

• pseudocode

• a flow diagram

An algorithm should be seen as a starting point before writing a program. The finished program should follow the steps the algorithm describes.

Before an algorithm can be designed, it is important to check that the problem is completely decomposed. The decomposed problem should consider:

• What are the inputs into the problem?

• What will be the outputs of the problem?

• In what order do instructions need to be carried out?

• What decisions need to be made in the problem?

• Are any areas of the problem repeated?

Only when a problem is properly decomposed and understood can an algorithm design begin.

Producing algorithms with pseudocode

Most programs are developed using programming languages. These languages have specific syntax that must be used so that the program will run properly.

Pseudocode is not an actual programming language. Instead, it is a simple way of describing a set of instructions in a manner that resembles a programming language. It has its own syntax, some of which is very similar to many actual programming languages. Any algorithms designed using pseudocode will not run unless they are converted into an actual programming language.

This simple pseudocode algorithm asks a user to input what their favourite subject is:

while answer != 'computer science'
     answer = input ('What is your favourite subject? ')
     if answer == 'computer science' then
          print('Good choice!')
     else
          print('Really? ')
     endif
endwhile

Advantages and disadvantages of pseudocode

Designing an algorithm in pseudocode has benefits:

• because pseudocode is similar to a programming language, it can be quickly and easily converted into an actual programming language

• it is fairly easy to understand, even for non-programmers

• it does not matter if there are errors in the syntax - it is usually still obvious what is intended

• changes to the design can be incorporated quite easily

Pseudocode also has its disadvantages:

• It can be hard to see how a program flows, for example, where does following one path as opposed to another take the program?

• It can be time consuming to produce.

Pseudocode covers many areas of programming and there are different variants. The specific pseudocode syntax for your course can be found at the end of the OCR specification.

Flow diagrams

A flow diagram is a diagram that shows an overview of a program. Flow diagrams normally use standard symbols to represent the different types of instruction. These symbols are used to construct the flowchart and show the step-by-step solution to the problem. Flow diagrams are sometimes known as flowcharts.

Common flow diagram symbols

Flow diagrams can be used to plan out programs. This simple flow diagram maps out an algorithm for a program that prints the numbers 1 to 10:

Advantages and disadvantages of using flow diagrams

Designing an algorithm using flow diagrams has benefits:

• It is easy to see how a program flows. For example, where does following one path as opposed to another take the program?

• Flow diagrams follow an international standard - it’s easy for any flow diagram user to pick up a diagram and understand it.

Flow diagrams also have their disadvantages:

• with a large program, the diagrams can become huge in size and unwieldy to follow any changes to the design may mean a lot of the diagram has to be redrawn

Programming errors

When developing programs there are two types of error (bug) that often occur:

• syntax errors

• logic errors

Syntax errors

A syntax error occurs when code written does not follow the rules of the programming language. Examples include:

• misspelling a statement, eg writing pint instead of print

• using a variable before it has been declared

• missing brackets, eg opening a bracket but not closing it

A program will not run if it has syntax errors. Any such errors must be fixed first. A good integrated development environment (IDE) will usually point out any syntax errors to the programmer.

Logic errors

A logic error is an error in the way a program works. The program simply does not do what it is expected to do.

Logic errors can have many causes, such as:

• incorrectly using logical operators, eg expecting a program to stop when the value of a variable reaches 5, but using <5 instead of <=5

• incorrectly using Boolean operators

• unintentionally creating a situation where an infinite loop may occur

• incorrectly using brackets in calculations

• unintentionally using the same variable name at different points in the program for different purposes

• referring to an element in an array that falls outside of the scope of the array

Unlike a syntax error, a logic error will not usually stop a program from running. Instead the program will run but not function as expected.

Trace tables

One way to test short programs is to do what is known as a dry run using paper. A dry run involves creating what is called a trace table, containing all the variables a program contains. Whenever the value of a variable changes, the change is indicated in the trace table.

Key fact

Trace tables help a programmer to determine the point in a program where a logic error has occurred.

Consider this simple program:

1   total = 0
2   for count = 1 to 3
3       number = int(input("Enter number ", count))
4       total = total + number
5  next count

Each instruction has been given a line number (1-5). The program has three variables - total, count and number – which will be put into a trace table.

Next, the program is tested using test data. If the numbers 5, 7 and 9 are inputted, the resulting total should be 21.

The instruction number is inputted. If a variable changes with that instruction, the new variable value is written in the appropriate box, as follows:

At each step, the programmer is able to see if, and how, a variable is affected.

Trace tables are extremely useful because they enable a programmer to compare what the value of each variable should be against what a program actually produces. Where the two differ is the point in the program where a logic error has occurred.