The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.

net

1 – Problem Solving
Specification Coverage

This chapter covers the following specification content from topic 1:

• 1.1.1 decomposition and algorithms

• 1.2.1 understanding algorithms and algorithmic thinking
• 1.2.4 trace tables
• 1.2.6 search and sort algorithms (including evaluating their efficiency)
• 1.2.7 evaluating efficiency of algorithms
• 1.3.1 truth tables

Chapter 6 (Programming) will cover the following specification content from topic
1:
• 1.1.2 benefits of subprograms
• 1.2.2 variables, constants, strings, records and arrays
• 1.2.3 arithmetic, relational and logical operators
• 1.2.5 programming errors

Python Files

Where Python has been used in examples, there will be two icons which are both
buttons that link to the original Python code. One icon is for the Python code in
Repl.it and the other is for the Python (.py) file:

Some activities will also include these buttons. Not all activities include the buttons
as running the Python code for those activities would make answering the question
too easy. Where answers are provided using Python, many of the answer
documents (both activity answers and exam style question answers) will include
links to Python files that include answers in Python code, and often a step-by-step
run through of the code. The icons used for answers are:

These answer files can be used by the teacher to explain the answers to students
after they have completed the tasks, or by students once they have completed
the tasks.

© paullong.net 2020 Page 1 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

PRIMM

This chapter follows the PRIMM approach to learning programming. Where

examples or activities use elements of PRIMM then it is denoted using the following
icons:

Predict what the program does

Run the program
Investigate how the program works
Modify the program
Make a new program

Note: It is recommended that students complete chapter 6 before this chapter, or

at least that some parts of chapter 6 are taught before some parts of this
chapter in order to understand programming concepts used within some of
the algorithms in this chapter.

Flowcharts

Where flowcharts have been used there will be an icon which will open
the file created in draw.io

This free software can either be downloaded from http://tiny.cc/downloaddrawio

or used directly online from https://app.diagrams.net/

Visualising Variables
Use the trace variables visualisation tool at http://tiny.cc/tracevariables
to watch what happens to the value of the variables as each line is
executed. You can input any code into the tool. If inputs are required,
then add these, including if enter needs to be input.

© paullong.net 2020 Page 2 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Contents

1) Representing algorithms ............................................................................................ 4

Algorithms ................................................................................................................ 4
Decomposition ........................................................................................................ 7
Abstraction ............................................................................................................ 10
Pattern recognition............................................................................................... 14
Problem solving ..................................................................................................... 18
Pseudocode ............................................................................................... 18
Flowcharts ................................................................................................... 20
2) Understanding algorithms ........................................................................................ 28
Input, process and output ................................................................................... 28
Understanding the purpose of an algorithm ..................................................... 33
Trace tables ........................................................................................................... 37
Evaluating algorithms ........................................................................................... 43
3) Searching algorithms ................................................................................................ 50
Linear search ......................................................................................................... 50
Binary search ......................................................................................................... 57
Binary search – extension work ................................................................. 62
Comparing and contrasting search algorithms ................................................ 69
4) Sorting algorithms ..................................................................................................... 73
Bubble sort ............................................................................................................. 73
Bubble sort – extension work ..................................................................... 81
Merge sort.............................................................................................................. 85
Merge sort – extension work...................................................................... 88
Comparing and contrasting sort algorithms ...................................................... 91
Comparing and contrasting sort algorithms – extension work .............. 92
5) Truth tables ................................................................................................................ 95
Introduction ........................................................................................................... 95
Truth tables ............................................................................................................ 95
Logical operators .................................................................................................. 96
NOT .............................................................................................................. 96
AND ............................................................................................................. 97
OR ................................................................................................................ 98
Combining logical operators .............................................................................. 99
Truth tables for Boolean expressions ........................................................ 99
Precedence rules ..................................................................................... 101

© paullong.net 2020 Page 3 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

1) Representing algorithms

Algorithms
An algorithm is a sequence of clear instructions that are used to solve a problem
step by step.

Video
Watch the video about algorithms at http://tiny.cc/bbcalgorithms from BBC
Teach. Write down 4 things you have found out about algorithms. Share these
with your class.

Example – algorithm to make toast

1) Open the bread bin door
2) Pick up the bag of bread
3) Open the bag of bread
4) Take one slice of bread from the bag
5) Place slice of bread vertically into toaster
6) Pull the lever down on the toaster
7) Close bag of bread
8) Put bag of bread back in bread bin
9) Close the bread bin door
10) Wait for toast to pop up out of toaster
11) Remove toast from toaster

Algorithms must be unambiguous, complete, accurate, consistent and efficient.

Instructions must be unambiguous which means they must not be open to more
than one interpretation. The instructions must be clear and easily understood. For
example, instruction number 5 in the example above clearly states that the bread
must be placed vertically into the toaster. If the word vertically had not been
used, then somebody following the algorithm could try to squash the bread in
horizontally.

Video
Watch the video about evaluating algorithms at http://tiny.cc/evalalgorithms
from BBC Teach. Identify aspects of the video that demonstrate how an algorithm
may be ambiguous, incomplete, inaccurate, inconsistent or inefficient.

Instructions must also be complete. In the example above, instructions 7 to 9

complete the process of putting the bread away. However, the algorithm
assumes that the toast is complete once it has popped up out of the toaster.
What if the person eating the toast wants to have butter, jam or have the toast
sliced?
© paullong.net 2020 Page 4 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Instructions must be accurate. If there are any errors, then the algorithm will not be
successful. In the example above, instruction number 4 specifies one slice of
bread and instruction number 2 refers to a bag of bread. These are specific
instructions that ensure the algorithm is run correctly. They also help to make sure
the algorithm is unambiguous.

Activity – human robots

Get into groups of 3. One person should be blindfolded and will act as a robot
responding only to instructions given. One person will give out the instructions to
get from one place to another (this could be within the classroom, in the corridors
or outside). The 3rd person will make notes about what went well and what went
wrong. Compare your experience with other groups.

Algorithms should always be consistent. This means that they will be run the same
every time and produce the same result every time for the same input data. The
algorithm above should work for any piece of bread being used to make toast,
but may not work for a different type of toaster.

Algorithms should be efficient. One method of efficiency is that the instructions

should solve a problem in the shortest possible time. In the example above,
instructions 7 to 9 are carried out while the bread is being cooked. If they had
been carried out after the toast had finished cooking, then the whole task would
have taken more time.

Video
Watch how these algorithms for making a jam sandwich at
http://tiny.cc/ambiguous from Philip Bagge go wrong due to ambiguous,
incomplete or inaccurate instructions. Identify the errors that the children make
with their instructions.

Activity – completing the slice of toast

1) Continue the algorithm in the example above to include buttering the slice
of toast, adding jam and slicing it into two triangles.
2) Test your algorithm on a friend by asking them to follow your instructions
precisely without trying to fill in any gaps in your instructions.

An algorithm is not necessarily a computer program, but all computer programs

are algorithms. An algorithm can be presented as a set of written instructions, as a
flow-chart, as pseudocode, as diagrams, or in a programming language if the
problem is suitable to be solved by a computer. Formulae and functions in a
spreadsheet are also algorithms. For example, =A1*A2 is an algorithm to multiply
the value in cell A1 by the value in cell A2.

© paullong.net 2020 Page 5 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – algorithm presented as a diagram

This image is taken from a flat-pack furniture instruction booklet for a bunk bed.

You can see that there are plenty of opportunities for ambiguity where the
instructions are not clear and may be interpreted differently by different people.

Maths Link – addition algorithm

Algorithms are used to solve many problems in maths. Have a look at the following
multi-column addition problem.

The algorithm for the right most column is:

1) Add numbers in right most column together.
2) If the answer is a single number, write it down
under the column
3) If the answer is a two digit number, write the
units digit under the column and the tens digit
above the next column to the left.

These instructions are then repeated for every column.

Extension: Read the example of Euclid’s Algorithm for finding the greatest
(largest) common factor at http://tiny.cc/euclids

© paullong.net 2020 Page 6 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Decomposition

Note: This section could be taught alongside

subroutines in Chapter 6. Small
Small Solution
Decomposition is about breaking down a problem into Solution 2
1
smaller problems that are easier to manage. Edexcel
describe decomposition as: Small
Solution
3
“breaking a complex problem down into a
number of sub-problems, each of which
accomplishes a specific task”.

Whole Solution

Video
Watch the decomposition video http://tiny.cc/decompose from BBC Teach.
Make a list of the smaller problems involved in going shopping that you see during
the video.

Example – cleaning teeth

Start by identifying the tools that are needed: toothpaste, toothbrush and water.

Next think about the smaller solutions that need to take place:
Getting equipment
Get toothbrush
Get toothpaste
Find water
Putting toothpaste on toothbrush
Clean toothbrush
Squeeze toothpaste
Cleaning teeth
Scrubbing teeth
Spitting out toothpaste
Swilling mouth with water
Spitting out water
Putting equipment away
Put toothbrush away
Put toothpaste away

© paullong.net 2020 Page 7 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

This could be also be represented as a diagram:

Clean Teeth

Put toothpaste Put equipment

Get equipment Cleaning teeth
on tooth brush away

Clean Put toothbrush

Get toothbrush Scrub teeth
toothbrush away

Squeeze Spit out Put toothpaste

Get toothpaste
toothpaste toothpaste away

Swill mouth
Find water
with water

Spit out water

Some of these solutions can be re-used. Spitting out toothpaste and spitting out
water will include the same actions. Finding water could be used to solve part of
another problem too.

Benefits of using decomposition include:

✓ each smaller problem is a smaller problem that is easier to solve than the
whole problem.
✓ each smaller problem can be solved independently of the whole problem.
✓ each smaller algorithm can be tested independently.
✓ the algorithms for the smaller problems can be combined to solve the whole
problem.
✓ some smaller algorithms could be repeated within the solution for the whole
problem.
✓ some smaller algorithms could be re-used to help solve other problems.
✓ different people can work on solving different smaller problems.

© paullong.net 2020 Page 8 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – decomposition
1) Use Google Maps to find cycling directions from Dragonfly Pool in
Birmingham to Little Aston Golf Club. Notice how you are presented with
different options. Click on Details for the option that goes through Sutton
Coldfield and Sutton Park. Notice how the problem has been decomposed.

2) Using a map, but without using a route finder, write down the directions to
drive, walk or cycle from your school to home.

3) Decompose two of the following problems into smaller problems. One

should be done as a list and the other using a diagram as shown in the
example above.
a) Cook a roast meal
b) Plan a dinner party
c) Put the rubbish out for collection
d) Hang a cabinet on the wall
e) Get dressed
f) Mow the lawn
g) Sew a button onto a shirt
h) Another problem of your choice

Maths Link – decomposition

How much does it cost to
produce this necklace?

Identify the cost of each part:

big beads
medium beads
small beads
end beads
coupling
cord
Count how many of each bead.
Multiply the cost of each bead
by the number of each beads.
Add the costs of all the beads.
Add the cost of other items.

Each of the smaller problems

above can be solved separately
making the whole problem easier
to understand.

© paullong.net 2020 Page 9 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Abstraction
Abstraction is the process of making a complex problem easier to understand by
focusing only on necessary information. It is important to identify which information
is necessary and ignore the information that is not necessary. Edexcel describe
abstraction as:

“removing any unnecessary detail from a problem in order to reduce its

complexity and make it easier to solve.”

Video
Watch this video http://tiny.cc/abstraction about abstraction from Robotics
Academy.

Abstraction involves:

• identifying information required for a solution

• ignoring information that is not required for a solution
• hiding unnecessary detail

Example – London Underground map

This is part of the London Underground map:

© paullong.net 2020 Page 10 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Notice the information that is included:

Lines (eg red for Central line)
Underground stations
Underground stations that are interchanges for other lines
Disabled access
Car parks
Railway stations
River crossings

What information is not included though?

Distance between stations
Travel times
Street map
Bus routes
Tourist attractions

If the information above was included then the map would be far too
complicated to read and understand. The image below is an original
underground map from 1908.

© paullong.net 2020 Page 11 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

In this map, the distances between stations are represented to scale and you can
see how difficult it is to fit in all the detail for stations in the centre of London. As a
result, some of the stations at the ends of the lines have been omitted.

In 1933, Harry Beck designed the modern tube map which ignored detail such as
the distances between stations, streets, places of interest and the true direction of
travel. This was a method of abstraction to make the map easier to understand.

Have a look at the animation between the abstracted tube map and the physical
tube map at http://tiny.cc/tubeanimation or use the file London Underground
Map Extraction.mp4

Video
Watch this video http://tiny.cc/tubemap about how Harry Beck designed the
modern underground map from Jill Britton.

Activity – abstraction of maps

1) Use Google Maps to find a driving route from Durham to Sunderland.
a) What features are included in the map?
b) What features do you think have been hidden from the map?

2) Change the destination to be Sunderland Museum & Winter Gardens. Zoom

in on the map to the destination.
a) What additional features can you now see on the map?
b) Why do you think these features were hidden for the route map?

3) Try zooming out one step at a time.

a) What features are hidden each time you zoom out?
b) Why do these features need to be hidden each time you zoom out?

4) Zoom back in and add Pegman (the little yellow man used for Streetview) to
Borough Road outside the destination.
a) What additional features are now shown?
b) Which of these could help in finding the destination?
c) Why wouldn’t Street View be useful for the whole journey?

5) Look at the underground map in the example above. The Piccadilly Line
(dark blue) is closed. An able-bodied person needs to travel from Holburn to
Green Park.
a) What information is needed?
b) What information can be ignored?

© paullong.net 2020 Page 12 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Video
Watch http://tiny.cc/abstraction2 about how abstraction relates to computer
algorithms from BBC Teach.

A computer programmer will understand how to write code to solve a problem

but does not need to understand how the detail of how the hardware stores and
processes the data. A user of the program will understand how to use the
program but does not need to understand how the program was created.

Activity – truth or lie?

A blue robot which can walk, talk and climb stairs
only tells the truth on Monday, Wednesday and
Friday and always lies on all other days of the
week. Today he says: “Tomorrow I will tell the
truth."

What day is it today?

a) Tuesday
b) Friday
c) Saturday
d) Sunday

What information is necessary and what

information is unnecessary to solve this problem?

What is the answer to the problem? How did you work it out?

© paullong.net 2020 Page 13 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – frog puzzle

Six frogs are sitting on rocks. Frogs can jump from one rock to another adjacent
empty rock, or they can jump over one frog to an empty rock, but they can’t jump
over more than one frog. The frogs can only jump forwards. Send the ABC frogs to
the right-hand side of the pond and send the xyz frogs to the left-hand side of the
pond. How many moves does it take?

What information is necessary and what information is unnecessary to solve the

problem?

What is the answer to the problem? You can use the interactive puzzle at
http://tiny.cc/frogs to help solve the problem.

Extension: find a rule (algorithm) to work out the minimum number of moves
needed for any number of frogs on each side.

Pattern recognition
Pattern recognition involves following the process of abstraction and
decomposition to try to identify patterns that will help to solve problems.

Video
Watch http://tiny.cc/patternrec about pattern recognition from BBC Teach.

© paullong.net 2020 Page 14 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – jigsaw
To complete this jigsaw, a child will look for patterns.

These patterns will include:

Corner pieces
Edge pieces
Centre piece
Matching colours
Body parts

This will help a child to complete the jigsaw puzzle.

More complex problems may include repetitive patterns. It is useful to be able to

identify patterns that repeat because the solution for that part of the problem only
needs to be identified once and then it can be repeated. That part of the
problem may also exist in another problem and so the solution could be re-used.

Example – repetitive patterns

Imagine you are going shopping.
Here is part of your shopping list:

Halloumi Ketchup Sausages

Water Wraps Crisps
Salad Burgers Coleslaw
Chicken Napkins Mayonnaise
Salmon Juice

Following this list at the supermarket

would mean making several trips up
and down the aisles. Pattern
recognition would help to group the
items into categories so they can be
found easily at the supermarket:

© paullong.net 2020 Page 15 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – pattern recognition

1) A magic word is needed to open a box. A secret code assigns each letter
of the alphabet to a number.

15 26 7 7 2 18

a) What is the magic word?

i) LOOSER ii) WINNER iii) LOTTOS iv) TICKET

b) Explain how you solved this problem using pattern recognition.

2) A pearl bracelet is worn by a lady. After it has

been worn, it is unfastened and put into a
jewellery box. The next day, the lady wants to
wear the same bracelet, but there are many
similar bracelets in the jewellery box.

a) Which bracelet should the lady wear?

i) ii)

iii) iv)

b) Explain how you solved this problem using pattern recognition.

© paullong.net 2020 Page 16 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

3) A robot is sent on a mission in space to find

an artefact hidden in this maze. The
instructions have been given as alien words.
You know that aliens use a different word for
each of:
Move one space north
Move one space south
Move one space east
Move one space west

a) Which set of instructions should the robot follow:

i) Ha', Ha', poS, Ha‘ ii) Ha', poS, poS, Ha‘, nIH, Ha’
iii) Ha', poS, poS, Ha‘, Ha’, nIH iv) Ha', poS, nIH, vI’ogh, Ha’,poS

b) Explain how you solved this problem using pattern recognition.

Activity – Beaver Computing Challenge

Try using pattern recognition to solve some other puzzles from past challenges at
www.bebras.uk or the Beaver Computer Challenges http://tiny.cc/beavercc from
the University of Waterloo Beaver Computing Challenge. There are different levels
of challenge dating back to 2012.

How about entering this year’s Bebras Challenge? Your school can register at
www.bebras.uk

© paullong.net 2020 Page 17 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Problem solving

Pseudocode
Pseudocode looks a bit like the English language but has some structure to it.
Pseudo means ‘fake’ and so pseudocode is ‘fake code’. Pseudocode is one way
of writing instructions for an algorithm. There is no single correct solution for writing
pseudocode – it just needs to make sense, be clear and unambiguous. Edexcel
define pseudocode as:

“an informal written description of a solution that uses imprecise English

language statements and does not require the use of any specific
command words or syntax.”

Video
Watch http://tiny.cc/pseudo-code about pseudocode from TED-Ed. You will
notice there is also some pattern recognition involved.

Example – structured English

Pseudocode can look like an unstructured version of programming code or
structured English can be used too. E.g. how to calculate a standard black cab
fare in London in 2013:

Charge £2.40 initially

After 254.6 metres REPEAT
charge an additional £0.20 for every 127.3 metres
UNTIL fare is £17.20
Charge £0.20 for each additional 89.2 metres.

This pseudocode represents an algorithm for starting a car

Put key in ignition

Check gear stick is in neutral
Turn key
If engine doesn’t start, apply pressure to the accelerator
until engine starts

© paullong.net 2020 Page 18 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – pseudocode
Using your own structured English or pseudocode, write algorithms for the
following:
1) Hang a picture on the wall.
2) Charge a mobile phone fully.
3) Cross a road.
4) Calculate entrance price to a theme park - £45 for adults, £30 for children
under 16, £5 for children under 4 and £15 for OAPs. There is a discount of
10% if purchased online.

Note: In an exam, you can use your own version of pseudocode as long as it
makes sense to another person. Edexcel do not have a standard way of
presenting pseudocode to you in an examination. However, you should be
familiar with all the commands used in Edexcel’s Programming Language
Subset (PLS) of Python which will be used in programming questions for
Paper 2. The PLS is not pseudocode but a subset of the Python
programming language.

Example – pseudocode
This example of pseudocode calculates the body mass index (BMI) of a person.
This pseudocode is structured and looks similar to a programming language. It is
not necessary for pseudocode to be structured with syntax like this, as long as it is
clear and unambiguous.

SEND “Please enter your weight in kilograms:” TO DISPLAY

RECEIVE weight FROM (REAL) KEYBOARD
SEND “Please enter your height in metres:” TO DISPLAY
RECEIVE height FROM (REAL) KEYBOARD
SET bmi TO weight / height / height

IF bmi < 18.5 THEN

SET description TO “underweight”
ELSE IF bmi < 25 THEN
SET description TO “healthy”
ELSE IF bmi < 30 THEN
SET description TO “overweight”
ELSE
SET description TO “obese”
END IF

SEND “Your BMI is“, bmi, “which is“, description TO DISPLAY

© paullong.net 2020 Page 19 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Video
Watch this video http://tiny.cc/pseudokhan which shows a different approach to
using pseudocode from Khan Academy.

Flowcharts
So far, we have only written instructions for algorithms. Flowcharts can represent
algorithms graphically using a set of symbols.

These are some of the symbols that can be used within a flowchart:

Symbol Meaning
Terminator used at the start and end of a flowchart to
indicate the start and end of an algorithm. The
terminator must always include the word START at the
beginning and STOP or END at the end. The only
exception is a loop that continues forever which does not
need a STOP terminator.

Process used to represent a process that needs to be

carried out in the algorithm, such as an instruction.

Input or Output representing data that is needed as an

input to the algorithm or data that is output from the
algorithm.

Subprogram or subtask that is called to run.

Connects the symbols showing the direction of flow

through the flowchart.
Decisions are used for selection and iteration (see
chapter 2). A question can be asked which will have
response. The response will determine which direction to
take next in the flowchart.

Note: the colours used above are just for illustrative purposes. Colours are not
necessary in a flowchart.

© paullong.net 2020 Page 20 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

There are lots of tools that you can use to draw flowcharts, including a pencil and
ruler or a pencil and stencil. If you are looking for an online tool then
https://www.draw.io/ is simple to use and moves symbols and arrows around
together. You can also save flowcharts to the cloud or locally. The symbols used
in the table above can be found in basic flowchart symbols.drawio which can be
opened in draw.io using either the online or installed version. In this
chapter, draw.io has been used to create most flowcharts and all files
are in the examples folder, but to show that other tools can also be
used, Microsoft Visio has been used to create some flowcharts too.

Example – changing gear in a car

Start terminator Arrows showing Processes that Stop terminator
direction of flow include actions

The algorithm above has a start and an end but there are no decisions. This is
known as a sequence of instructions.

Rules for flowcharts:

• generally drawn from top to bottom, but left to right is OK too
• all shapes must be connected with an arrow
• a terminator must be used at the start and the end of the flowchart, unless
the sequence is a loop that continues forever in which case a STOP
terminator is not required
• decisions have responses which must be labelled

© paullong.net 2020 Page 21 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Selection algorithms require a decision to be

made and include the decision symbol. Each
option must lead to another part of the
flowchart.

Question that is asked to decide

which route to take.

If the answer to the question is “No” then the

No route will be followed and Process 2 will
run.

If the answer to the question is “Yes”, then the

Yes route will be followed and Process 3 will
run.

Example – getting dressed

This simple selection algorithm shows
the decision that needs to be made
when you get dressed in the
morning. The decision is a question
which is to ask yourself “is it a school
day”. If it is, then you will wear your
school uniform. If it isn’t, then you will
wear casual clothes.

You could extend this further to have

another question asking whether it is
a ‘non-uniform’ day.

© paullong.net 2020 Page 22 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Iterative algorithms also require a decision to be made but the outcome of the
decision will enable processes to repeat.

Decisions can be precondition or postcondition. Precondition means that the

decision is taken before any iterations take place and would be implemented in
programming code as a while loop. Postcondition means that the decision is
taken after each iteration takes place and would be implemented in
programming code as a repeat … until loop.

Here is a precondition loop:

This is the process that will repeat if the answer to the

question is “yes”.

This is the question that is asked. If the answer is “yes”, the

iteration starts. If the answer is “no”, the algorithm ends.
Note that the yes and no answers could also be the other
way around.

Example – precondition - password

This precondition loop checks if
a password is correct. A
process takes place that asks
the user for a password before
the iteration begins.

The question that is asked is

whether the password is
correct. It is asked before any
iteration takes place. If it is
correct, then the algorithm
ends. If it is not correct, then
the user is presented with an
error message and asked for
their password again. This will
continue in a loop while the
password is incorrect.

© paullong.net 2020 Page 23 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Here is a postcondition loop:

This is the process that will repeat if the answer to the

question is “no”.

This is the question that is asked. If the answer is “no”,

the process repeats. If the answer is “yes”, the algorithm
ends. Note that the yes and no answers could also be
the other way around.

Example – postcondition - password

This postcondition loop also checks if a password
is correct. The first iteration takes place before
any decision is made. In this case, the first
iteration asks the user for their password.

The postcondition question that is asked is

whether the password is correct.

It is asked after the first iteration took place. If it is

correct, then the algorithm ends.

If it is not correct, then the loop is repeated and

the user is asked for their password again. This
will continue in a loop until the password is
incorrect.

This algorithm could be improved by presenting

the user with an error message is their password
is incorrect.

© paullong.net 2020 Page 24 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – countdown
Flowcharts are used for programming concepts
such as sequence, selection and iteration in
chapter 2. In this chapter, the focus is just on
the use of flowcharts for everyday algorithms,
but this is an example of an algorithm that
could be represented as a computer program.

This algorithm asks the user how many numbers

they want to countdown. The user gives an
answer, eg 10. The algorithm then displays the
value (eg 10), and reduces the value by 1. If it
has reached 0, it stops. If it hasn’t reached 0,
then it displays the new value, eg 9 and keeps
repeating this until the value is 0.

Notice how the INPUT/OUTPUT symbol can be

used when drawing a flowchart for a computer
program.

Pseudocode

display “How many numbers do you want

to countdown?” on the screen
accept counter as input
repeat
display counter on the screen
decrease counter by 1
until counter = 0

Algorithms may just include sequence, or they may include selection and may also
include iteration. When lots of decisions need to be made, the algorithm can
become quite complex. Looking at the algorithm visually as a flowchart can help
to understand the purpose of the algorithm and how it works.

© paullong.net 2020 Page 25 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – snap
This algorithm for
a game of snap
uses all of
sequence,
selection and
iteration.

Player 1 and
Player 2 playing
their cards are
processes in
sequence.

Deciding whether
the cards match
or not are
selection but the
‘no’ route enables
iteration to take
place of the
players playing
cards.

The end of the

game is
determined by a
decision. If a
player has run out
of cards, then the
end of the game
has been
reached.

© paullong.net 2020 Page 26 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – central heating

This is a classic example of an iterative
loop. It is for a central heating system
that is constantly running. The
question that is asked is whether the
temperature is less than 21o Celsius. If
it is, then the heating is turned on and
the question is asked again. If it is not,
then the heating is turned off and the
question is asked again.

You could extend this further to have

options for the time of day, setting the
temperature, and manually turning
the heating off.

Activity – flowcharts
Draw flowcharts to represent algorithms for the following:
1) Hang a picture on the wall.
2) Charge a mobile phone fully.
3) Cross a road.
4) Calculate entrance price to a theme park - £45 for adults, £30 for children
under 16, £5 for children under 4 and £15 for OAPs.

You may find it useful to refer to the pseudocode you wrote form the previous
activity.

Questions – follow me
1) a) Define the term algorithm. [2]
b) Explain why an algorithm must be accurate and consistent? [2]

2 a) Define the term decomposition. [2]

b) Describe three advantages of decomposition. [3]

3 a) Define the term abstraction. [1]

b) Give three examples of unnecessary detail on a map when planning a
journey by train. [3]

© paullong.net 2020 Page 27 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

2) Understanding algorithms

Input, process and output

INPUT PROCESS OUTPUT

STORAGE

This is a diagram that that is fundamental to computing. Here is a basic overview

of this diagram:

• data is input into a computer system

• that data is then processed
• the data may be stored either during or after processing
• data might need to be retrieved from storage
• information is output by the computer system

Example – inputs and outputs

This is the way in which all information processors work. Each of the following
devices accept data inputs, and then process that data into outputs.
Device Inputs Outputs
Alarm Clock Current temperature Alarm sound
Current weather Current time
Alarm time set using Alarm set time
buttons Temperature as a
Current time (maybe number
from radio signal) Image of weather
Thermostat Current room Current temperature as
temperature a number
Preferred room Current time
temperature set using Time of next mode
up and down buttons change
Times to turn heating on Turn heating on or off
and off using buttons

© paullong.net 2020 Page 28 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

The input, process and output for one set of input and output data for the
thermostat could be shown as:

Current
Decide if it is Turn heating on
temperature in
too hot or cold or off
room

Temperature
set by user

The process could be broken down into a flow chart like in the central heating
example seen earlier.

Activity – inputs and outputs

1) For each of the following devices, identify the input data they might receive
and the output data they might produce.

a) Fitness Tracker b) Mobile Phone

c) Car

2) For each device above, draw one input, process and output diagram to
show how one set of input data is processed into an output.

© paullong.net 2020 Page 29 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

The same diagram can be applied to a desktop computer system.

Example – scanning a document

A document is scanned into the computer. It is turned into an image which is
saved on the hard disk and then displayed on the screen.

Scan document Image file

Document
and save displayed on
(INPUT)
(PROCESS) screen
(OUTPUT)

Image file on
hard disk
(STORAGE)

A formula or function in a spreadsheet is an example of how input data (a

variable) can be processed into output data (answer to formula or function).

Formula or
Variable Data Answer
Function
(INPUT) (OUTPUT)
(PROCESS)

Example – spreadsheet
The input data here are 5 for the
width and 3 for the length. The
output is 15 for the area.

A process took place to turn the input

into an output. The process was
=B1*B2 to multiply the width by the
length.
In an input, process output diagram, this would be represented as:

B1 = 5
B1*B2 15
B2 = 3
(PROCESS) (OUTPUT)
INPUT

Activity – spreadsheet input and output

Complete the activities in Input & Output.xlsx to see if you can work out what the
process is.

© paullong.net 2020 Page 30 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

You should to be able to describe simple algorithms in terms of their inputs,

processing and outputs.

Example – countdown
This is an example you have seen before in both
flowchart and pseudocode form.

Pseudocode

display “How many numbers do you want to

countdown?” on the screen
accept counter as input
REPEAT
display counter on the screen
decrease counter by 1
UNTIL counter = 0

The input is:

• <counter> (number of numbers)

The outputs are:

• “How many numbers do you want to
countdown?”
• <counter> (displayed each time through
the loop)

The processes are:

• Reduce <counter> by 1
• Repeat if counter not = 0

Activity – describing algorithms

1) Identify the inputs, processes and outputs for each of the following
algorithms:
a) c = int(input("Please enter a number: "))
d = c * 5
e = c + 4
f = d - e
print(f)

© paullong.net 2020 Page 31 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

b) def initials(forename, surname):

initialf = forename[0]
initials = surname[0]
result = initialf + initials
return result
#end initials
print(initials("Paul", "Long"))

2) Describe the algorithms below in terms of their inputs, processes and outputs:
a) def subname(s, t):
if s > t:
result = True
else:
result = False
#endif
return result
#end subname
print(subname(5, 4))

b) authenticated = False
while not authenticated:
username = input("Enter username: ")
password = input("Enter password: ")
if username == "LongPA" and password == "letmein":
authenticated = True
print("Welcome.")
else:
print("Username and password wrong. Try again.")
#endif
#endwhile

c) number_students = int(input("How many students do you

have? "))
number_tests = int(input("How many tests are there? "))
marks=[]
for student in range(number_students):
marks.append([None]*number_tests)
for test in range(number_tests):
marks[student][test] = int(input("Please enter
mark for student number " + str(student) +
" test number " + str(test) + ": "))
#next test
#next student
print(marks)
© paullong.net 2020 Page 32 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Understanding the purpose of an algorithm

You need to be able to work out what an algorithm does, how it works and what
its purpose is. By understanding the inputs, processes and outputs, you are already
making a good start at understanding how an algorithm works.

Understanding the purpose is about knowing what the algorithm does.

Example – algorithm to make toast

Here is an algorithm we have seen before:

1) Open the bread bin door

2) Pick up the bag of bread
3) Open the bag of bread
4) Take one slice of bread from the bag
5) Place slice of bread vertically into toaster
6) Pull the lever down on the toaster
7) Close bag of bread
8) Put bag of bread back in bread bin
9) Close the bread bin door
10) Wait for toast to pop up out of toaster
11) Remove toast from toaster

It is quite clear that the purpose is to make a single slice of toast.

The example above is quite simple and straightforward. However, look at some of
the other algorithms you have seen as examples earlier in this chapter such as
changing gear in a car, the snap game, countdown and central heating
algorithms and it is not so obvious what the purpose of the algorithm is.

With more complex algorithms, it is necessary to look in detail at what is

happening, what data is being used, how it is being modified and what selection
and iteration processes are used.

© paullong.net 2020 Page 33 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – purpose of algorithm 1

You could be asked to describe the purpose of the following algorithm:

import random
y = int(input("Please enter largest number: "))
z = random.randint(0, y)
i = -1
while i != z:
i = int(input("Please enter number: "))
if i == z:
print("Well done")
elif i < z:
print("Higher")
else:
print("Lower")
#endif
#endwhile

You need to decompose the problem by looking at each stage and the inputs,
outputs and processing. Work through the algorithm from beginning to end and
replace variables with descriptions of what data the variable holds.

The user is asked to enter a number and it is assigned to <y>

y = int(input("Please enter largest number: "))

A random number is generated between 0 and the user’s choice of largest

number <y> and assigned to <z>.
z = random.randint(0, y)

The user is asked to enter another number which is assigned to <i>. The whole
process repeats while the new number chosen by the user <i> does not match
the random number <z>.
i = -1
while i != z:
i = int(input("Please enter number: "))
.....
#endwhile

If the new number chosen by the user matches the random number then the user
is told “Well done” and the loop ends.
if i == z:
print("Well done")

© paullong.net 2020 Page 34 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

If the new number chosen by the user is less than the random number then the
user is told “Higher” and the loop continues until the user chooses a number that
matches the random number.
elif i < z:
print("Higher")

If the new number chosen by the user is bigger than the random number then the
user is told “Lower” and the loop continues until the user chooses a number that
matches the random number.
else:
print("Lower")

The purpose of the algorithm is that the user chooses what the largest random
number can be. The user must then guess what the random number is until they
get it correct. To help the user, they are given clues as to whether the random
number is higher or lower than their guess.

It is the last paragraph that is the answer to the question. The rest of the example
was how you would have gone about understanding the problem in your head or
by making notes.

Example – purpose of algorithm 2

You could be asked to describe the purpose of the following algorithm:

def subr(z, y):

result = 1 result will always be 1 if y is 0
if y > 0:
for i in range(1, y + 1): when y is 1, result will be z * 1
result = z * result
#next i when y is 2, result will be z * z * 1
#endif
when y is 3, result will be z * z * z * 1
return result
#end subr

print(subr(2, 5))

The answer is that the purpose is to calculate z to the power of y. The reason for
the IF statement is in case the power y is 0 in which case the answer will always be
1.

© paullong.net 2020 Page 35 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – purpose of algorithms

Describe the purpose of each of the following algorithms?

1) def subr(a, b):

if a > b:
result = a
elif a < b:
result = b
else:
result = 0
#endif
return result

print(subr(5, 5))

2) a = "hello"
b = "goodbye"

if len(a) < len(b):

while len(a) < len(b):
b = b[0:len(b)-1]
#endwhile
elif len(b) < len(a):
while len(b) < len(a):
a = a[0:len(a)-1]
#endwhile
#endif

3) def subr(x):
result = ""
for i in range(len(x) - 2):
result = result + x[i] + ","
#next i
result = result + x[i+1] + "."
return result
#end subr

print(subr("Blobby"))

Extension: Write a single line of code to replace the first WHILE loop
and another for the second WHILE loop in question 2 to
make the code more efficient.

© paullong.net 2020 Page 36 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Trace tables
Trace tables are used to test the logic of an algorithm. They can help to identify
any errors in the logic or confirm that the algorithm is working as it is intended to.

A trace table may include a row for each line of code where the values of
variables could change or a new row may only be used when there is no more
space in the current row. It will also include a column for each variable. If there
are any outputs then an output column should also be used. You can then trace
through an algorithm by writing down the value of each variable during each line
of code.

Example – trace table for a sequential algorithm

Complete a trace table for the following algorithm when x is 5 and y is 7:

1 def subr(x, y): 1 x starts as 5, y starts as 7

2 a = x * y 2 a becomes result of x * y which is 35
3 p = 2 * (x + y) 3 p becomes result of 2 * (x + y) which is 24
4 result = [a, p] 4 the result becomes an array of a and p which
5 return result will be [35, 24]
6 #end subr 5 the value of result [35, 24] is returned

Working through this one line at a time gives the following results:

Line x y a p result RETURN

1 5 7
2 35
3 24
4 [35, 24]
5 [35, 24]

Alternative answer using only one row and no line numbers:

x y a p result RETURN
5 7 35 24 [35, 24] [35, 24]

Use the trace variables visualisation tool at http://tiny.cc/tracevariables to watch

what happens to the value of the variables as each line is executed. This example
has been set up for you at http://tiny.cc/ttforaseqalgorithm to include the code
and the input of enter. Note that this visualisation does not retain previous values
like a trace table would but only shows the new value of each variable. You can
use this tool for any Python code.

Notice in the example above how it is only necessary to record when the value of
a variable changes. It is not necessary to repeat its value if it has not changed.
© paullong.net 2020 Page 37 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – trace table using selection

Complete a trace table for the following algorithm.

1 a = 20 1 initial value of a is set

2 b = 30 2 initial value of b is set
3 if a == b: 3 do not follow this route
4 to 5 – ignore
4 a = 0
5 c = "equal"
6 elif a > b: 6 do not follow this route
7 a = b 7 to 8 - ignore
8 c = "bigger"
9 else: 9 follow the else route
10 b = a 10 b becomes a which is 20
11 c = "smaller" 11 c becomes “smaller”
12 #endif
13 a is still 20
13 print(a)

Working through this one line at a time gives the following results:
Line a b c OUTPUT
START 20 30
10 20
11 “smaller”
13 20

This is what the trace table would look like:

a b c OUTPUT
20 30
20 “smaller” 20
Once you have started using a new line in the trace table (e.g. value of 20 for b)
then it is best to continue on that new line as it shows the order of events.

When an algorithm uses selection, there is often a lot to ignore because certain
routes are not followed.

Trace tables are most useful for algorithms that use iteration because it allows you
to see the changes in variables through each iteration.

Video
Watch this video about creating trace tables http://tiny.cc/tracetables

© paullong.net 2020 Page 38 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – trace table using iteration

Complete the trace table for the following algorithm when z is 2 and y is 4:

1 def subr(z, y): 1 z starts as 2, y starts as 4

2 result = 1 2 result becomes 1
3 if y > 0: 3 y (8) is > 0
4 i starts as 1 and will end at 4
4 for i in range(1, y+1):
5 result becomes 2 * 1 = 2
5 result = z * result
6 repeat lines 4 to 5 another 3 times
6 #next i
7 #endif
8 return result 8 result is 16
9 #end subr

Working through this one line at a time gives the following results:
Line z y i result RETURN
1 2 4
2 1
4 1
5 2
4 2
5 4
4 3
5 8
4 4
5 16
8 16

This is an example that has been used before for describing the purpose of the
algorithm. Notice how using a trace table makes it easier to understand what the
algorithm is doing.

This is what the trace table should look like:

Iteration z y i result RETURN
- 2 4 1
1 1 2
2 2 4
3 3 9
4 4 16 16

Notice that a new line has been used for each iteration of the FOR loop. This
makes it easier to spot where errors might occur in a program and to refer back to
each iteration.

© paullong.net 2020 Page 39 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – trace table for an algorithm that uses iteration

Visit http://tiny.cc/trace-iteration and watch the animation for creating a trace
table for an iterative algorithm. Then complete the challenges. There are further
code breaking challenges at http://tiny.cc/trace-code-break for you to try.

Note: although the Computing 101 website uses a separate line in the trace table
for each line of code, this is not necessary in exams.

Trace tables are also useful when tracking the values within an array. When
creating a trace table that includes an array, create a separate column for each
position within the array and group those columns together:

Array Name
0 1 2 x

Video
Watch this video http://tiny.cc/trace-array from Mr AI Teacher to see how a trace
table can be used in an array.

Example – trace table using an array

Complete the trace table for the following algorithm:

1 x[0] is 1, x[1] is 3, x[2] is 7

1 x = [1, 3, 7]
2 z becomes length of x = 3
2 z = len(x)
3 i starts as 0
3 for i in range(0,z):
4 x[0] becomes 1 * 5 = 5
4 x[i] = x[i] * 5
5 lines 3 and 4 repeated for
5 #next i i = 1 and i = 2
6 print(x[2] + x[1] + x[0]) 6 Output is 5 + 15 + 35 = 55

The trace table below starts a new line for each iteration. This makes it easier to
follow what is happening each time the FOR loop runs.
x
Iteration 0 1 2 z i OUTPUT
- 1 3 7 3
1 5 0
2 15 1
3 35 2
- 55

© paullong.net 2020 Page 40 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Exam questions tend to ask you to produce a trace table for an algorithm
represented in the Python programming language. However, there may be
occasions when you are asked to produce a trace table for an algorithm
expressed in another format such as a flowchart.

Video
Watch this video http://tiny.cc/trace-flow from Liam McQuay about how trace
tables can be used to trace an algorithm represented by a flowchart.

Debuggers in an IDE (Integrated Development Environment) often include a

watch feature which displays the values of variables while a program is being run.
The step feature can be used to run through the code one line at a time which
means that the watch feature is acting a bit like a trace table.

Activity – trace tables

1) Complete the trace table for the algorithm below when a is 25 and b is 25.

def subr(a, b):

if a > b:
result = a
elif a < b:
result = b
else:
result = 0
#endif
return result
#end subr
a b result RETURN

2) Complete the trace table for the algorithm below when a is “Hi” and b is
“Hello”. Add extra rows that you are likely to need.
if len(a) < len(b):
while len(a) < len(b):
b = b[0:len(b)-1] # this could be written b[0:-1]
#endwhile
elif len(b) < len(a):
while len(b) < len(a):
a = a[0:len(a)-1] # this could be written a[0:-1]
#endwhile
#endif
Iteration a b len(a) len(b)
-

© paullong.net 2020 Page 41 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

3) Complete the trace table for the algorithm below when x is [“A”, “B”,
“C”, D”]. Add extra rows that you are likely to need.

def subr(x):
result = ""
for i in range(0, len(x) – 1):
result = result + x[i] + "-"
#next i
result = result + x[i+1] + "."
return result
# end subr
x
Iteration 0 1 2 3 i len(x) - 1 result RETURN

4) Create a trace table for the algorithm below.

x = [500, 100, 50]

z = len(x)
for i in range(0,z):
x[i] = x[i] + 25
#next i
print(x[0] - x[1] - x[2])

© paullong.net 2020 Page 42 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Evaluating algorithms
Have you heard of the saying “there is more than one
way to crack an egg”? This is often used to mean
“there is more than one way to solve a problem”.
Each morning you need to get to school. There are
several ways you could do this: you could walk, go by
car, go by bus, catch a train or cycle. Each method
will solve the problem of getting to school.

Activity – London Underground

Study the London Underground map below:

1) How would you get from Kings Cross to Waterloo? Is there another way?
2) How would you get from Knightsbridge to Liverpool Street? Is there another
way?
3) Compare your answers with others in your class. Are they all the same?
4) Use www.tfl.gov.uk to search for journeys from Euston to Westminster.
Compare the different journey options. Try changing some of the settings
such as Tube only.

© paullong.net 2020 Page 43 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

From the examples above, some methods will be more efficient than others. If you
do not live close to a train station or your school is not close to a train station, then
catching the train would not be very efficient as it would take a very long time. If
you live 5 miles away from your school, then walking may not be as efficient as
catching the bus, although it would be good exercise. Although different
problems have different solutions, some are more efficient than others.

Example – London Underground

One option to travel from Euston to Westminster is the Northern Line from Euston,
change at Embankment, then the Circle or District Line to Westminster. This will
take about 8 minutes. You could also take the Victoria Line to Green Park, then
the Piccadilly line to Piccadilly Circus, then the Bakerloo line to Embankment and
then the Circle or District Line to Westminster. This would take a lot longer than 8
minutes.

In the example above, both solutions work. It is important when comparing

algorithms to check that each solution works as otherwise the algorithm does not
solve the problem.

A more efficient algorithm will complete more quickly than a less efficient
algorithm. There are other efficiency factors that can be considered like the
readability of the code and the amount of memory required but the examples
used in this book will focus on time.

Maths Link – algorithm efficiency

There are 10 octopuses. How many legs are there in total?

You know there are 8 legs per octopus, so you could do:

8+8+8+8+8+8+8+8+8+8

But this would take you a long time and so you are more likely to calculate:

8 x 10

Examples – time efficiency

Compare the two algorithms below:
Algorithm 1 Algorithm 2
x = 0 for i in range(1,11):
x = x + 10 x = i
#next i

© paullong.net 2020 Page 44 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Both algorithms have the same result – the value of 10 is assigned the variable <x>.
However, algorithm 2 uses 20 instructions (10 times assigning <i> and 10 times
assigning <x> to complete this task whereas algorithm 1 only uses two instructions,
making it more efficient.

Compare the two algorithms below:

Algorithm 3 Algorithm 4
arr = [1,2,3,4,5] arr = [1,2,3,4,5]
i = 0 arr_len = len(arr)
while i < len(arr): i = 0
arr[i] = arr[i] + 5 while i < arr_len:
i += 1 arr[i] = arr[i] + 5
#endwhile i += 1
#endwhile

Both algorithms have the same purpose, the same result and both work – they add
5 to each element in the array <arr>. However, algorithm 3 has to calculate the
length of <arr> for each iteration, whereas in algorithm 4 this calculation only
takes place once because it is assigned to a variable <arr_len> and that
variable is then used in the WHILE loop.

Compare the two algorithms below:

Algorithm 5 Algorithm 6
myList = [] myList = []
f = open("file56.txt", "r") for i in range(0, 12):
for line in f: f = open("file56.txt", "r")
myList.append(line) myList.append(f.readlines()[i])
#next i f.close()
#next i
f.close()

Both algorithms have the same purpose, the same result, and both work – they
read a line of data from a file and assign it to a position in an array. However,
algorithm 6 has to repeat opening and closing the file for all 12 iterations.

Compare the two algorithms below:

Algorithm 7 Algorithm 8
age = 19 age = 19
if age < 2: if age < 2:
status = "infant" status = "infant"
elif age < 18: elif age < 18:
status = "child" status = "child"
elif age >= 18: else:
status = "Adult" status = "Adult"
#endif #endif

© paullong.net 2020 Page 45 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Both algorithms have the same purpose, the same result and both work. However,
algorithm 5 requires an additional process to take place to determine if the age is
greater than or equal to 18. This is unnecessary because if the age is not less than
18 then it must be greater than or equal 18 and so only ELSE is required, rather
than an ELIF which will result in a need to process the additional condition.

To reduce the completion time of an algorithm:

• remove any repetitive calculations

• remove unnecessary loops, such as if it only needs to run once
• use ELSE instead of ELSE IF if there is only one other possibility for the condition
• remove any code within a loop that doesn’t need to be repeated

It is possible to make the readability of the code more efficient, but this doesn’t
necessarily make the algorithm more efficient in terms of code. Therefore, the
following methods that can be used to make code more readable and use less
lines of code do NOT necessarily improve the time efficiency of an algorithm:

• using loops
• using subroutines
• using IF . . . ELIF rather than lots of IF . . . : . . . END statements if the same
variable is being checked

Examples – code vs time efficiency

Compare the two algorithms below:
Algorithm 9
score1 = input("Please enter score 1: ")
score2 = input("Please enter score 2: ")
score3 = input("Please enter score 3: ")
score4 = input("Please enter score 4: ")

Algorithm 10
scores = []
for i in range(1,5):
score = input("Please enter score " + str(i) + ": ")
scores.append(score)
#next i
Both algorithms complete in the same amount of time available. Algorithm 10
looks more efficient because the code is in a loop, but algorithm 1 will complete
more quickly because the variable <i> does not have to be assigned and added
to the prompt each time. Algorithm 10 is better written, but not more efficient.

You will see later in this chapter how different algorithms can be used for sorting
and searching data and how some are more efficient than others.

© paullong.net 2020 Page 46 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Questions – follow me
1 Examine the algorithm below:
weight = float(input("Please enter weight in kilograms: "))
height = float(input("Please enter height in metres: "))
bmi = weight / height / height

if bmi < 18.5:

description = "underweight"
elif bmi < 25:
description = "healthy"
elif bmi < 30:
description = "overweight"
else:
description = "obese"
#endif
print("Your BMI is", bmi, "which is", description)

a) State the purpose of this algorithm? [1]

b) Describe this algorithm in terms of its inputs, processing and outputs. [5]
c) Draw a flow chart to represent this algorithm. [7]

d) Complete the trace table below for this algorithm. You may not need to
use all rows. [2]
weight height bmi description
70 1.6

2 Study the algorithm below:

p s t OUTPUT
p = 5
s = 2
while True: #repeat
p = p + 3
s = s * 2
if p > 20: break
# until p>20
t = p + s
print(p * s)
Complete the trace table for this algorithm. You may not need to use all rows
or you may need to use more. [6]
© paullong.net 2020 Page 47 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

3) Examine the two algorithms below.

Algorithm 1 Algorithm 2
p = -3 p = -3
if p > 0: if p > 0:
result = "positive" result = "positive"
elif p == 0: elif p == 0:
result = "nothing" result = "nothing"
elif p < 0: else:
result = "negative" result = "negative"
#endif #endif

Explain why algorithm 2 is more efficient than algorithm 1 in terms of time. [2]

4) Examine the two algorithms below.

Algorithm 1 Algorithm 2
x,y,z = 3,4,50 x,y,z = 3,4,50
if (x + y) * z < 200: c = (x + y) * z
result = "P" if c < 200:
elif (x + y) * z < 1000: result = "P"
result = "Q" elif c < 1000:
else: result = "Q"
result = "W" else:
#endif result = "W"
#endif
a) State which algorithm is more efficient in terms of time. [1]
b) Explain your answer to (a). [3]

5) Examine the two algorithms below.

Algorithm 1 Algorithm 2
x = 5 z = 100
y = 20 while z != 1000:
z = 100 x = 5
while z != 1000: y = 20
z += 1 z += 1
#endwhile #endwhile

Explain why algorithm 1 is more efficient than algorithm 2 in terms of time. [2]

© paullong.net 2020 Page 48 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

6) Examine the two algorithms below.

Algorithm 1 Algorithm 2
grades = ["A", "B", "C", "D"] grades = ["A", "B", "C", "D"]
grade = input("Enter a grade: ") grade = input("Enter a grade: ")
h = len(grades) found = False
found = False i = 0
i = 0 while i < len(grades) and not
while i < h and not found: found:
if grades[i] == grade: if grades[i] == grade:
found = True found = True
else: else:
i += 1 i += 1
#endif found = False
#endwhile #endif
#endwhile

Give two reasons why algorithm 1 is more efficient than algorithm 2 in terms of
time. [4]

© paullong.net 2020 Page 49 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

3) Searching algorithms

Computers can search for data much more quickly than we can as humans.
Imagine looking up a contact in your mobile phone. Scrolling down the list might
take you a few seconds, but typing the first two letters into a search box finds the
contact very quickly.

Activity – search a text book

Use the contents page of this text book. Look for interpreting algorithms in the
contents page. Now look through the book to find the page without using any
computer search techniques.

Compare that to searching for the topic by clicking on the link in the contents
page or using the find feature of your software.

Both of the tasks above were achievable by both a computer and a human,
although the computer will have been much faster. Now imagine a bank that
needs to find a customer from a list of hundreds of thousands of customers. A
computer can find the customer in a few seconds, but a human would take
several hours if not days.

Video
Watch the video http://tiny.cc/searchBBC on searching algorithms from BBC
Bitesize.

Linear search
The linear search algorithm is a simple sequential search. It looks through a list one
data item at a time until it finds the data it is looking for.

Example – exercise books

Your maths teacher needs to find Sam’s exercise
book. She has a set of 30 books and they are not in
any order. She will look at each book in turn until she
finds Sam’s book. Here is the algorithm:

REPEAT
Look at next book
Is it Sam’s book?
If yes, then book found
UNTIL book is found OR no more books

© paullong.net 2020 Page 50 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

A computer can search for data within an array. The data the computer is
searching for will be referred to as the target.

Example – linear search

The target that is being looked for is 72. This is the array that will be searched:
Position 0 1 2 3 4 5 6
Value 20 18 64 19 72 25 4

Using a linear search, the first item in an array (position 0) will be compared with
the target. As 20 ≠ 72 then the target has not been found.
Position 0 1 2 3 4 5 6
Value 20 18 64 19 72 25 4

This process continues for positions 1, 2 and 3 where the target of 72 is still not
found:
Position 0 1 2 3 4 5 6
Value 20 18 64 19 72 25 4

The process continues again for position 4 where the value is 72. As the value
matches the target, the position in the array has been found:
Position 0 1 2 3 4 5 6
Value 20 18 64 19 72 25 4

Video
Watch this linear search video http://tiny.cc/linearsearch from Harvard University.

This is a very basic version of the Python code for a linear search:
1 for item in myArray:
2 if item == target:
3 print(target, "found")
4 #endif
5 #next item

Activity – linear search using a for loop

1) Follow the Repl or Python link above to run the basic version of the code for
a linear search and investigate how it works.
2) Run the step-by-step version to see what is happening at each stage and
see if you can find part of the code that is inefficient.
3) Try modifying the code to make it more efficient.

<target> is the item being searched for and <myArray> is the array that will be
searched to find that item.

Line 1 defines the loop which will repeat for every item in <myArray>.
Line 2 determines if <target> has been found. If <target> has been found, then
a confirmation message is printed by line 3.
© paullong.net 2020 Page 51 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Exam tip: you can use the version above in an exam for lower marks, but if you
are aiming for higher grades then you also need to be able to
understand and write the WHILE loop versions shown below.

The linear search above could be made more efficient though. Currently, it
searches through every single item in the array. Even if it finds the <target> at
position 3 out of 100, it will still continue to search the rest of the array.

Below is a modified more efficient version of the linear search which BREAKs out of
the loop if the <target> has been found. This means the search does not
continue after the <target> has been found.
1 for item in myArray:
2 if item == target:
3 print(target, "found")
4 break
5 #endif
6 #next number

Line 4 only runs if the <target> is found. Line 4 breaks out of the FOR loop so the
rest of <myArray> does not need to be searched.

Activity – linear search using break

1) Follow the Repl or Python link above to run the modified basic version of the
code for a linear search and investigate how it works.
2) Run the step-by-step version to see what is happening at each stage.
3) Try modifying the code so that it uses a while loop instead?

BREAK statements should be avoided as they can cause unpredictable results.

Below is a version of the linear search using a WHILE loop which you need to be
familiar with for exams. Note that this version only confirms if the item has been
found or not.
1 arrayLength = len(myArray)
2 found = False
3 counter = 0
4 while counter < arrayLength and not found:
5 if myArray[counter] == target:
6 print(target, "found")
7 found = True
8 else:
9 counter += 1
10 #endif
11 #endwhile

© paullong.net 2020 Page 52 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Line 1 calculates the length of <myArray> so it does not have to be calculated for
each iteration of the WHILE loop.

Line 2 sets a <found> flag to be default so the WHILE loop will run at least once.
Line 3 initialises the <counter> variable which will be used to identify the position in
<myArray> that should be checked.

Line 4 uses a WHILE loop to decide if either the end of <myArray> has been
reached and also that the <target> has not been found. This stops the loop from
continuing after the <target> has been found.

Line 5 uses the current value of counter to look at the next item in <myArray> and
compares it with the <target>. If they match, then lines 6 and 7 are run, but if
they do not match then line 9 runs which will increase the value of counter ready
for the next item in the <myArray>.

Line 6 simply states that the <target> has been found. Line 7 sets the <found>
flag to be True which means that the WHILE loop will not run again.

Activity – linear search using while

1) Follow the Repl or Python link above to run the WHILE loop version of the
code for a linear search and investigate how it works.
2) Run the step-by-step version to see what is happening at each stage.
3) Try modifying the code so that it outputs the position (index) of the <target>
in <myArray>.
4) Try modifying the code so that it lets the user know if the <target> has not
been found.

Example – linear search to see if a value exists

This program asks the user for a number and then searches for it in an array called
<numbers>.

target = int(input("What number would you like to find?"))

numbers = [15,10,12,17,18,24,29,13,21]
numbersLength = len(numbers)
found = False
counter = 0
while counter < numbersLength and not found:
if numbers[counter] == target:
print(target, "found")
found = True
else:
counter += 1
#endif
#endwhile
© paullong.net 2020 Page 53 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net
The algorithm used above does not identify the position of the <target> but only
identifies if the <target> was found or not. The linear search algorithm below has
been modified to display the position of the <target>:
1 arrayLength = len(myArray)
2 found = False
3 counter = 0
4 while counter < arrayLength and not found:
5 if myArray[counter] == target:
6 print(target, "found at position", str(counter))
7 found = True
8 else:
9 counter += 1
10 #endif
11 #endwhile
12 if not found:
13 print(target, "not found")
14 #endif

If the <target> was found then Line 6 displays the position of the <target> in the
<myArray>. If the <target> was not found, then lines 12 to 13 are used to report
this to the user.

Exam tip: you should be familiar with the code above for exams and you should
be able to write similar code if asked in an exam.

Example – trace table for linear search

Using the code above, the <target> is “F” and <myArray> is [A,Z,F,P,Q].
Iteration target myArray array found counter myArray
Length [counter]
- F [A,Z,F,P,Q] 5 FALSE 0
1 1 A
2 2 Z
3 TRUE F

Output = “F found at position 2”

Activity – linear search

1) Explain the purpose of line 9 in the algorithm above.

2) Explain how this algorithm works in terms of its inputs, processes and outputs.
3) Imagine the algorithm had to search through one million items.
a) What is the least number of iterations the WHILE loop could complete?
b) What is the most number of iterations the WHILE loop could complete?

© paullong.net 2020 Page 54 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

4) Complete the trace table below when:

a) the value of <target> is 8 and <array_name> is [7, 9, 2, 8, 4]
b) the value of <target> is 8 and <array_name> is [3, 2, 5].
Iteration key myArray arrayLength found counter myArray[counter]

5) Complete this flowchart for the linear search algorithm above that uses a
WHILE loop.

© paullong.net 2020 Page 55 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

So far you have seen the linear search being used directly within the programming
code. The linear search is likely to be re-used within a program several times and
by other programs too. It would therefore be sensible to put it into a function. If
you are aiming for the highest grades, then you should try to do this.

Example – linear search as a function

The function below is for a linear search. It takes <target> and <myArray> as
parameters and returns either the position of the <target> in <myArray> or -1 if
the <target> is not found.

def linear_search(target, myArray):

arrayLength = len(myArray)
found = False
counter = 0

while counter < arrayLength and not found:

if myArray[counter] == target:
found = True
else:
counter += 1
#endif
#end while

if not found:
counter = -1
#endif
return counter
#end linearsearch

The function can now be re-used several times. In the example below, F is being
searched for in a list of letters. The <linear_search> function is called and the
position of the item is assigned to a variable called <index>.

letters = ["A", "Z", "F", "P", "Q"]

letter = "F"
index = linear_search(letter, letters)

This final section of code checks to see if <index> was -1. If it was, then it reports
that the <letter> was not found. If it was not -1 it displays the position of the letter
in the list of letters.

if index == -1:
print(letter, "was not found in the list.")
else:
print(letter, "was found at position/index", index)
#endif

The linear search is easy to code, and it works well for a reasonably short list, but
once there are thousands of items in the list the linear search is too slow. There is
not a more efficient algorithm than a linear search when a list is unordered.
© paullong.net 2020 Page 56 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Binary search

Video
Watch this video http://tiny.cc/linear-vs-binary about the weakness of the linear
search algorithm and how the binary search algorithm overcomes this. Watch this
video http://tiny.cc/binary-CSU for a fun way of understanding the binary search
algorithm from Computer Science Unplugged

Activity – iterations of search algorithms

Having watched the first video above, if a computer was to search 4,000,000
items, what is the maximum number of iterations that would be needed to find a
data item using:
a) Linear search
b) Binary search? Tip: use a spreadsheet to help calculate the answer.

A binary search works by splitting a list into two halves. It then keeps halving the list
until the value is found. It will only work on an ordered list. To find the half way
point, the middle item in the list is found to give the left-hand side of the list and the
right-hand side of the list:

For an odd number of items in a list, the middle is the middle item so there are an
equal number of items on the left-hand side to the right-hand side as shown
below:

Position 0 1 2 3 4 5 6
LEFT-HAND SIDE OF LIST Middle RIGHT-HAND SIDE OF LIST

Remember: Unless told otherwise in an exam, indexing always starts at 0 (zero).

For an even number of items in a list, the middle is the number of items in the list
divided by two using an integer division (DIV):

Position 0 1 2 3 4 5 6 7
LEFT-HAND SIDE OF LIST Middle RIGHT-HAND SIDE OF LIST

In the list above, there are 8 items, so 8 DIV 2 = 4.

Remember: DIV 2 means divide by 2 and only use the whole number part of the
answer.

To find the middle position in a list for a binary search, always divide the (number
of items) by 2 and round down:

middle position in list = number of items DIV 2

© paullong.net 2020 Page 57 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

The middle item in an even length list can be found visually by looking at the 2
middle values and choosing the right-hand side value:

Position 0 1 2 3 4 5 6 7
middle values
left right

Note: It is also acceptable to visually use the left-hand side item. As long as you
are consistent, either method can be used. The right-hand side value works
better in programming because it is a simple calculation to do as shown
below.
In Python, the middle item in a list would be calculated as:
middle = len(array) // 2

Note: In Python, the middle position in a list using the left-hand side item would be:

middle = (start + end) // 2

Position 0 1 2 3 4 5 6
LEFT-HAND SIDE OF LIST Middle RIGHT-HAND SIDE OF LIST

For the array above, the length of the list is 7.

7 // 2 = 3.

Position 0 1 2 3 4 5 6 7
LEFT-HAND SIDE OF LIST Middle RIGHT-HAND SIDE OF LIST

For the array above, the length of the list is 8.

8 // 2 =4.

Maths Link – median

The median value in maths is different to the middle item because it represents a
value and not a position. The median position is found by the (number of items +
1) divided by 2. If this gives a half value, then the median value is the mean of the
two numbers either side of the half value.

Example: calculate the median of 1, 3, 5, 7, 11, 13, 17, 19.

Number of items = 8
8+1=9
9 ÷ 2 = 4.5 (median position)

Item 4 is 7 and item 5 is 11 (indexing starts at 1 (one) in maths)

The mean of 5 and 11 is (5 + 11) ÷ 2 = 8 (median value)

© paullong.net 2020 Page 58 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – middle and median

1) Identify the position and value of the middle item that will be used for a
binary search in each of these arrays (indexing starts at 0):
a) 1, 8, 9, 10, 11, 15, 19, 20, 35, 29
b) 7, 20, 35, 102, 108, 201, 256, 238, 242, 253, 287
c) 83, 829, 1092, 1800, 2400
d) -4, -2, -1, 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

2) To make sure you do not get confused in maths, calculate the median of
each of the above lists (indexing starts at 1). Show your working.

The binary search algorithm uses a method sometimes referred to as divide and
conquer. The middle value of a list is found to divide the list. Then the side of the
list that does not contain the target value being searched for is discarded and the
half that does contain the value is kept. The target value is compared with the
middle value. If the target value is higher than the middle value then the right-
hand side of the list is kept. If the target value is less than the middle value then
the left-hand side of the list is kept. If the target value matches the middle value
then the target value has been found. Here is one way of writing the algorithm:

• REPEAT
- IS Target Value = Middle Value?
▪ target value found
- ELSE Is Target Value > Middle Value?
▪ keep right-hand side
- ELSE (Target Value must be < Middle Value)
▪ keep left-hand side
• UNTIL target value found or no more items in list

© paullong.net 2020 Page 59 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Examples – binary search

Example 1
The target that is being searched for is 89. Here is the list that will be searched:
1 5 9 13 15 25 67 79 85 89 92 95 102 112

The middle value is the 7th item in the list (14 DIV 2 = 7) which is 67.

The target value (89) is greater than the middle value (67) so the right-hand side
of the list is kept:

Left-hand side removed 79 85 89 92 95 102 112

The new middle value is 92. 7 DIV 2 = 3.

The target value (89) is less than the new middle value (92) so the left-hand side
of the new list is kept:

Left-hand side removed 79 85 89 Right-hand side removed

The new middle value is 85. The target value (89) is greater than the new middle
value (85) so the right-hand side is kept:

LHS removed
Left-hand side removed 89 Right-hand side removed

89 is the only value left and is automatically the new middle value and as it
matches the target value (89), the target value has been found.

This took 4 iterations of the binary search to find the target value. A linear search
would have taken 10 iterations because the target value is in the 10th position.

Example 2
The target that is being searched for is 41. Here is the list that will be searched:

2 3 7 11 13 17 19 23 29 31 37 41 43 47

The middle value is 23 (right of centre or 14 DIV 2 = position 7). The target value
(41) is greater than the middle value (23) so the right-hand side of the list is kept:

Left-hand side removed 29 31 37 41 43 47

The new middle value is 41 (right of centre or 6 DIV 2 = position 3). The target
value (41) matches the middle value (41) so the target value is found. This took 2
iterations. A linear search would have taken 12.

© paullong.net 2020 Page 60 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example 3
This time the target that is being searched for is E. Here is the list that will be
searched:

A C E G H J K M N P R Y Z

The middle value is the 7th item in the list (13 DIV 2 = 6) which is K.

The target value (E) is less than the middle value (K) so the left-hand side of the
list is kept:

A C E G H J Right-hand side removed

The new middle value is G. (6 DIV 2 = 3 or right of centre).

The target value (E) is less than the new middle value (G) so the left-hand side of
the new list is kept:

A C E RHS removed Right-hand side removed

The new middle value is C (3 DIV 2 = 1). The target value (E) is greater than the
new middle value (A) so the right-hand side is kept:

LHS rem. E RHS removed Right-hand side removed

E is the only value left and is automatically the new middle value and as it
matches the target value (E), the target value has been found.

This took 4 iterations of the binary search to find the target value. A linear search
would have taken 2 iterations because the target value is in the 2nd position.

© paullong.net 2020 Page 61 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – binary search

1) The target being searched for is G. The list being searched is shown below:
B C F G I J M N P S Y Z
Explain how the binary search finds the target value G in the list above.

2) The target being searched for is 7. The list being searched is shown below:
1 3 7 12 18 25 36 49 78 85 92 98 99
Explain how the binary search finds the target value 7 in the list above.

5) Complete this flowchart for the binary search algorithm that uses a REPEAT
loop.

Is Target Keep right

<Middle? hand side

Target Keep left

found hand side

Yes Yes

No No

Binary search – extension work

The following pages related to the binary search are extension work only. It is not
necessary to be able to code the binary search.

Extension video
Watch this explanation of the binary search and a simple version of the
pseudocode http://tiny.cc/binarypseudo1 from Harvard University.

Now watch this other explanation of the binary search and its pseudocode
http://tiny.cc/binarypseudo2, also from Harvard University. Stop at 4 minutes 22
seconds.

© paullong.net 2020 Page 62 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

This is Python code being used to represent a binary search algorithm that reports
back whether an item was found in the list:

1 def binary_search_find(target, arr):

2 found = False
3 left = 0
4 right = len(arr) - 1
5 while left <= right and not found:
6 middle = (left + right) // 2
7 if arr[middle] == target:
8 found = True
9 elif arr[middle] < target:
10 left = middle + 1
11 else:
12 right = middle - 1
13 #endif
14 #endwhile
15 return found
16 #end binarysearch

Line 1 defines the function and accepts the parameters <target> (search value)
and <arr> (the array to search).

Lines 2-4 assign values to variables. <found> is set to False and will only change
to True if the target value is found in the array. <left> and <right> are used to
define the first and last items in the array to be searched. Initially these will be 0 for
the first item and the last item will be one less than the length of the array
(because the array count starts at 0). <left> or <right> will change during each
iteration to define the new shorter list to use.

Line 5 starts the loop which will continue while the <left> and <right> values do
not match and while the <target> value has not been found. When the <left>
and <right> values match, it means that the final middle value has been found
because the start and end of the list will be the same value.

Line 6 defines the new middle value. It will always be the <left> position plus the
<right> position divided by two and rounded down to an integer value.

Lines 7 to 13 determine if the target value has been found, or whether the list
needs splitting in half to try and find the target value again. If the <target> value
is found then it will match the middle item of the array (line 7) and so True will be
assigned to <found>. This will stop the WHILE loop from continuing next time
around. If the <middle> value is less than the target value then it means that the
right hand side of the list needs to be kept and so the value of <right> remains
the same and the value of <left> is changed to be the position after the current
middle position. The opposite happens if the left-hand side needs to be kept.

In line 15, the value of <found> is returned as either TRUE or FALSE.

© paullong.net 2020 Page 63 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension example – binary search code

The target that is being searched for is 6. Here is the list that will be searched:
Position 0 1 2 3 4 5 6
Value 4 6 29 36 72 88 95

1 def binary_search_find(target, arr):

# <target> is received as 6 and <arr> is received as
[4,6,29,36,72,88,95].
2 found = False
3 left = 0 # first position in array
4 right = len(arr) # last position (6) in array
# position 6 is calculated as the LENGTH (7) – 1 = 6
5 while left <= right and not found:
# <left> is 0 and <right> is 6 so left < right
# found is FALSE and so both conditions are true
6 middle = (left + right) // 2
# 0 + 6 = 6. 6 DIV 2 = 3. <middle> becomes 3
Position 0 (left) 1 2 3 (middle) 4 5 6 (right)
Value 4 6 29 36 72 88 95

7 if arr[middle] == target:
# <arr[3]> is 36, <target> is 6 so not true
8 found = True # this line is not run
9 elif arr[middle] < target:
# arr[3] is 36 and is not < 6 so not true
10 left = middle + 1 # this line is not run
11 else:
# only other option is that 36 < 6
12 right = middle - 1
# <right> becomes 3 – 1 = 2
13 #endif
# while loop will repeat with <left> 0 and right <2>
Position 0 (left) 1 2 (right)
Value 4 6 29
15 #endwhile

5 while left <= right and not found:

# <left> is 0 and <right> is 2 so left < right
# found is False and so both conditions are true
6 middle = (left + right) // 2
# 0 + 2 = 2. 2 DIV 2 = 1. <middle> becomes 1
Position 0 (left) 1 2 (right)
Value 4 6 29
7 if arr[middle] == target:
# <arr[1]> is 6, <target> is 6 so true
8 found = True # <found> becomes True
9-12 # these lines are not run because THEN was run
5 while left <= right and not found:
# found is True so the loop does not run
16 return found # TRUE is returned as 6 was found
17 ENDFUNCTION
© paullong.net 2020 Page 64 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension example – using the binary search

The binary search subroutine can be called in exactly the same way as a linear
search subroutine. The only difference is the way the subroutine searches for the
target value.

A program calls the subroutine above when searching for a make of car:

cars = ["Fiat", "Ford", "Mitsubishi", "Tesla", "Toyota",

"Vauxhall"]
make = input(“Please enter the make of car you want to find:”)
in_list = binary_search_find(make, cars)

if in_list:
print(make, "was found in the list.")
else:
print(make, "was not found in the list.")
#endif

Extension activity – binary search code

The array <arr> below contains the following data:
Position 0 1 2 3 4 5 6
Value Apple Banana Kiwi Lemon Lime Mango Plum

1) Explain how the binary search code finds the target values <target>:
a) Mango
b) Lemon
c) Apple

2) a) State the value of <found> if <target> is “Orange”?

b) Explain how the binary search code searches for the target value
“Orange”.

© paullong.net 2020 Page 65 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

3) Complete this flowchart for the binary search algorithm.

left =
middle -
1

left = 0

not found?

return
found

found =
False

middle
= (left +
right) // 2

found =
True

4) Try modifying the function so that it returns the position of the target value.

© paullong.net 2020 Page 66 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension example – binary search trace table

Using the binary search algorithm above, complete the trace table when
<target> is ”S” and <arr> is as shown below:

Position 0 1 2 3 4 5 6 7
Value D F Q R S X Y Z

Trace table:
Iteration target arr found len left right middle arr return
(arr) [middle]
- S [D,F,Q,R,S,Y,Z] False 8 0 7
1 4 3 R
2 4 5 X
3 True 4 S

Note: although <left> <= <right> (4 <= 4) on the final iteration, the WHILE
loop still continues because <found> is still False but then it does not
perform another iteration because <found> is set to True on line 8.

Extension activity – binary search trace table

1) Using the binary search code, complete the trace table for the array <arr>:
Position 0 1 2 3 4 5 6 7
Value black blue orange pink red scarlet white yellow
and each of the following values of <target>:
a) black
b) blue
c) orange
d) pink
e) red
f) scarlet
g) white
h) yellow
i) teal
j) apple

© paullong.net 2020 Page 67 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

2) Using the binary search code, complete the trace table for each of the
following values of <target> and <arr>:
a) <target> is Y and <arr> is:

Position 0 1 2 3 4
Value R S V W Y

b) <target> is 29 and <arr> is:

Position 0 1 2 3 4 5 6 7 8 9 10
Value 2 4 29 30 32 35 40 64 78 98 99

c) <target> is Fa and <arr> is:

Position 0 1 2 3 4 5 6
Value Doe Fa La Me Ray Sew Tea

d) <target> is 2.8 and <arr> is:

Position 0 1 2 3 4 5 6 7 8 9
Value 0.3 0.8 1.6 2.4 2.5 2.8 3.1 3.2 3.6 4.0

Trace table:
Iteration target found len left right middle arr return
(arr) [middle]

Extension video
Watch the explanation of binary trees at http://tiny.cc/binarypseudo3 from
Harvard University. Start from 4 minutes 22 seconds.

© paullong.net 2020 Page 68 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Comparing and contrasting search algorithms

Here is a summary of comparing and contrasting the search algorithms:
Linear Binary
Time of search Fine for short lists. Faster than a linear search
for most circumstances.
Best case scenario Target is in first position so Target is in middle position
only one item to check so only one item to check.
Worst case scenario Target is in last position (or For 1000 items need to
not on the list) so all values check 11 values. For 2n
have to be checked. items (or less) it is n+1 values.
Order of data The list can be in any order. The list has to be in a
sequential order.
Complexity Algorithm is simple to write Algorithm is more complex
and follow. to write and follow.

Video
Watch these videos http://tiny.cc/linearbbc and http://tiny.cc/binarybbc from Ed
Tracey’s BBC Bitesize videos to compare the efficiency of the linear and binary
search algorithms.

Example – best-case scenario

The array below is to be searched:
Position 0 1 2 3 4 5 6 7
Value 2 4 29 30 32 35 40 64
Using a linear search to find the target value 2 would only take one attempt as the
value 2 is in the first position of the array.

Using a binary search to find the target value 32 would only take one attempt as
the value 32 is in the middle of the array at position 4 (8 DIV 2). (30 would also
be an acceptable answer if choosing left-hand side of middle point.)

Example – worst-case scenario

The same array will be searched. Using a linear search to find the target value 64
would take 8 attempts as the value 64 is in the last (8th) position of the array.

Using a binary search to find the target value 2 would take 4 attempts:
Positions 0 - 7 position 4 (32) as middle
Positions 0 - 3 position 2 (29) as middle
Positions 0 - 1 position 1 (4) as middle
Position 0 position 0 (2) as middle = FOUND

(If using the left-hand side of middle point, then worst-case scenario would be for
the target value of 64.)
© paullong.net 2020 Page 69 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – search algorithm attempts

The array below contains letters of the alphabet.

Position 0 1 2 3 4 5 6 7 8 9 10
Value A F H J L M P R T V Z
1) How many attempts would the linear search take to find each of the
following target values:
a) A b) P c) Z d) L

2) How many attempts would the binary search take to find each of the
following target values:
a) A b) P c) Z d) L

3) Using an example, explain how the simplified linear search algorithm below
could be made more efficient.

for item in myArray:

if item == target:
print(target, "found")
#endif
#next item

Extension Maths Link – worst-case scenario - binary logarithm

Imagine a list with 1024 items. When a binary search is performed, the first middle
point will be 512. Here are all the sizes of the list each time it is halved assuming the
value being searched for is always smaller than the middle point:

Attempt 1 2 3 4 5 6 7 8 9 10 11
Size 1024 512 256 128 64 32 16 8 4 2 1

Notice how these are binary numbers. The number of attempts is equivalent to a
binary logarithm (base-2 logarithm) of the number of items in the list plus one more
attempt. The binary logarithm calculates p for 2p (2 to the power of p) needed
when the size of the list = 2p.

Imagine a list size of 8 items:

Incorrect guess reduces to 4 items
Incorrect guess reduces to 2 items
Incorrect guess reduces to 1 item
Remaining item either matches or does not match

© paullong.net 2020 Page 70 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Log2 8 = 3. Add 1 and that gives the 4 attempts above.

For a list of size n, the number of attempts = log2 n + 1
For a list with 1000 items, log2 1000 = 9.97 so this is rounded up to 10.

Each time the list size is doubled, the number of attempts only increases by 1. So,
for a list with 2048 items, only 12 attempts would be needed.

The graph below shows how efficient the binary search algorithm is as the number
of items in a list grows:

Log2 n + 1 Graph
18

16
Number of attempts (Log2n +1

14

12

10

0
3700

26200
100
1000
1900
2800

4600
5500
6400
7300
8200
9100
10000
10900
11800
12700
13600
14500
15400
16300
17200
18100
19000
19900
20800
21700
22600
23500
24400
25300

27100
28000
28900
29800
Items in List

You can use a calculator’s log2 function or a search engine to calculate how
many attempts it would take in the worst-case scenario for any size of list.

Questions – follow me
1) A programmer wants to use a search algorithm for this array
[3, 8, 9, 15, 12, 8].
a) Explain how a linear search would search for the target value 12. [4]
b) State why a binary search could not be used for this array. [1]

2) A binary search is usually more efficient than a linear search.

a) Explain why a linear search would complete quicker for this array
[1, 5, 8, 10, 25, 26, 27, 30, 45, 60, 62, 63] when searching
for the target value 5. [2]
b) Explain why the speed of the binary and linear search algorithms are not
an important factor when choosing an algorithm for this array. [2]
c) State which target value would be the best-case scenario (fastest search
time) for using a binary search on this array. [1]

© paullong.net 2020 Page 71 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

d) A binary search algorithm is used with the list ['a', 'c', 'e', 'f',
'h', 'j', 'm', 's', 't'] to find the target value 'j'.

Complete the table to show the characters in the order that the algorithm
would compare them against the target value. You may or may not
need to use all the rows. [3]
Middle Value

Extension: Examine the code for a binary search algorithm below.

1 def binary_search(target, arr):

2 found = False
3 start = 0
4 end = len(arr) - 1
5 while start <<i>> end and not found:
6 middle = (start + end) // 2
7 if arr[mid] == target:
8 <<ii>>
9 elif arr[mid] < target:
10 start = mid + 1
11 else:
12 <<iii>>
13 #endif
14 #endwhile
15 if not found:
16 mid = -1
17 #endif
18 return mid
19 #end binarysearch

a) i) Identify the code which should go in place of <<i>>.

A =
B <
C <=
D <>
E >= [1]
ii) Write the code which should go in place of <<ii>>. [1]
ii) Write the code which should go in place of <<iii>>. [1]

b) State the purpose of line 16. [1]

© paullong.net 2020 Page 72 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

4) Sorting algorithms

It can often help if data in a list is sorted in order. For example, if you wanted to
use a binary search, then the data would need to be sorted into order. The order
of data could include:

• numbers (low to high or high to low)

• letters (A to Z)
• days of the week
• months of the year
• dates

When data is produced as an output to the user, it may need sorting so that the
user can find data in the list quickly.

Activity – sort a deck of cards

1) Sort a deck of cards so that each suit is in a separate pile. How did you do
this?
2) Sort one of the suits into order from Ace to King. How did you do this?
3) Watch somebody else sort another suit into order. Did they do it differently?
If so, how?

Some methods of sorting are more efficient than others.

Bubble sort

Video
Watch http://tiny.cc/bubblesortBBC from Ed Tracey’s BBC Bitesize videos.

The general idea of the bubble sort is that high

values rise to the top like bubbles in water rise to
the top of the water. The algorithm works by
comparing the two values at the beginning of the
list and swapping them if they are not in order. It
then continues to the next two values and repeats
this until the end of the list has been reached and
the highest value will now be in the correct position at the end of the list. The
whole process repeats again until no more swaps need to be made.

© paullong.net 2020 Page 73 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Here is a simple version of the bubble sort algorithm based on sorting numbers
where n is the position in the list:

1. Look at first item in list <LIST[n]>

2. Compare this item <LIST[n]> with next item in list <LIST[(n+1)]>
3. If this item <LIST[n]> is bigger than next item <LIST[(n+1)]> then swap
them
4. Move to next number position in list <n+1> so n becomes <n+1>
5. Repeat steps 2 to 4 until last item is reached
6. If there were any swaps, repeat steps 1 to 5

Example – simple bubble sort

The table below contains 5 values in positions 1 to 5. It needs to be sorted into
order so that the lowest value is in position 1 and the highest value in position 2.

Following the bubble sort algorithm, each pair of items is compared and if
necessary, swapped:

Pos Value Pos Value Pos Value Pos Value Pos Value
4 19 4 19 4 19 4 19 4 23
3 18 3 18 3 18 3 23 3 19
2 17 2 17 2 23 2 18 2 18
1 15 1 23 1 17 1 17 1 17
0 23 0 15 0 15 0 15 0 15

Notice how 23 has risen from the bottom of the list to the top of the list like a
bubble. As swaps took place, the whole process needs to be repeated:

Pos Value Pos Value Pos Value Pos Value

4 23 4 23 4 23 4 23
✓
3 19 3 19 3 19 3 19
2 18 2 18 2 18 ✓ 2 18
1 17 1 17 ✓ 1 17 1 17
✓
0 15 0 15 0 15 0 15
This time, each value is in the correct order and so no swaps take place meaning
that the algorithm completes. This took two iterations, known as passes, through
the table.

Video
Watch http://tiny.cc/bubble-harvard from Harvard University but stop at 1:45.

The algorithm for this simple version of the bubble sort can be represented as a
flow chart:

© paullong.net 2020 Page 74 of 106 by Paul Long

 The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

1. Look at first item in list

<LIST[n]>

2. Compare this item

<LIST[n]> with next item
1 in list <LIST[(n+1)]>

3. If this item <LIST[n]> is

bigger than next item
2 4
<LIST[(n+1)]> then swap

4. Move to next number

5
6 position in list <n+1> so n
becomes <n+1>

5. Repeat steps 2 to 4 until last

item is reached
3
6. If there were any swaps
repeat steps 1 to 5

In an exam, the list is likely to be presented to you horizontally, rather than vertically
and so from this point forward, all examples will use a horizontal list – just imagine
the bubble moving to the right instead of to the top.

Example – simple bubble sort with multiple passes

The table below contains 5 values in positions 0 to 4. It needs to be sorted into
order so that the lowest value is in position 0 and the highest value is in position 4.

Following the bubble sort algorithm, each pair of items is compared and if
necessary, swapped. The table below shows the first pass (iteration):
Pass 1:
Position 0 1 2 3 4 Notes
Value 30 10 50 40 20 30 is bigger than 10 so items 0 and 1 will swap

Value 10 30 ✓50 40 20 30 and 50 in order so no swap

Value 10 30 50 40 20 50 is bigger than 40 so items 2 and 3 will swap

Value 10 30 40 50 20 50 is bigger than 20 so items 3 and 4 will swap

Value 10 30 40 20 50 End of first pass

The first pass has moved the highest value of 50 to the top of the list. As swaps took
place, the whole process needs to be repeated:

© paullong.net 2020 Page 75 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Pass 2:

Position 0 1 2 3 4 Notes
Value 10✓ 30 40 20 50 10 and 30 in order so no swap needed

Value 10 30 ✓ 40 20 50 30 and 40 in order so no swap needed

Value 10 30 40 20 50 40 is bigger than 20 so items 2 and 3 will swap

Value 10 30 20 40✓ 50 40 and 50 in order so no swap needed

Value 10 30 20 40 50 End of 2nd pass

The second pass has moved the second highest value of 40 to the second highest
position in the list. As swaps took place, the whole process needs to be repeated:
Pass 3:
Position 0 1 2 3 4 Notes
Value 10✓ 30 20 40 50 10 and 30 in order so no swap needed

Value 10 30 20 40 50 30 is bigger than 20 so items 1 and 2 will swap

Value 10 20 30✓ 40 50 30 and 40 in order so no swap needed

Value 10 20 30 40✓ 50 40 and 50 in order so no swap needed

Value 10 20 30 40 50 End of 3rd pass

The third pass has moved the third highest value of 30 to the third highest position
in the list. As swaps took place, the whole process needs to be repeated:
Pass 4:
Position 0 1 2 3 4 Notes
Value 10 20 30 40 50 10 and 30 in order so no swap needed
✓
Value 10 20 30 40 50 30 is bigger than 20 so items 1 and 2 will swap
✓
Value 10 20 30 40 50 30 and 40 in order so no swap needed
✓
Value 10 20 30 40 50 40 and 50 in order so no swap needed
✓
Value 10 20 30 40 50 End of 3rd pass

No swaps took place so the bubble sort is complete and the list is in ascending
order.

Activity – human bubble sort

Stand in a line of around 8 students. Use the bubble sort algorithm to sort
yourselves into height order. Then use the bubble sort algorithm to sort yourselves
into alphabetical order.
© paullong.net 2020 Page 76 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net
In an exam, you may to be presented with an array and asked to show the steps
involved during the bubble sort.

Example – simple bubble sort of an array

The bubble sort algorithm will be used to sort the array [8, 12, 6, 4, 7]. Show
the steps involved using the bubble sort algorithm.

Pass 1: [8,12,6,4,7] – [8,12,6,4,7] – [8,6,12,4,7] – [8,6,4,12,7] – [8,6,4,7,12]

Pass 2: [8,6,4,7,12] – [6,8,4,7,12] – [6,4,8,7,12] – [6,4,7,8,12] – [6,4,7,8,12]
Pass 3: [6,4,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12]
Pass 4: [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12]

The yellow highlights show where a swap needs to been made.

You could also be asked to show just the changes that are made with the first row
given for you:
8 12 6 4 7 This is the first row given for you.

8 6 12 4 7 6 and 12 have been swapped

8 6 4 12 7 4 and 12 have been swapped

8 6 4 7 12 7 and 12 have been swapped (end of pass 1)

6 8 4 7 12 6 and 8 have been swapped

6 4 8 7 12 4 and 8 have been swapped

6 4 7 8 12 7 and 8 have been swapped (end of pass 2)

4 6 7 8 12 4 and 6 have been swapped (end of pass 3)

Activity – efficiency
Can you find a way of making the bubble sort algorithm above more efficient?

Exam tip: you can use the version above in an exam for lower marks, but if you
are aiming for higher grades then you also need to be able to
understand the more efficient version shown below.

Have you noticed that the after the first pass, the last value in a list is in its final
position? Then after the second pass, the last 2 values in a list are in their final
positions, and after a third pass, the last 3 values are in their final positions ? The
pattern continues. It is therefore not necessary to keep checking the latter values
during each pass. The method above was used earlier, but this time, for each
pass, the bubble sort stops one position shorter than the previous pass.

© paullong.net 2020 Page 77 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – complete bubble sort of an array

The bubble sort algorithm was used to sort the array [8, 12, 6, 4, 7]. The
green highlights below show the values that are in their final position at the end of
each pass.

Pass 1: [8,12,6,4,7] – [8,12,6,4,7] – [8,6,12,4,7] – [8,6,4,12,7] – [8,6,4,7,12]

Pass 2: [8,6,4,7,12] – [6,8,4,7,12] – [6,4,8,7,12] – [6,4,7,8,12] – [6,4,7,8,12]
Pass 3: [6,4,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12]
Pass 4: [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12]

The blue highlights show steps that do not need to be taken. This is unnecessary
processing. The method below is much more efficient:

The bubble sort algorithm will be used to sort the array [8, 12, 6, 4, 7]. Show
the steps involved using the bubble sort algorithm.

Pass 1: [8,12,6,4,7] – [8,12,6,4,7] – [8,6,12,4,7] – [8,6,4,12,7] – [8,6,4,7,12]

Pass 2: [8,6,4,7,12] – [6,8,4,7,12] – [6,4,8,7,12] – [6,4,7,8,12]
Pass 3: [6,4,7,8,12] – [4,6,7,8,12] – [4,6,7,8,12]
Pass 4: [4,6,7,8,12] – [4,6,7,8,12]

Video
Watch this explanation of a bubble sort http://tiny.cc/bubblecups using
polystyrene cups from KC Ang. Notice how the sort is shorter for each pass.

Watch this explanation http://tiny.cc/bubble-exam from Hegarty Maths of how to

answer a bubble sort question in an exam from 4:30 to 8:36.

You may also find this Hungarian folk dance http://tiny.cc/bubbledance an

entertaining way of understanding the bubble sort. The letter ‘a’ represents the
name of an array and the numbers in square brackets are the positions in the
array. The dancers are the values in the array that need to be sorted into order.

© paullong.net 2020 Page 78 of 106 by Paul Long

 The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Here is the complete version of the bubble sort algorithm based on sorting
numbers where n is the position in the list. The green highlights show the
improvements from the simple bubble sort:

1. Look at first item in list <LIST[n]>

2. Compare this item <LIST[n]> with next item in list <LIST[(n+1)]>
3. If this item <LIST[n]> is bigger than next item <LIST[(n+1)]> then swap
4. Move to next number position in list <n+1> so n becomes <n+1>
5. Repeat steps 2 to 5 until last item to check is reached
6. If there were any swaps, check if <LIST[n]> is first item in list
7. if <LIST[n]> is NOT the first item in list, repeat steps 1 to 7

7
4

Exam tip: use this complete version of the bubble sort algorithm in the exam.

© paullong.net 2020 Page 79 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – complete bubble sort of an array

For each question below, use the complete bubble sort that reduces the amount
of data to sort during each pass. The first pass has been done for you.

1) The bubble sort algorithm will be used to sort the array [Q, Z, R, B].
Show the steps involved using the bubble sort algorithm.
Pass 1 Pass 2 Pass 3
0 1 2 3 0 1 2 3 0 1 2 3
Q Z R B
Q Z R B
Q R Z B
Q R B Z

2) The bubble sort algorithm will be used to sort the array [9, 8, 5, 4, 6].
Show the steps involved using the bubble sort algorithm. You may or may
not need to use all rows for each pass.

Pass 1 Pass 2 Pass 3 Pass 4

0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
9 8 5 4 6
8 9 5 4 6

3) The bubble sort algorithm will be used to sort the array [a, h, g, f, b].
Show the steps involved using the bubble sort algorithm.

4) The bubble sort algorithm will be used to sort the array [3, 12, 4, 7].
Show the steps involved using the bubble sort algorithm.

5) The bubble sort algorithm will be used to sort the array [10, 4, 8, 3, 7].
Show the steps involved using the bubble sort algorithm.

6) The bubble sort algorithm will be used to sort each of the following arrays.
Show the steps where a change is applied to the array.
a) [19, 6, 13, 14, 18] b) [3, 1, 8, 5] c) [Z, P, D, B]

Activity – bubble sort animation

Step through the animation of the bubble sort at http://tiny.cc/sorting-ani

Click on BUBBLE at the top, then SORT at the bottom followed by GO. You can
pause or rewind the animation at any time. Notice how the items are changing in
time with the pseudocode visualisation.
© paullong.net 2020 Page 80 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Bubble sort – extension work

The following pages related to the bubble sort are extension work only. It is not
necessary to be able to code the bubble sort.

Example – complete bubble sort code

This is the code for the complete bubble sort:

1 def bubblesort(arr_in):
2 arr = arr_in[:] #this is to avoid overwriting original list
3 last_compare = len(arr) - 1
4 swapped = True
5 while swapped and last_compare != 0:
6 swapped = False
7 for counter in range(0, last_compare):
8 if arr[counter] > arr[counter+1]:
9 temp = arr[counter]
10 arr[counter] = arr[counter+1]
11 arr[counter+1] = temp
12 swapped = True
13 #endif
14 #next counter
15 last_compare = last_compare - 1
16 #end while
17 return arr
18 #end bubblesort

Line 1 receives an array named <arr_in>. Line 2 is needed to prevent Python

overwriting the original list – this is a problem specific to Python. Line 3 sets the
position of the last item in the list (array positions start at zero) to be the last item to
compare for the first iteration. For example, if the list is ["a", "h", "g", "f",
"b"] then the last item to compare is "f".

Position 0 1 2 3 4
last_compare = length - 1

Line 4 sets a <swapped> variable (flag) to False so the WHILE loop runs at least
once.

Lines 5 to 16 are the WHILE loop for each pass (iteration) of the bubble sort. It runs
while items have been swapped. The first condition of items being swapped
means that the bubble sort will stop if no items are swapped because it then
knows the list is in the correct order. The second condition is there so that if the
bubble sort has to swap when only comparing the first two values on the final pass
where the <last_compare> is now 0 (first item in array), then it doesn’t need to run
again to check that there are no swaps

© paullong.net 2020 Page 81 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Line 6 sets the variable (flag) named <swapped> to be False so that the WHILE
loop will continue to repeat if values are swapped.

Lines 7 to 14 deal with comparing adjacent items in the list and swapping them if
necessary. The FOR loop starts at the item in position 0 of the array and finishes at
the last but one item in the array because the last item has nothing left to
compare with (remember Python’s top value in range is exclusive (it is not
included in the range).
Each pair of items is compared using lines 8 to 13. If a swap is necessary (line 8),
then a temporary variable <temp> (line 9) is assigned the value of
<arr[counter]> (the current position in the array). The current position in the
array is then assigned the value of the next position in the array
<arr[counter+1]> (line 10). The next position in the array is then assigned the
temporary value <temp> (line 11) which was originally the current position in the
array.

Line 9 arr[counter] temp

Line 10 arr[counter+1] arr[counter]

Line 11 temp arr[counter+1]

Line 12 swapped True

The variable (flag) <swapped> is then set to True so that the WHILE loop knows a
swap took place and will continue with another pass.

Line 15 reduces the <last_compare> by one at the end of each pass so that the
next pass does not need to compare the higher values that are already in their
correct position.

Position 0 1 2 3 4
last_compare = last_compare - 1

Extension activity – complete bubble sort code

Run the code for the complete bubble sort. Watch the step-by-step version to
watch the variables changing and investigate how the code works. Try out
different values for the list.

Try modifying the code so that it sorts a list in descending order instead of
ascending order.
© paullong.net 2020 Page 82 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension example – bubble sort trace table

Here is an example of a trace table for the algorithm shown above when the
value of arr_in is [M, A, T, H, S]. For each iteration, the number represents
the WHILE loop and the letter represents the nested FOR loop inside the WHILE
loop.

Iteration last_ swapped counter temp arr arr arr

compare [counter] [counter+1]
4 True [M,A,T,H,S]
1 False
1a 0 M A [A,A,T,H,S]
True M [A,M,T,H,S]
1b 1
1c 2 T H [A,M,H,H,S]
True T [A,M,H,T,S]
1d 3 S T [A,M,H,S,S]
3 True T [A,M,H,S,T]
2 False
3a 0
3b 1 M H [A,H,H,S,T]
True M [A,H,M,S,T]
3c 2 2
4 False
4a 0
4b 1 1

© paullong.net 2020 Page 83 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension activity – bubble sort trace table

1) Complete the trace table below for the bubble sort algorithm shown above
when the value of <arr_in> is [4, 3, 5, 2]. For each iteration, the
number in the iteration column represents the WHILE loop and the letter
represents the nested FOR loop inside the WHILE loop. The first few lines have
been completed for you.

Iteration last_ swapped counter temp arr arr arr

compare [counter] [counter+1]
3 True [4,3,5,2]
1 False
1a 0 4 3 [3,3,5,2]
True 4 [3,4,5,2]

2) Complete the trace table below for the bubble sort algorithm shown above
when the value of <arr_in> is ["P", "B", "D", "C", "Q"].
Iteration last_ swapped counter temp arr arr arr
compare [counter] [counter+1]
3 True [4,3,5,2]
1 False
1a 0 4 3 [3,3,5,2]
True 4 [3,4,5,2]

© paullong.net 2020 Page 84 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Merge sort
The merge sort is a quicker algorithm than the bubble sort for longer lists. It uses a
divide and conquer method. It starts by dividing the list repeatedly into halves until
there is a set of lists with only one item in each:

Example – divide
The array [5,3,9,4,15,2,1,16] is to be sorted using a merge sort. First it is
divided:
5 3 9 4 15 2 1 16

5 3 9 4 15 2 1 16

5 3 9 4 15 2 1 16

5 3 9 4 15 2 1 16
There are now 8 separate arrays with just one item in each.

Next the merge sort conquers and combines by merging the arrays into order:

Example – conquer and combine

5 3 9 4 15 2 1 16

3 5 4 9 2 15 1 16

3 4 5 9 1 2 15 16

During the first pass through, 3 was smaller than 5 so 3 was moved into the first
position of the new array and 5 into the second position. Similarly, 4 was smaller
than 9 so 4 was moved into the first position of the new array and 9 into the
second position. With 1 and 16, they were already in order so 1 was moved into
the first position and 16 into the second position.

During the second pass through, each of the arrays of length two were merged
into arrays of length four. The smallest number 3 was moved into the first position,
then the next number 4 moved into the second position, then the next number 5
moved into the third position and finally 9 moved into the last position. A similar
process took place with the other two arrays.

In the final pass through, the numbers will be merged in order, starting with one,
into the final sorted array:
1 2 3 4 5 9 15 16

© paullong.net 2020 Page 85 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Video
Watch this explanation of the merge sort using cups http://tiny.cc/mergesort from
Harvard University but stop at 1:20.

Alternatively, watch http://tiny.cc/mergebbc from Ed Tracey’s BBC Bitesize videos.

The phrase divide and conquer is used because the list is divided down into smaller
lists and each smaller list is solved before combining each smaller list into longer
lists. You could try replacing the word list with problem in the sentence above and
you can see how this is a bit like decomposition.

Activity – divide and conquer

The array [68, 34, 15, 23, 19, 20, 80, 35] is to be sorted using a merge
sort. Show the steps that are involved in dividing the array:

Now show the steps involved in conquering the array into a sorted list using the
merge sort:

The merge sort is an out-of-place sort which means it creates extra lists to sort the
main list. These extra lists take up additional memory while the merge sort is
running.

Video
Watch this animation of the merge sort http://tiny.cc/mergesort2 from Geeks for
Geeks. You can skip the code at the end. Observe how the list on the right-hand
side with an odd number of values is split and then merged.

© paullong.net 2020 Page 86 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – odd numbered lists

The array [5,3,9,5,2,1] is to be sorted using a merge sort. First it is divided:
5 3 9 15 2 1

5 3 9 15 2 1

5 3 9 15 2 1

5 3 9 15 2 1
There are now 6 separate arrays with just one item in each. Notice how the two
odd-numbered lists needed to be split into two, but they were not equal halves.
This left 9 and 1 in lists on their own but each one still needed to be added to
another individual list of one item in the bottom row.

When splitting an odd numbered list, it does not matter whether you split with the
longer list on the left-hand side or right-hand side, as long as you are consistent
with all odd numbered lists.

Now it is time to conquer and combine. Follow the same pattern as before
ensuring the odd numbered lists are merged in the same way they were split.

5 3 9 15 2 1

3 5 9 2 15 1

3 5 9 1 2 15

In the final pass through, the numbers will be merged in order, starting with one,
into the final sorted array:
1 2 3 5 9 15

Activity – merge sort of odd numbered lists

1) Take one suit of playing cards (13 total). Perform a merge sort on the
playing cards so they are in order from Ace (low) to King (high).

2) Line up as a class in a random order. Divide, conquer and combine

yourselves so that you are sorted into order using the merge sort method.

3) Show the steps involved in merge sorting this array [29, 35, 24, 15, 20]

© paullong.net 2020 Page 87 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Merge sort – extension work

The following pages related to the merge sort are extension work only. It is not
necessary to be able to code the merge sort. These particular pages should be
used with caution for the highest ability learners only as the concepts covered
here are of A Level standard.

Repeatedly dividing the arrays requires a method known as recursion. The

subroutine calls itself to run again. There is an alternative merge sort algorithm that
uses iteration instead of recursion.

Here is a way of describing the merge sort algorithm:

• Stop if only one item in list
• Divide list into two parts
• Recursively divide the new lists into two parts until each list only has one item
• Unwrap the recursion to merge the lists

Extension activity – merge sort animation

Watch the animation step-by-step at http://tiny.cc/merge-ani and observe
carefully how the merge sort algorithm calls itself recursively to divide, conquer
and combine.

Watch how the pseudocode is recursively called in this animation

http://tiny.cc/sorting-ani of the merge sort.

Click on MERGE at the top, then SORT at the bottom followed by GO. You can
pause or rewind the animation at any time. Notice how the items are changing in
time with the pseudocode visualisation.

Extension video
Watch this visual explanation of the recursive merge sort using odd numbers of
items in lists http://tiny.cc/mergerecursive from Yusuf Shakeel.

You may also find this German folk dance http://tiny.cc/mergedance an

entertaining way of understanding the merge sort. The letter ‘a’ represents the
name of the unsorted array and the numbers in square brackets are the positions
in the array. The dancers are the values in the array that need to be sorted into
order. The letter ‘b’ represents the name of the sorted array.

© paullong.net 2020 Page 88 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension example – merge sort code

<alist> is the list to sort. The list is repeatedly cut into two until it is of length one.
It is then put back together as each recursion collapses where <k> is the current
position (index) being sorted in each list. <leftside> is the LEFT sorted part of the
array. <i> is the current position in the left array. <rightside> is the RIGHT sorted
part of the array. <j> is the current position in the right array.
Index i 0 1 2 3 Index j 0 1 2 3
leftside[i] 54 26 93 17 rightside[j] 77 31 44 55
Position k 0 1 2 3 4 5 6 7
alist[k] 17 26 31 44 54 55 77 93
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)//2
leftside = alist[:mid]
rightside = alist[mid:]
mergeSort(leftside)
mergeSort(rightside)
i=0
j=0
k=0
while i < len(leftside) and j < len(rightside):
if leftside[i] < rightside[j]:
alist[k]=leftside[i]
i=i+1
else:
alist[k]=rightside[j]
j=j+1
#endif left vs right
k=k+1
#endwhile

while i < len(leftside):

alist[k]=leftside[i]
i=i+1
k=k+1
#endwhile leftside

while j < len(rightside):

alist[k]=rightside[j]
j=j+1
k=k+1
#endwhile rightside
#endif length
#end mergeSort
© paullong.net 2020 Page 89 of 106 by Paul Long
The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Extension activity – merge sort code

Examine the code in the example above.

Watch the step-by-step version of the code as it runs, to see how the code is being
called recursively to split the lists, and how each recursion collapses to merge the
lists.

© paullong.net 2020 Page 90 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Comparing and contrasting sort algorithms

Here is a summary of comparing and contrasting the sorting algorithms:

Bubble Merge
Time of sort Fine for short lists, but very Faster than a bubble sort for
slow for long lists, unless most circumstances.
they are close to being in
the correct order already.

Memory Variables only use memory New lists and variables reserve
during each pass. more memory each time a
recursion takes place requiring
a lot more memory in this out-
of-place sort.
Complexity Algorithm is reasonably Algorithm is very complex to
simple to write and follow. write and follow.
Best case scenario The list is already sorted so The running time is always
only one pass needed to calculated as n x log2n unless
confirm no swaps required. a quick check is done at start
Number of comparisons = to see if list is already in order
n (number of items in list). in which case the running time
is n.
Worst case scenario The list is in reverse order so For 1,000 items, the number of
the maximum number of comparisons is approximately
passes are needed to 10,000. For 500 items, the
‘bubble’ each element number of comparisons is
across the list. This will take approximately 4,500. The
approximately n2 calculation for number of
comparisons. comparisons is n x log2n

Both sorting methods will sort an unsorted list into an order. The input is an unsorted
list and the output will be an ordered list – e.g. numerical or alphabetical order.

Activity – compare speed of sorting algorithms

Find a partner to work with and collect one suit of playing cards each. Put one suit
into a random order and then place the other suit in the same order.

One of you should use the bubble sort to sort the cards, and the other should use
the merge sort to sort the cards.

Record how many comparisons you each had to make. Which search was fastest.
Why do you think it was faster?

You could also do this with a group of students sorting yourselves into height or
alphabetical or date of birth order.

© paullong.net 2020 Page 91 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Comparing and contrasting sort algorithms – extension work

This page is extension work only. It is not necessary to know how to calculate the
best-case and worst-case scenarios for searches.

Extension Maths Link – running time

Extension: worst case scenario time taken for sort algorithms.
The worst-case scenario number of comparisons for a bubble sort is n2.
The worst-case scenario number of comparisons for a merge sort is n x log2n.
The graph below shows how the number of comparisons for the bubble sort
becomes exponentially longer than the merge sort as the number of elements to
be sorted grows.

Bubble vs Merge Sort running time

800

700

600

500
Comparisons

400

300

200

100

0
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number of elements (n)

Merge n*Log2n Bubble n2

Extension activity – calculate the running time of sort algorithms

1) Calculate the worst-case number of comparisons for a) merge sort and b)
bubble sort algorithms for each of the following number of elements:
i) 16 ii) 100 iii) 1000 iv) 250,000

2) Create a formula in a spreadsheet or use a programming language to

calculate the worst-case number of comparisons for any number of
elements for both merge sort and bubble sort.

© paullong.net 2020 Page 92 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Questions – follow me
1) a) State the purpose of the algorithm below. [1]

arr = ["z", "q", "x", "b", "h"]

last_compare = len(arr) - 1
swapped = True
while swapped and last_compare != 0:
swapped = False
for counter in range(0, last_compare):
if arr[counter] > arr[counter+1]:
temp = arr[counter]
arr[counter] = arr[counter+1]
arr[counter+1] = temp
swapped = True
#endif
#next counter
last_compare = last_compare - 1
#end while

b) Give the name of a more efficient algorithm for achieving the same
purpose. [1]

c) Give three reasons why a programmer would prefer to use the less time
efficient algorithm from (a). [3]

2) A bubble sort is to be used to sort the array [3, 4, 8, 9, 10, 11].

a) State how many passes are needed to sort this array. [1]

b) Explain your answer to (a). [1]

3) a) A bubble sort is to be used to sort the array [8, 3, 4, 10, 11, 9].
Show the missing steps each time a change is applied to the array. [4]

8 3 4 10 11 9

© paullong.net 2020 Page 93 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

b) A merge sort is to be used to sort the array [4, 6, 1, 2, 9, 3, 5, 8].

Show the missing stages of the merge sort. [3]

[4, 6, 1, 2, 9, 3, 5, 8]

[4] [6] [1] [2] [9] [3] [5] [8]

[1, 2, 3, 4, 5, 6, 8, 9]

c) A merge sort is to be used to sort the array [8, 3, 4, 10, 11, 9].
Show the stages of the merge sort. [5]

© paullong.net 2020 Page 94 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

5) Truth tables

Introduction
The Boolean data type has two possible values which are TRUE or FALSE, often
represented as 1 or 0, and ON or OFF in an electrical circuit:

TRUE FALSE
1 0
ON OFF

Truth tables
Computers include electronic circuits which can be switched to ON and OFF using
a variety of components. Some of these components are known as logic gates
which include NOT, AND and OR.

A truth table shows the possible values of outputs for all the possible values of
inputs. Outputs are often shown as a Boolean expression. The simplest Boolean
expression is when the output matches the input:

Q=A

The truth table below shows the output for the Boolean expression Q = A:

INPUT (A) OUTPUT (Q)

0 0
1 1

Boolean expressions in Python

In Python code, you might see this used in an expression for a loop or a selection
statement.
In a truth table, this would look like:
if a:
q = True INPUT OUTPUT
else: a q
q = False False False
#endif True True

© paullong.net 2020 Page 95 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Logical operators

Each of the logical operators can also be referred to as a Boolean expression.

NOT
The NOT operator is the simplest of all operators. It reverses the value of a single
input.

If the input is TRUE then the output will be FALSE. If the input is FALSE then the
output will be TRUE.

A truth table can be constructed to show the possible values of outputs for all the
possible values of inputs:

INPUT OUTPUT
0 1
1 0

The output can be expressed as:

Q = NOT A

This would be represented in a truth table as:

A Q
0 1
1 0

NOT operator in Python

In Python code, the NOT operator can be included in an expression for a loop or a
selection statement.
In a truth table, this would look like:
if not a:
q = True INPUT OUTPUT
else: a q
q = False False True
#endif True False

© paullong.net 2020 Page 96 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – NOT
1) Consider the Boolean expression below with an input of A and an output of
Q:

Q = NOT A

a) What is the value of Q when A is 1?

b) What is the value of Q when A is 0?

AND
If both inputs are TRUE then the output will be TRUE. If any of the inputs are FALSE
then the output will be FALSE.

A truth table can be constructed to show the possible values of outputs for all the
possible values of inputs:

INPUT OUTPUT
A B Q
0 0 0
0 1 0
1 0 0
1 1 1

Q can be expressed as:

Q = A AND B

AND operator in Python

In Python code, the AND operator can be included in an expression for a loop or a
selection statement.

In a truth table, this would look like:

if a and b:
q = True
INPUT OUTPUT
else: a b q
q = False False False False
#endif False True False
True False False
True True True

© paullong.net 2020 Page 97 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – AND
1) Consider the Boolean expression below with an input of A and an output of
Q:

Q = A AND B

a) What is the value of Q when A is 1 and B is 0?

b) What is the value of Q when A is 0 and B is 1?
c) What is the value of Q when A is 1 and B is 1?
d) What is the value of Q when A is 0 and B is 0?

OR
If either input is TRUE then the output will be TRUE. If both of the inputs are FALSE
then the output will be FALSE.

A truth table can be constructed to show the possible values of outputs for all the
possible values of inputs:

INPUT OUTPUT
A B Q
0 0 0
0 1 1
1 0 1
1 1 1

Q can be expressed as:

Q = A OR B

OR operator in Python
In Python code, the AND operator can be included in an expression for a loop or a
selection statement.

In a truth table, this would look like:

if a or b:
q = True
INPUT OUTPUT
else: a b q
q = False False False False
#endif False True True
True False True
True True True

© paullong.net 2020 Page 98 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – OR
1) Consider the Boolean expression below with an input of A and an output of
Q:

Q = A OR B

a) What is the value of Q when A is 1 and B is 0?

b) What is the value of Q when A is 0 and B is 1?
c) What is the value of Q when A is 1 and B is 1?
d) What is the value of Q when A is 0 and B is 0?

Video
Watch the video at http://tiny.cc/truthtables1 to review truth tables for logic gates.
Although you do not need to know what logic gates are, the concept is quite
simple.

Combining logical operators

Boolean operators can be combined to produce complex expressions which can
make many logical decisions. A combination of Boolean operators can have
many inputs. For the Edexcel exam, you only need to consider 3 inputs.

Truth tables for Boolean expressions

You need to be able to create truth tables for Boolean expression.

Example – two inputs truth table

Consider this Boolean expression:

Q = (NOT A) AND B

When creating a truth table, it can help to create a column for interim results. In
this case, a column for the output of the NOT gate would be useful. This will be
referred to as X:

INPUT INTERIM OUTPUT

A B X = NOT A Q = X AND B
0 0 1 0
0 1 1 1
1 0 0 0
1 1 0 0

© paullong.net 2020 Page 99 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

In Python code, this expression could be part of a loop or a selection statement.

In a truth table, this would look like:

if (not a) and b:
q = True
INPUT INTERIM OUTPUT
else: a b not a (not a) and b
q = False False False True False
#endif False True True True
True False False False
True True False False

Example – three inputs truth table

Consider this Boolean expression:

Q = (NOT A) AND (B OR C)

There are 3 inputs: A, B and C. There is one output: Q.

A is an input to a not gate which we can give an interim result of X:

X = NOT A

B and C are inputs to an OR gate which we can give an interim result of Y:

Y = B OR C

X and Y are inputs to an AND gate:

Q = X AND Y
Q = (NOT A) AND (B OR C)

When creating the truth table, start with the interim results X and Y. You can then
use X and Y as an input to Q.

INPUT INTERIM OUTPUT

A B C X = NOT A Y = B OR C Q = X AND Y
0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 0 0 0
1 0 1 0 1 0
1 1 0 0 1 0
1 1 1 0 1 1

© paullong.net 2020 Page 100 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

When creating a truth table for a combination of logic gates, you need to
determine how many lines are required in the truth table. This can be calculated
using the following rule:

number of lines = 2n where n is the number of inputs

Number of inputs Number of lines (2n)

1 1
2 4
3 8

Always start with a line of zeros and finish with a line of 1s.

The tables below show the pattern to use for each number of inputs:

2 inputs: 3 inputs:

INPUT OUTPUT INPUT OUTPUT

A B Q A B C Q
0 0 0 0 0 0
0 1 1 0 0 1
1 0 1 0 1 0
1 1 1 0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Can you spot a pattern? If you look carefully, you will notice that the inputs are in
a sequence as if they were binary numbers.

Precedence rules
Before looking at the precedence rules for logical operators, let’s look at how they
work in maths.

Maths link – BIDMAS

BIDMAS is an acronym used in maths to help remember the correct order in which
to solve maths problems:

Brackets
Indices
Division
Multiplication
Addition
Subtraction

© paullong.net 2020 Page 101 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

This means that any calculations within brackets should be calculated first,
followed by any indices (e.g. 52 = 25). Once those calculations have been made,
then division and multiplication should take place. The final calculation to take
place is addition.

For example:

(5 + 2) x 32 + 4 ÷ 2 – 8

To calculate this expression, we first look at the brackets and calculate 5 + 2 = 7 so

we now have:

7 x 32 + 4 ÷ 2 – 8

Next, we calculate any indices so 32 = 9. This give us:

7x9+4÷2–8

The next stage is to calculate any multiplication or division. These are 7 x 9 = 63

and 4 ÷ 2 = 2. We no have:

63 + 2 – 8

Finally, any addition or subtraction can be calculated giving us an answer of 57.

A clearer way of writing the above calculation would have been:

((5 + 2) x 32) + (4 ÷ 2) – 8

The rules of precedence for calculations in maths are important where brackets
are not explicitly used.

Logical operators also have precedence rules when combined to form a complex
expression:

Brackets
Not
And
Or

Brackets should always be evaluated first, followed by the NOT operator. In the
absence of further brackets, AND operators should be evaluated next followed by
OR.

© paullong.net 2020 Page 102 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Example – precedence rules

Consider this Boolean expression:

Q = NOT (A OR B) AND NOT C OR B

The brackets should be evaluated first so we will use an interim result of W:

W = (A OR B) Q = NOT W AND NOT C OR B

NOT W and NOT C should be the next to be evaluated so we will use interim results
of X and Y:

X = NOT W
Y = NOT C Q = X AND Y OR B

Next, AND should be evaluated so we will use an interim result of Z:

Z = X AND Y Q = Z OR B

Finally, OR can be evaluated giving the final result of Q.

The truth table would look like this:

INPUT INTERIM OUTPUT

A B C W = (A OR B) X = NOT W Y = NOT C Z = X AND Y Q = Z OR B
0 0 0 0 1 1 1 1
0 0 1 0 1 0 0 0
0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1
1 0 0 1 0 1 0 0
1 0 1 1 0 0 0 0
1 1 0 1 0 1 0 1
1 1 1 1 0 0 0 1

© paullong.net 2020 Page 103 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Activity – truth tables for multiple inputs

1) Complete a truth table for each of the Boolean expressions.

a) Q = NOT(A AND B)
A B Q
0 0
0 1
1 0
1 1
b) NOT A OR B

A B Q
0 0
0 1
1 0
1 1
c) Q = NOT A AND (B OR C)

A B C X = B OR C Y = NOT A Q = Y AND X
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

d) NOT(A AND B) AND (A OR B)

A B Q
0 0
0 1
1 0
1 1

© paullong.net 2020 Page 104 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

e) Q = NOT((A OR B) AND (B OR C))

A B C Q
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Extension:
In an exam, you would only be expected to work with 3 inputs. This question uses a
4th input – D.

f) Q = A OR B AND C OR D

A B C D Q
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

© paullong.net 2020 Page 105 of 106 by Paul Long

The Ultimate GCSE CS Textbook for Edexcel - Chapter 1 - Published by paullong.net

Questions – follow me
1) Explain why data is represented in computer systems in binary form. [2]

2) Examine the truth table below:

A B Q
0 0 0
0 1 1
1 0 1
1 1 1

State which logical operator is represented by this truth table. [1]

3) Complete the truth table below:

A B A AND B
0 0
0 1
1 0
1 [1] 1

4) Complete column Q of the truth table for the Boolean expression

Q = NOT (A OR B). You may or may not want to use column X. [1]

A B X Q
FALSE FALSE
FALSE TRUE
TRUE FALSE
TRUE TRUE FALSE

5) Complete a truth table the following Boolean expressions:

a) Q = NOT A [1]

b) Q = A AND B OR NOT C [2]

c) Q = NOT A AND (B OR C) [2]

© paullong.net 2020 Page 106 of 106 by Paul Long