AQA A-level

Computer
Science
Includes AS and A-level
Bob Reeves

Approval message from AQA

This textbook has been approved by AQA for use with our qualification. This means that we
have checked that it broadly covers the specification and we are satisfied with the overall
quality. Full details of our approval process can be found on our website.
We approve textbooks because we know how important it is for teachers and students to
have the right resources to support their teaching and learning. However, the publisher is
ultimately responsible for the editorial control and quality of this book.
Please note that when teaching the AQA A-level Computer Science course, you must
refer to AQA’s specification as your definitive source of information. While this book has
been written to match the specification, it cannot provide complete coverage of every
aspect of the course.
A wide range of other useful resources can be found on the relevant subject pages of our
website: [Link]
The Publishers would like to thank the following for permission to reproduce copyright material:
P.11 © chombosan - [Link]; P.24 © VvoeVale - iStock via [Link]; P.69 Courtesy of Wikipedia,
The Opte Project ([Link] P.111 © Hodder & Stoughton; P.136 middle
© Sergey Kamshylin - [Link], bottom © mark huls - [Link]; P.137 © Jenny Thompson - [Link];
P.142 screenshot from TRANSYT from TRL Software ([Link]); P.214 © ra3rn - [Link];
P.217 © davemhuntphoto - [Link]; P.218 © Bob Reeves; P.231 top © TheVectorminator - [Link],
bottom © R+R - [Link]; P.267 top © Maksym Yemelyanov - [Link], bottom © finallast -[Link];
P.271 © KarSol - [Link]; P.289 © Igor Mojzes - [Link]; P.295 Courtesy of Wikimedia Commons, author
Ordercrazy, Creative Commons CC 1.0 ([Link]
P.313 © Maxim Pavlov - [Link]
Every effort has been made to trace all copyright holders, but if any have been inadvertently overlooked the
Publishers will be pleased to make the necessary arrangements at the first opportunity.
Although every effort has been made to ensure that website addresses are correct at time of going to press, Hodder
Education cannot be held responsible for the content of any website mentioned. It is sometimes possible to find a
relocated web page by typing in the address of the home page for a website in the URL window of your browser.
Hachette UK’s policy is to use papers that are natural, renewable and recyclable products and made from
wood grown in sustainable forests. The logging and manufacturing processes are expected to conform to the
environmental regulations of the country of origin.
Orders: please contact Bookpoint Ltd, 130 Milton Park, Abingdon, Oxon OX14 4SB.
Telephone: (44) 01235 827720. Fax: (44) 01235 400454. Lines are open 9.00–17.00, Monday to Saturday,
with a 24-hour message answering service. Visit our website at [Link]
© Bob Reeves 2015
First published in 2015 by
Hodder Education
An Hachette UK Company,
Carmelite House
50 Victoria Embankment
London EC4Y 0DZ
[Link]
Impression number 5 4 3 2 1
Year 2019 2018 2017 2016 2015
All rights reserved. Apart from any use permitted under UK copyright law, no part of this publication may be
reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying and
recording, or held within any information storage and retrieval system, without permission in writing from the
publisher or under licence from the Copyright Licensing Agency Limited. Further details of such licences (for
reprographic reproduction) may be obtained from the Copyright Licensing Agency Limited, Saffron House, 6–10
Kirby Street, London EC1N 8TS.
Cover photo © LaCozza – Fotolia
A catalogue record for this title is available from the British Library
ISBN 978 1 447 183951 1
Contents
Introduction v
Section One Fundamentals of programming
1 Programming basics 2
2 Programming concepts 8
3 Basic operations in programming languages 14
4 Subroutines, local and global variables 22
5 Structured programming 28
6 Object-oriented programming concepts 35
Practice questions 46
Section Two Fundamentals of data structures
7 Data Structures and abstract data types 50
8 Queues and stacks 57
9 Graphs and trees 67
10 Hash tables and dictionaries 77
11 Vectors 84
Practice questions 90
Section Three Fundamentals of algorithms
12 Graph and tree traversal 92
13 Dijkstra’s shortest path algorithm 101
14 Search algorithms - binary, binary tree and
linear search 110
15 Reverse Polish Notation 117
16 Sorting algorithms – bubble and merge 124
Practice questions 132
Section Four Fundamentals of computational thinking
17 Abstraction and automation 134
18 Finite state machines 145
19 The Turing machine 150
20 Regular and context-free languages 156
21 Maths for regular expressions 164
22 Big O notation and classification of algorithms 169 iii
Practice questions 179
Section Five Fundamentals of data representation
23 Number systems 182
24 Number bases 187
25 The binary number system 194
26 Coding systems 207
27 Encryption 220
Practice questions 228
 Section Six Fundamentals of computer systems
28 Hardware and software 230
29 Classification of programming languages
and translation 238
30 Boolean algebra 245
31 Logic gates 256
Practice questions 264
Section Seven Fundamentals of computer organisation and
architecture
32 Internal hardware of a computer 266
33 The stored program concept and processor
components 274
34 The processor instruction set and addressing modes 281
35 External hardware devices 287
Practice questions 298
Section Eight Consequences of uses of computing
36 Moral, ethical, legal and cultural issues 300
Section Nine Fundamentals of communication and networking
37 Communication basics 310
38 Networks 317
39 The Internet 326
40 Internet security 339
41 Transmission Control Protocol/Internet
Protocol (TCP/IP) 347
42 The client-server model 353
Practice questions 360
Section Ten Fundamentals of databases
43 Relational databases 364
44 Structured query language (SQL) 375
CONTENTS

45 Big data 382

Practice questions 390
Section Eleven Fundamentals of functional programming
46 Basics of functional programming 394
iv 47 Writing functional programs 400
Practice questions 405
Section Twelve Software development
48 Aspects of software development 408
49 Non-exam assessment (NEA) 417
Glossary 423
Index 433
Introduction

● What is computer science?

The world of computer science continues to develop at an amazing rate.
If you had spoken to an A-level student embarking on a computer science
course just ten years ago they might not have believed that in the year
2015 we would all be permanently connected to the Internet on smart
phones, watching movies in high definition on 55-inch curved-screen TVs,
streaming our favourite music to our phones from a database of millions
of tracks stored in ‘the cloud’ or carrying round a tablet that has more
processing power than the flight computer on the now decommissioned
space shuttle.
No-one really knows where the next ten years will take us. The challenge
for you as a computer scientist is to be able to respond to this ever-changing
world and to develop the knowledge and skills that will help you to
understand technology that hasn’t yet been invented!
Studying A-level computer science gives you a solid foundation in the
underlying principles of computing, for example: understanding how
algorithms and computer code are written; how data are stored; how data
are transmitted around networks; and how hardware and software work.
It also provides you with a deeper level of understanding that goes beyond
the actual technology. For example, you will learn about how to use
computation to solve problems and about the close links between computer
science, mathematics and physics.
You might be surprised to learn that many of the key principles of
computing were developed before the modern computer, with some
concepts going back to the ancient Greeks. At the same time, you will
v
be learning about the latest methods for solving computable problems in
today’s world and developing your own solutions in the form of programs
or apps.
Studying computer science at A level is challenging, but it is also highly
rewarding. There are very few jobs that do not involve the use of computers
and having a good understanding of the science behind them will
effectively prepare you for further study or employment.
 ● Course coverage and how to use this book
This book has been written to provide complete coverage of the AQA
Computer Science specifications for AS and A level that are taught from
September 2015. The content of the book is matched and sequenced
according to the specification, and organised into sections in accordance
with the main specification headings used by AQA.
Students studying A level need to be familiar with all of the content of the
AS specification and in addition need to cover those sections highlighted
throughout the text and are flagged up as A level only. There is support
for every section of the specification including the written papers and
coursework element.
The main objective of the book is to provide a solid foundation in the
theoretical aspects of the course. Further support and practical examples of
coded solutions are provided on line via Dynamic Learning.

Chapters contain:
Specification coverage KEYWORDS
Taken directly from the All of the keywords are identified with
specification, it shows which concise definitions. These form a
elements of AS and A level are glossary, which is useful for revision
covered within each chapter. and to check understanding.

2
condition is met – either you run out of words to count or the device comes

Programming
to a wall. An iterative process has two parts – a pair of commands that show

REPETITION (ITERATION)
KEYWORDS the start and finish of the process to be repeated and some sort of condition.
Definite iteration: a process that There are two basic forms of iteration – definite and indefinite. Definite

concepts repeats a set number of times.

Indefinite iteration: a process
that repeats until a certain
iteration means that the instructions are repeated in a loop a certain number
of times. Indefinite iteration means that the instructions are repeated in a
loop until some other event stops it. Iteration statements are often referred to
condition is met. as loops, as they go round and round. Let’s look at an example of each.
Loop: a repeated process.
Definite iteration
If you want a process to be carried out a set number of times you will need
to use definite iteration. For example, the following code could be used to
SPECIFICATION COVERAGE operate a robotic device. It will move a device forward 40 units:
[Link] Programming concepts For Counter = 1 To 40
Move forward 1 unit
Next
LEARNING OBJECTIVES LEARNING OBJECTIVES
In this chapter you will learn how to:
After it has moved forward 40 units it will stop. It will try and move
irrespective of whether it meets an obstacle or not. This is known as a
Matched to the specification, •
•
put lines of code in the correct sequence
write an assignment statement
For...Next loop as it will carry out the instruction for a set number
of times.

these summarise what you will •

•
write a selection statement
write an iterative (repeat) statement
Indefinite iteration
In this case the loop is repeated until a specified condition is met – so
learn by the end of the chapter.
• use loops.
it uses a selection process to decide whether or not to carry on (or even
whether to start) a process.
INTRODUCTION

This routine moves a device forward until the sensor detects an obstacle:
INTRODUCTION
Repeat
In simple terms, programming is just a case of writing a series
of instructions in order to complete a task. Depending on which Move forward 1 unit
programming language you use, this is done in different ways. Until Sensors locate an obstacle
However, there are certain constructs that are common to all high-
level languages. These building blocks of programming are sequence,
selection and repetition (also known as iteration). There is also a further
fundamental principle called assignment.

● Sequencing
Sequencing instructions correctly is critical when programming. In simple
terms this means making sure that each line of code is executed in the right
8 order. For example, a DVD recorder may have a simple program to record a 11
TV channel at a certain time. The sequence of events would be:
Set time to record = 15:00
Set channel to record = Channel 4
vi Check time

INTRODUCTION If time = 15:00 Then Record

If any of these instructions were wrong, missed out or executed in the

This is a concise introduction to wrong order, then the program would not work correctly. Figure 2.1 Parking sensor

set the scene.

The main text Diagrams and images

This contains detailed The book uses diagrams and
definitions, explanations and images wherever possible to aid
examples. understanding of the key points.
 Acknowledgements

Introduction
Dave Fogg for producing the VB code examples used.
Matthew Walker for producing the Python code example used.
Paul Varey for his initial proofread.
Dedicated to Tommy and Eli.

Code examples
Where relevant there are examples of
pseudo-code or actual code to demonstrate
particular concepts. Code examples in
this book are mainly written using the
Visual Basic framework. Visual Basic 2010 TASKS
Express has been used as this is available KEY POINTS
All of the main points These are activities designed to
as a free download. The code can also be test your understanding of the
migrated into other versions of VB. Note for each chapter are
summarised. These are contents of the chapter. These
that code that is longer than one line in the may be written exercises or
book is shown with an underscore (_). It particularly useful as a
revision aid. computer tasks.
should be input as one line in VB.

There is no way of knowing how many times this loop will be repeated so
potentially it could go on forever – a so-called infinite loop. This example is

REPETITION (ITERATION)
TASKS
also known as a Repeat...Until loop as it repeats the instruction until a KEY POINTS
condition is met. 1 Write examples of the three main types of programming statement:
• Programming statements
assignment, selection, iteration.
To check for a condition before the code is run, you can use what is are built up using four main
constructs: sequence, 2 Give two examples where an iterative process might be used.
commonly called a While or Do while loop. For example, a program
that converts marks to grades might use the following line of code:
selection, repetition (also 3 Explain the difference between definite and indefinite iteration.
known as iteration) and
4 Explain the concept of a nested statement.
While Mark <=100 assignment.
5 Why is the sequence of programming statements so important? Use
Convert Mark to Grade • Sequence is putting the
an example to explain.
instructions in the correct
End While order to perform a task. 6 What is syntax and why is it important? Use an example to explain.
In this case, it checks the condition before the code is run. If the mark is • Selection statements
over 100, then the code inside the While loop will not even start. choose what action to take
based on specified criteria.
Nested loops For example, If...Then STUDY / RESEARCH TASKS
statements. 1 Identify a real-life situation where it might be useful to use the
Tens Units
In the same way that you can nest selection statements together, it is also
possible to have a loop within a loop. For example, an algorithm to create • Iteration is where a particular following constructs within a program:
0 0 0 0 3 5 2 8 step or steps are repeated a) iteration
a web counter on a web page may have 8 digits allowing for numbers up to
in order to achieve a certain b) selection.
Figure 2.2 A web counter 10 million. Starting with the units, the program counts from 0 to 9. When
task. For example, For...
it reaches 9, it starts again from 0, but it also has to increment the value in Next statements. 2 Write a program that reads in a file of test marks and then converts
the tens column by 1. The units will move round 10 times before the tens, them to grades.
• Assignment is the process
then moves once. The tens column moves around 10 times and then the of giving values to variables 3 Write a program that works out the postage charges for parcels of
hundreds increments by 1 and so on. and constants. For example, different weights.
KEYWORD The same algorithm can therefore be used for each digit and can be nested Age = 25. 4 Write a program that simulates the odometer on a car.
Sequence: the principle of putting together so that the code is carried out in the correct sequence. The code
the correct instructions in the below shows a nested loop just for the units and tens:
right order within a program.
Tens = 0
Units = 0 CASE STUDY 1: BANKING – THE BENEFITS OF TECHNOLOGY
While Tens < 10 Around 30 years ago, if you wanted to carry out any banking transaction
2 Programming concepts

you had to do it between the hours of 9 a.m. and 3 p.m. on a weekday as

While Units < 10 this was when banks used to open. The invention of cash machines in
the 1980s was a technological revolution giving customers access to
Output Tens and Units to web counter their money 24 hours a day. The invention of online banking in the 1990s
Units = Units + 1 meant that almost all transactions could be done at any time on any day
of the week, including paying bills, setting up direct debits and moving
End While money from one account to another. Some estimates suggest that as
many as half of all web users now do their banking online.
Tens = Tens + 1
Units = 0
End While
12 Notice that the way the code is indented indicates the sequence of events. This 13
shows that for every iteration of the outer loop, the inner loop will be completed.
Section One: Practice questions
Structures such as those mentioned in this chapter are one of the
1 The following code is part of a stock control system.
characteristics of a high-level language. They are easy to understand when they
Dim Name As String
are viewed in isolation, but the problems start when you try to put a series of
constructs together to do something more useful than deciding if someone
is old enough to drive a car or to move a device forwards. In order to create
Dim Price As Real
Const VAT = 0.2 vii
larger, more useful programs, you need to plan ahead and organise your code. Type RecordDetails
Practice questions can be found at the end of the section on pages RecordType As String * 14
4 6 and 4 7 . RecordCurrent As Integer
RecordRestock As Integer
End Type

CASE STUDY Practice questions STUDY/RESEARCH TASKS

These provide real-life These are revision These questions go beyond
examples of the applications questions designed to the specification and provide a
of computing. check understanding of further challenge designed to
the topics covered across encourage you to ‘read around
the whole section. the subject’ or develop your
skills and knowledge further.
Section One:
Fundamentals of
programming
 1 Programming basics

SPECIFICATION COVERAGE
[Link] Data types
[Link] Programming concepts
[Link] Constants and variables in a programming language
[Link] Integers

LEARNING OBJECTIVES
In this chapter you will learn:
• the basic principles of writing instructions in the form of
programming code
• what constants and variables are and how to use them
• what the main data types are
• how to store data using meaningful names.

INTRODUCTION
In its simplest form a computer program can be seen as a list
KEYWORDS of instructions that a computer has to work through in a logical
Memory: the location where sequence in order to carry out a specific task. The instructions that
instructions and data are stored make up a program are all stored in memory on the computer along
on the computer. with the data that is needed to make the program work.
Algorithm: a sequence of Programs (also known as applications or apps) are created by writing
steps that can be followed to lines of code to carry out algorithms. An algorithm is the steps required
complete a task and that always to perform a particular task and the programming code contains the
terminates. actual instructions written in a programming language. This language is
Syntax: the rules of how words in itself an application that has been written by someone else to enable
are used within a given language. you to write your own programs.
2 In the same way that there are lots of different languages you can learn
to speak, there are also lots of programming languages, and in the same
way that some languages have many different dialects, there are also
different versions of some of the more popular programming languages.
Another similarity with natural languages is that each programming
language has its own vocabulary and rules that define how the words
must be put together. These rules are known as the syntax of the
language. The difference between learning a foreign (natural) language
and a computer language is that there are far fewer words to learn in a
computer language but the rules are much more rigid.
 ● Naming and storing data

CONSTANTS AND VARIABLES

In addition to instructions, the computer program also needs data to work
with. For example, to add two numbers together requires an add instruction
and then the two numbers that need to be added. You need to give these two
data items names so that the computer will know which data to use.
The data are stored in memory along with the instructions. You could view
KEYWORD memory rather like a series of pigeon-holes, each having a unique address,
Memory address: a specific known as a memory address.
location in memory where
instructions or data are stored. It is a really good idea to use names that indicate the purpose of the
data – in the case of the example above the two numbers might be called
Number1 and Number2. Using meaningful names will help you when they
are trying to trace bugs and it also allows other programmers to follow the
code more easily. It is good practice to adopt a common naming convention.
In this case the first character in upper case and the rest in lower case.
This process of giving data values is called ‘assigning’, and it looks
something like these two:
Number1 23
Name "Derek"
The means ‘becomes’ or ‘equals’. Number1 is an example of a variable.
In the example above it has been given a value of 23, though this value
will change while the program is being run. Name is another example of a
variable and has been given the value "Derek".
Different programming languages have slightly different ways of assigning
KEYWORD values. For example, you may need to use the equals sign to make the
Assignment: the process of assignment in the code you are writing. So a simple algorithm to add two
giving a value to a variable or numbers together might look like this:
constant.
Number1 = 2
Number2 = 3
Answer = Number1 + Number2
Figure 1.1 shows a simplified visualisation of how this program is handled.
There will be millions of memory addresses, of which just three are shown
in this diagram.
Memory address 1000 1001 1002
Variable Number1 Number2 Answer
Data 2 3 5

Figure 1.1
3

● Constants and variables

Data are stored either as constants or as variables. Constants (as you’d
KEYWORDS expect from the name) have values that are fixed for the duration of a
Constant: an item of data whose program. For example, if you were writing a program that converted miles
value does not change. into kilometres you could set the conversion rate as a constant because it will
Variable: an item of data whose never change. In this case we could call the constant ConvertMilestoKm
value could change while the and assign it a value of 1.6 as there are approximately 1.6 km to the mile.
program is being run. Then whenever we want to convert a distance in miles to its metric equivalent
we would multiply it by the constant ConvertMilestoKm.
 Notice that the name given to the constant is self-explanatory. We could
have just called it Constant1. However, by giving it a meaningful name
it makes the code easier to work with as the program gets bigger. It also
makes it easier for anyone else that looks at the code, to work out what the
program is doing. This is important for three main reasons:
KEYWORD ● It makes it easier to find and correct errors/bugs in code. This is called
Debug: the process of finding debugging.
and correcting errors in ● There are many occasions where there are several programmers working
programs. on the same program at the same time, so having a sensible naming
convention makes it easier for everyone to understand.
● It will be easier to update the code later on when further versions of the

program are created.

The value of variables can change as a program is being run. For example,
the same conversion program will require the user to type in the number
of miles they want to convert. This number will probably be different each
time the user enters data. Therefore, you need to have a variable that you
could call NumberOfMiles.
There are lots of other examples – the number of answers a pupil has got right
in a test would (hopefully) increase as they work their way through a test so the
data would have to be stored as a variable. The password a user uses to access a
network can be changed at any time, so it would also be classed as a variable.

Variable and constant declaration

Declaring a constant or variable means that when you are writing code you
describe (or declare) the variables and constants that you are going to use
before you actually use them in your program.
Some programming languages force you to declare the variables and
constants you intend to use in your program before you start writing any
code. The benefits of doing this are that it forces you to plan first and the
KEYWORD computer will quickly identify variables it does not recognise.
Declaration: the process of There are two parts to a declaration. You need to supply a suitable name
1 Programming basics

defining variables and constants in for the constant/variable and you need to specify the data type that will be
terms of their name and data type. used. The declarations might look something like this:
Dimension Age As Integer
Dimension Name As String
Dimension WearsGlasses As Boolean
Dimension or Dim is one of the command words used in Visual Basic to
indicate that a variable is being declared. Once you have declared a variable
it starts with a default value. In the above examples Age will start as zero,
4 Name as nothing (also known as the empty string) and WearsGlasses
will start with the value False. Other languages may use different default
values so it is good practice to assign an initial value to the variable just to
make sure it is correct.

● Data types
It is important to consider how you want your program to handle data. For
example, to create the miles to kilometres conversion program, you have to
tell the program that miles and kilometres both need to be stored as numbers.
 There are lots of data types you might need to use and you need to think
carefully about the best type to use. For example, if storing numbers, how

DATA TYPES
KEYWORD
accurate do you need the number to be? Will a whole number be accurate
Data type: determines what sort
of data are being stored and how enough or will you need decimals? In addition to numbers, you will
it will be handled by the program. probably want to store other data such as a person’s name, their date of
birth or their gender.
All programming languages offer a range of data types but the actual name
of the data type may vary from language to language. Here are some of the
most common data types:
● Integer: This is the mathematical name for any positive or negative

whole number. This might be used to store the number of cars sold
in a particular month or the number of pupils in a class. The range of
KEYWORD numbers that can be stored depends on how much memory is allocated.
Integer: any whole positive or For example, an integer in Visual Basic can store numbers between
negative number including zero. –2 147 483 648 through to +2 147 483 647.
Declaring a number as an integer means that the program will then
handle the data accordingly. For example, 2 + 3 will equal 5. In some
languages, if you did not set it to integer 2 + 3 would equal 23 (two three).
● Real/Float: This is a number that has a fractional or decimal part, for

example 3.5 or 3 _21 . In our miles to kilometres conversion program, you

would need to store both miles and kilometres using this data type as the
user might want to convert a number that is not a whole number. Other
examples might include a person’s height in metres or their weight in
kilograms.
● Text/String: This data type is used to store characters, which could be

text or numbers. For example, you could use this to store a person’s
name or address. Some programming languages refer to this data type as
alphanumeric because you can actually store any character you want in a
string whilst text implies it can only store letters. Text or string variables
are normally shown in quotation marks. For example you might assign
the name Frank to a variable like this: Name "Frank". House
numbers and phone numbers are often stored as text / string as although
they are numbers, you would never need to carry out any calculations on
them and in the case of telephone numbers the leading zero is important
and would be omitted if stored as a number.
● Boolean: The simplest data type is a simple yes/no or true/false. This

is called a Boolean data type. It is named after George Boole who

discovered the principles behind logic statements. Boolean data types
can be used to store any kind of data where there are two possible values.
● Character: This data type allows you to store an individual character,

which might be a letter, number or symbol. All computers have a defined

character set, which is the range of characters that it understands. This
would commonly be all the upper and lower case letters, plus other 5
keyboard characters and any special characters.
● Date/Time: This will store data in a format that is easily identifiable as

a date or time, e.g. 30.04.2014 or 12:30. The program will then handle
the data accordingly. For example, if you added 5 to the date, it would
tell you the date in five days’ time. 30.05.2014 + 5 would become
04.06.2015. If you did not declare it as a date you may get the wrong
answer, for example 30.05.2019.
● Pointer/Reference: This data type is used to store a value that will point to or

reference a location in the memory of the computer. If you think of memory

 as a series of pigeon-holes or addresses where instructions and data are
KEYWORD stored, the pointer/reference is used in a program to go to a specific address.
For example, you could set up a pointer called Pointer1 and put
Pointer: a data item that
address 1001 in it. The program would then go to memory address 1001
identifies a particular element in
a data structure – normally the and take the data from it. In the example below it would be the data
front or rear. assigned to Number2. Other lines of code will then be needed to tell the
program what to do with the data it finds there.
Figure 1.2 shows how a pointer is used to reference an item of data.
Pointer1 = 1001

Memory address 1000 1001 1002 1003

Number1 Number2 Add Answer

KEYWORDS Figure 1.2

Array: a set of related data ● Array: An array is a collection of data items of the same type. For
items stored under a single example, if you wanted to store a collection of names in a school register,
identifier. Can work on one or you could call this Register and each item of data would be stored
more dimensions. as text. Each individual name in the array is called an element. Every
Element: an single value within a element is numbered so that Register(2) would be the second person
set or list – also called a member. in the array, Register(4) the fourth person and so on. Note that 0 is
Record: one line of a text file. often used as the first element of an array, rather than 1. If this was the
case then Register(2) would actually be the third person in the array,
Register(4) the fifth and so on.

Brown
Figure 1.3 shows a simple array with six elements. Register(2) =
Hussain, Register(4) = Schmidt (assuming array indexing
Hussain starts at 1).
Koening ● Records: This is used to store a collection of related data items, where
the items all have different data types. For example, you might set
Schmidt
up a record called Book, which is used to store the title, author
Torvill name and ISBN of a book. Title and Author are text whereas the
PublicationDate is set as a Date data type.
West
You could write it like this:
1 Programming basics

Figure 1.3
Book = Record
Title, Author As Text * 50
ISBN As Text * 13
PublicationDate As Date
When the program is run, every time data are entered for the book, the
user will type in up to 50 characters of text for the title and author and
then the ISBN. A variable could now be set up using this record data
type and this variable would contain all of this data.

6
● Built-in and user-defined data types
Built-in data types are those that are provided with the programming
language that you are using. The list of built-in types varies from language
to language, but all will include versions of the types listed above.
Most programming languages allow users to make up their own data types,
usually by combining existing data types together. These are simply called
user-defined data types. For example, if you were making a program to
store user names and IDs, you may create a user-defined data type called
Logon made up of a set number of characters and numbers.
 Type Logon
UserName As String * 10

BUILT-IN AND USER-DEFINED DATA TYPES

UserID As Integer * 5
End Type
This code will set a new data type called Logon, which will be made up
of a 10-character user name followed by a 5-digit user ID. In total, the data
type will have 15 characters/digits to store the data.
The reasons for creating user-defined types are mainly to do with efficiency.
As you start to write your own programs you will find that they can get
very long and complex and that debugging can be very time-consuming.
Most programmers try to make their code as organised and efficient as
possible as this will save them time as the program develops. For example,
it is easier to reuse a block of code rather than have to write it all over again.
Most programmers aim to create code that is ‘elegant’. This means that it
does exactly what it is supposed to do as efficiently as possible. Often this
means writing as few lines of code as possible with no repeated coding.
Using a user-defined data type is just one example of where it is possible to
be more efficient. With our example of storing Logon information using a
user-defined variable, because all the data are stored in one variable rather
than two, when the program needs this information, we only need to access
one variable rather than two.
Practice questions can be found at the end of the section on pages 46
and 47.

KEY POINTS
TASKS
• Programming languages are
used to write applications 1 Give two reasons why it is a good idea to use meaningful variable names.
(apps). 2 Use examples to explain the difference between a constant and a
• An algorithm is a sequence variable.
of instructions that can be 3 Why is it important to declare all variables and constants at the
followed to complete a task. beginning of a program?
Algorithms always terminate.
4 Explain the difference between a value and a variable.
• Programming code is
5 Suggest suitable data types and variable names for:
made up of algorithms that
are implemented within a a) the current rate of VAT
programming language. b) today’s date
c) the total takings from a shop
• Instructions are stored in
memory along with the data d) a person’s date of birth
required by the program. e) which wrist a person wears a watch on.
• Data are stored and named
according to certain 7
conventions. STUDY / RESEARCH TASKS
• Variables and constants are
used to store data and must be 1 A list of data is also known as a one-dimensional array. Find out what
declared in some languages. two- and three-dimensional arrays are and give examples of where
you might use each.
• There are several data
types built in to every 2 Identify the built-in data types for the main programming language
programming language and that is used in your school or college.
the programmer can also 3 Research data types that are specifically used to store sound and
define their own. video data. How do they differ from other data types?
 2 Programming
concepts

SPECIFICATION COVERAGE
[Link] Programming concepts

LEARNING OBJECTIVES
In this chapter you will learn how to:
• put lines of code in the correct sequence
• write an assignment statement
• write a selection statement
• write an iterative (repeat) statement
• use loops.

INTRODUCTION
In simple terms, programming is just a case of writing a series
of instructions in order to complete a task. Depending on which
programming language you use, this is done in different ways.
However, there are certain constructs that are common to all high-
level languages. These building blocks of programming are sequence,
selection and repetition (also known as iteration). There is also a further
fundamental principle called assignment.

● Sequencing
Sequencing instructions correctly is critical when programming. In simple
terms this means making sure that each line of code is executed in the right
8 order. For example, a DVD recorder may have a simple program to record a
TV channel at a certain time. The sequence of events would be:
Set time to record = 15:00
Set channel to record = Channel 4
Check time
If time = 15:00 Then Record
If any of these instructions were wrong, missed out or executed in the
wrong order, then the program would not work correctly.
 The actual process of writing statements varies from one programming
KEYWORD language to another. This is because all languages use different syntax.

SELECTION
Syntax: the rules of how Common usage of the word syntax refers to the way that sentences are
words are used within a given structured to create well-formed sentences. For example, the sentence
language.
‘Birds south fly in the winter’ is syntactically incorrect because the verb
needs to come after the noun. Programming languages work in the same
way and have certain rules that programmers need to stick to otherwise
the code will not work.

● Assignment
We met the concept of an assignment statement in Chapter 1. Assignment
gives a value to a variable or constant. For example you might be using a
variable called Age so the code:
Age 34
will set the variable Age to have the value 34.
The value stored in the variable could change as the program is run. For
example, a computer game might use a variable called Score. At the
beginning of the game the value is set to 0. Each time the player scores
a point, the assignment process takes place again to reset the value of
Score to 1 and so on.
Assigning values will take place over and over again while a program is
being run. Initially, the programmer will assign a value to the variable.
Then as the program runs, the algorithms in the program code will
calculate and then return (re-assign) the latest value. Assignments are the
fundamental building blocks of any computer program because they define
the data the program is going to be using.

● Selection
The selection process allows a computer to compare values and then
KEYWORD decide what course of action to take. For example you might want your
Selection: the principle of program to decide if someone is old enough to drive a car. The selection
choosing what action to take process for this might look something like this:
based on certain criteria.
If Age < 17 Then
Output = "Not old enough to drive"
Else
Output = "Old enough to drive"
End If 9
In this case, the computer is making a decision based on the value of the
variable Age. If the value of Age is less than 17 it will output the text
string "Not old enough to drive". For any other age it will output
the text string "Old enough to drive". The If statement is a very
common construct. In this case it is used to tell the program what to do
if the statement is true using the If...Then construct. If the statement
is false, it uses the Else part of the code. This is a very simple selection
statement with only two outcomes.
 Nested selection
You can carry out more complex selections by using a nested statement.
KEYWORD For example, a program could be written to work out how much to charge
Nesting: placing one set of to send parcels of different weights. This could be achieved using the
instructions within another set following sequence of selection statements:
of instructions.
If Weight >= 2000 Then
Price = £10
Else If Weight >= 1500 Then
Price = £7.50
Else If Weight >= 1000 Then
Price = £5
Else
Price = £2.50
End If
When the weight is input, it works through the lines of code in the If
statement and returns the correct value. For example, if the parcel weighs
1700 g it will cost £7.50 as it is between 1500 g and 1999 g. If it weighed
2000 g or more, the If statement would return £10.
In some languages complex selections can be implemented using constructs
such as this Case statement. The following example shows a section of
code that allows the user to type in a country code to identify where a
parcel is being sent to:
Select Case ParcelDestination
Case 1
WriteLine ("Mainland UK")
2 Programming concepts

Case 2
WriteLine ("Europe")
Case 3
WriteLine ("USA")
Case Else
WriteLine ("Rest of the World")
End Select

10
This routine takes the value of the variable ParcelDestination and
compares it against the different criteria. So if ParcelDestination is
1 then Mainland UK will be printed to the screen.

● Repetition (Iteration)
KEYWORD It is useful to be able to repeat a process in a program. This is usually called
Iteration: the principle of iteration. For example you might want to count the number of words in
repeating processes. a block of text or you may want to keep a device moving forward until it
reaches a wall. Both these routines involve repeating something until a
 condition is met – either you run out of words to count or the device comes
to a wall. An iterative process has two parts – a pair of commands that show

REPETITION (ITERATION)
KEYWORDS the start and finish of the process to be repeated and some sort of condition.
Definite iteration: a process that There are two basic forms of iteration – definite and indefinite. Definite
repeats a set number of times. iteration means that the instructions are repeated in a loop a certain number
Indefinite iteration: a process of times. Indefinite iteration means that the instructions are repeated in a
that repeats until a certain loop until some other event stops it. Iteration statements are often referred to
condition is met. as loops, as they go round and round. Let’s look at an example of each.
Loop: a repeated process.
Definite iteration
If you want a process to be carried out a set number of times you will need
to use definite iteration. For example, the following code could be used to
operate a robotic device. It will move a device forward 40 units:
For Counter = 1 To 40
Move forward 1 unit
Next
After it has moved forward 40 units it will stop. It will try and move
irrespective of whether it meets an obstacle or not. This is known as a
For...Next loop as it will carry out the instruction for a set number
of times.

Indefinite iteration
In this case the loop is repeated until a specified condition is met – so
it uses a selection process to decide whether or not to carry on (or even
whether to start) a process.
This routine moves a device forward until the sensor detects an obstacle:
Repeat
Move forward 1 unit
Until Sensors locate an obstacle

11

Figure 2.1 Parking sensor

 There is no way of knowing how many times this loop will be repeated so
potentially it could go on forever – a so-called infinite loop. This example is
also known as a Repeat...Until loop as it repeats the instruction until a
condition is met.
To check for a condition before the code is run, you can use what is
commonly called a While or Do while loop. For example, a program
that converts marks to grades might use the following line of code:
While Mark <=100
Convert Mark to Grade
End While
In this case, it checks the condition before the code is run. If the mark is
over 100, then the code inside the While loop will not even start.
Nested loops
Tens Units
In the same way that you can nest selection statements together, it is also
possible to have a loop within a loop. For example, an algorithm to create
0 0 0 0 3 5 2 8
a web counter on a web page may have 8 digits allowing for numbers up to
Figure 2.2 A web counter 10 million. Starting with the units, the program counts from 0 to 9. When
it reaches 9, it starts again from 0, but it also has to increment the value in
the tens column by 1. The units will move round 10 times before the tens,
then moves once. The tens column moves around 10 times and then the
hundreds increments by 1 and so on.
KEYWORD The same algorithm can therefore be used for each digit and can be nested
Sequence: the principle of putting together so that the code is carried out in the correct sequence. The code
the correct instructions in the below shows a nested loop just for the units and tens:
right order within a program.
Tens = 0
Units = 0
While Tens < 10
2 Programming concepts

While Units < 10

Output Tens and Units to web counter
Units = Units + 1
End While
Tens = Tens + 1
Units = 0
End While
12 Notice that the way the code is indented indicates the sequence of events. This
shows that for every iteration of the outer loop, the inner loop will be completed.
Structures such as those mentioned in this chapter are one of the
characteristics of a high-level language. They are easy to understand when they
are viewed in isolation, but the problems start when you try to put a series of
constructs together to do something more useful than deciding if someone
is old enough to drive a car or to move a device forwards. In order to create
larger, more useful programs, you need to plan ahead and organise your code.
Practice questions can be found at the end of the section on pages
46 and 47.
 REPETITION (ITERATION)
TASKS
KEY POINTS
1 Write examples of the three main types of programming statement:
• Programming statements
assignment, selection, iteration.
are built up using four main
constructs: sequence, 2 Give two examples where an iterative process might be used.
selection, repetition (also 3 Explain the difference between definite and indefinite iteration.
known as iteration) and
4 Explain the concept of a nested statement.
assignment.
5 Why is the sequence of programming statements so important? Use
• Sequence is putting the
an example to explain.
instructions in the correct
order to perform a task. 6 What is syntax and why is it important? Use an example to explain.
• Selection statements
choose what action to take
based on specified criteria.
For example, If...Then STUDY / RESEARCH TASKS
statements. 1 Identify a real-life situation where it might be useful to use the
• Iteration is where a particular following constructs within a program:
step or steps are repeated a) iteration
in order to achieve a certain b) selection.
task. For example, For...
Next statements. 2 Write a program that reads in a file of test marks and then converts
them to grades.
• Assignment is the process
of giving values to variables 3 Write a program that works out the postage charges for parcels of
and constants. For example, different weights.
Age = 25. 4 Write a program that simulates the odometer on a car.

13
 3 Basic operations
in programming
languages
SPECIFICATION COVERAGE
[Link] Arithmetic operations in a programming language
[Link] Relational operations in a programming language
[Link] Boolean operations in a programming language
[Link] String-handling operations in a programming language
[Link] Random number generation in a programming language

LEARNING OBJECTIVES
In this chapter you will learn:
• the correct syntax for writing basic programming code
• how to construct arithmetic operations, Boolean operations and
relational operations
• how to handle basic string operations
• how Visual Basic, Python and C# implement these operations.

INTRODUCTION
There are a number of basic operations that you can perform on text and
numeric data when programming. These fall into four main categories:
arithmetic operations, relational operations, Boolean operations and string
handling. In this chapter all of these basic operations are explained with
simple examples to illustrate each. The examples are based on Visual Basic
and there is also a look-up table at the end the chapter to show these how
these basic operations could be implemented in Python and C#.

When programming, the syntax for each operation will vary depending
14 on which language you are using. In practice, when creating full programs
you will be using many of these operations in combination to perform
particular tasks. In Sections Two and Three, you will see many of these
KEYWORD basic operations being used in context.
Variable: a data item whose When programming, values are likely to come from a variable or constant,
value will change during the or be generated as part of the program. For example, an assignment
execution of the program. statement that adds two numbers together may use three variables called
Answer, FirstNumber and SecondNumber:
Answer = FirstNumber + SecondNumber
5 = 3 + 2
 Note that in some languages these operations can be carried out on
numeric values or text strings. For example:

ARITHMETIC OPERATIONS
txtAnswer = txtFirstVariable + txtSecondVariable
DavidSmith = David + Smith
This has implications for the programmer as you might expect a simple
addition of 2 + 2 to equal 4. However, 2 + 2 could also result in the answer
22 if the programmer has not defined the values as integers. This is one
reason why it is good practice to declare variables at the beginning of every
program, so that the program knows how to handle the data.

● Arithmetic operations
Most of these are the standard mathematical operations that you use every
KEYWORD day such as add, subtract, multiply and divide.
Arithmetic operation: common ● Addition: The sum of two or more values. Example: 5 = 3 + 2 or
expressions such as +, –, /, ×.
Answer = FirstNumber + SecondNumber.
● Subtraction: One value minus another. Example: 2 = 5 – 3 or

Answer = FirstNumber - SecondNumber.

● Multiplication: The product of two values. Example: 6 = 3 * 2 or

Answer = FirstNumber * SecondNumber.

● Division of real numbers: A real number is one with a fractional part so

may result in an answer with a fractional part. Example: 3.1 = 6.2/2 or

Answer = FirstNumber / SecondNumber (where all variables
have been declared as Real or Float).
● Division of integers: An integer is a whole number and therefore may

generate a number with a remainder. Example: 3r1 = 7/2 or Answer

= FirstNumber / SecondNumber (where all variables have been
declared as Integer). The DIV operation can also be used in the format
Answer = FirstNumber DIV SecondNumber in which case the
quotient and remainder are calculated simultaneously.
● Modulo operation: The modulo or MOD operator is used to divide one

number by another to find the remainder. Example: 1 = 7 MOD 2 or

Answer = FirstNumber MOD SecondNumber as 7/2 = 3r1.
● Exponentiation: Repeated multiplication of a base number in the form

Bn where B is the base number and n is the number of times to repeat

the multiplication. For example 24 is 2 × 2 × 2 × 2. Example: 16 = 2 ^ 4
or Answer = FirstNumber ^ SecondNumber.
● Rounding: Replacing the real value with a simpler representation that
KEYWORDS is close to the original value. For example, 2.315432 becomes 2.3.
Rounding: reducing the number There are various methods for rounding within each programming
of digits used to represent a language such as rounding up and down, or rounding to a specific
number while maintaining a number of decimal places. Example: 2 = Round(2.3) or Answer = 15
value that is approximately Round(FirstNumber).
equivalent. ● Truncating: Shortening a value by cutting it off after a certain number
Truncating: the process of of digits. It is the equivalent of rounding down. There are various
cutting off a number after a methods for truncating within each programming language. Example:
certain number of characters or 2 = Truncate (2.345) or Answer = Truncate(FirstNumber)
decimal places.
where FirstNumber is a decimal value.
● Random number generation: Creating a number to be used in a program

that is random. There are several methods of doing this. Often the
number is set to be generated between two fixed values. There are
 various methods within each programming language. For example:
0.123 = Rnd () or Answer = Rnd().
Random numbers are a very useful tool for programmers. Typical
applications include:
– Creating a range of test data to be used on a new program
– Producing data to use in computer simulations
– Creating random events and movements in computer games
KEYWORDS – Selecting a random sample from a dataset.
However, as most random number generation techniques used
Random number generation:
a function that produces a in programming languages start from a seed value and then use an
completely random number. algorithm to create the random number, it means that the number
cannot be truly random as the algorithm used will produce an element
Pseudo-random number
generator: common in of structure to the results. Consequently, random numbers generated
programming languages, a by programming languages are often referred to as pseudo-random
function that produces a random numbers. This is perfectly adequate for the purposes listed above but in
number that is not 100% random. other circumstances, such as encryption, this level of randomness would
not be sufficient.

● Relational operations
Relational operations work by making comparisons between two data
KEYWORD items. They consist of operands and operators where the operands are the
Relational operations: values and the operator is the comparison being made. For example, in
expressions that compare the operation A > B, A and B are the operands and > is the operator. Most
3 Basic operations in programming languages

two values such as equal to or

programming languages recognise the standard method for representing
greater than.
these operators as shown in Table 3.1.

Table 3.1 Table of relational operators

Relational operator Sign

Equal to = or ==
Not equal to < > or !=
Less than <
Greater than >
Less than or equal to
Greater than or equal to

Relational operations are often performed in order to create selection

statements. For example: If A > 1 Then... means if A is 2 or more then
the next action is carried out. In common with all operations, the comparisons
could also be made between textual data as well as numerical data.
16
● Boolean operations
Boolean operations are those which result in either a TRUE or a FALSE
KEYWORD answer. Boolean algebra is used in logic circuits and is an underlying
Boolean operations: principle to how modern computers work. It is also fundamental to the
expressions that result in a process of searching data whether that is in a database, or on the web. Once
TRUE or FALSE value. the Boolean operation has been evaluated, a further action is then taken. For
example, on a database search, a subset of data would be created containing
records that met the search criteria. The examples below are based on a
scenario where an online dataset is being searched to find a new car.
 The four basic operations are:
● AND: This is known as a conjunction as it adds together the data. For

STRING-HANDLING FUNCTIONS
KEYWORDS
AND: Boolean operation that example, using the search phrase “Four Door AND Less than 3 years old”
outputs true if both inputs are would return a value of TRUE only if both conditions were met, so the
true. car would need to have four doors AND be less than 3 years old.
● OR: This is known as a disjunction, which means that a TRUE result is
OR: Boolean operation that
outputs true if either of its inputs produced if any of the conditions are met. For example, in the search
are true. phrase “Four Door OR Three Door”, only one of the conditions needs to be
NOT: Boolean operation that met to get a TRUE result, so all three- and four-door cars would be listed.
● NOT: This is known as a negation as it reverses the input. For example,
inverts the result so true
becomes false and false “NOT Ford” would result in data that did NOT contain the word Ford.
becomes true. ● XOR: This is known as an exclusive OR and means that a TRUE result

XOR: Boolean operation that is is produced when one or the other condition is met but not both. For
true if either input is true but not example, “Sunroof XOR Air conditioning” would result in data where
if both inputs are true. the car either had a sunroof or air conditioning, but not both. XOR
operations are used extensively when creating logic gates and there is
more on this in Chapter 30.

A B A B

AND OR

A B A B

XOR
NOT

Figure 3.1 Venn diagrams to represent the four basic Boolean operations.

You may have noticed that it is possible to embed relational operators

within Boolean operations. For example, “Four Door AND Less than 3
years old” uses the less than operator. It is also possible to join lots of
Boolean operations together to produce the desired outcome. For example, a
very specific search might be: “Four Door AND Less than 3 years old AND
Ford OR Vauxhall NOT Fiat”.
17

● String-handling functions
At the beginning of the chapter we saw that it is possible to carry out
KEYWORD operations on numbers and text data. This section looks specifically at the
String-handling functions: way in which text can be handled. To be more precise, this section looks
actions that can be carried out at how strings can be handled. A string is a sequence of characters and can
on sequences of characters. actually be made up of text, numbers and symbols. There are many situations
where you will need to work with strings to produce the desired outcome, for
example, searching for strings of characters or combining strings together.
 ● Length: The length of the string is how many characters are used to store
a particular item of data. The string length is often variable although
there is usually an upper limit placed on its size. There are various
operations that you can carry out using the string length. For example,
you may want to set the maximum length or calculate the length of a
particular string of data. For example: Dim LastName As String is
used to define a string data type and Len (Variable1) calculates the
length of data value stored in Variable1.
● Position: Within a text string it is possible to identify the position of
every character. This is useful when you want to extract particular
characters from the string or identify substrings within the data. There
are various operations that you can carry out. For example, to find the
start position of a particular string of characters within another string:
Txt = "JohnSmith22HighStreetLeicester"
AddressPosition = InStr(txt,"22HighStreet")
This would return a value of 10 in this example as that is the position
where the address data starts within the string being searched. This
assumes that the start position is 1. Some languages take the start
position as 0, in which case this would return a value of 9.
● Substring: A substring is a string contained within another string as shown
in the example above. Various techniques can be used to extract data from
anywhere in a string to create a substring providing the start and end
position are known or the start position and length are known. For example:
txt= "JohnSmith22HighStreetLeicester"
3 Basic operations in programming languages

txtAddress = [Link] (10,21)

This would create the substring “22HighStreetLeicester” and store it in a
variable called txtAddress. It does this by starting at position 10 of
the string and then extracting the next 21 characters.
● Concatenation: This is the process of adding strings together to create
another string. For example:
txtFirstName = "John"
txtLastName = "Smith"
txtFullName = txtFirstName + txtLastName
This would create the value “JohnSmith” stored in a variable called
txtFullName.
KEYWORD ● Character codes: Every character that you can use on a computer including
Character code: a binary all the keyboard characters has a corresponding character code, which is
representation of a particular used to identify it. This might be an ASCII code or Unicode (see Chapter 26).
letter, number or special This can be used in various ways, for example, if you need to convert a text
character. value to a numeric value in order to carry out a calculation on it. You might
do this when encrypting data. For example:
asc(Variable1) returns the ASCII code value of the value stored in
Variable1 where Variable1 is a text character.
18
chr(Variable1) returns the text character where Variable1 is an
ASCII code.
chrW(Variable1) returns the Unicode code value of Variable1
where Variable1 is a text character.
In addition to converting strings to character codes, there are a number
of other conversions that a programmer might need to do in order to
manipulate the data further. Most programming languages include specific
functions to carry out these conversions.
 ● String to Integer / Integer to String: An integer is a whole number. Some
programming languages convert between the two automatically if the

EXAMPLES OF COMMON OPERATIONS IN PYTHON AND C#

two variables are declared correctly. For example:
Dim i as Integer
Dim s as String
i = 1
s = i
This would result in s (a string) becoming 1 (an integer). The same code
could be used to reverse the process.
● String to Float / Float to String: A float is also called a real number and
is any number including those with a fractional part. In Visual Basic, a
function exists to carry out this conversion:
[Link](x) will convert the text string x into a Double
data type, used by Visual Basic to store real numbers.
[Link](n) will convert the real number n into a string.
● String to Date-time / Date-Time to String: Date-time is usually stored
with built-in formatting such as [Link] and hh:mm:ss. To
manipulate individual parts of the data, it can be converted into a string.
Most programming languages have built-in functions. For example, in
Visual Basic:
[Link](date) converts the date and time into a string
[Link](String) converts a string into date-time format.

● Examples of common operations

in Python and C#
Table 3.2 gives some examples of how these common operations can be
executed in both Python and C#. Note that there will be other ways of
implementing these operations based on the specific requirements of the
program being written.
You will notice that there are some commonalities between programming
languages and some operations that are handled completely differently.

19
 Table 3.2 Common operations in Python and C#

Operation or Python example C# example

function
Add c = a + b c = a + b
Subtract c = a – b c = a – b
Multiply c = a * b c = a * b
Divide real number c = a / b c = a / b
Divide integer c = a//b Int c = a / b
Modulo c = a % b c = a % b
Exponentiation c = a ** b or exp(n) [Link] (a,b)
Round round (x[,n]) [Link]()
Truncate round (x[, n]) [Link] (a, n)
Truncates according to the size input Truncates the value of a to n places
Random number random() random()
generation

Substring var1 = "JohnSmith" string input = "JohnSmith"

print var1[0 : 4] string sub =
Prints “John” [Link] (0, 4)
Returns the value “John”
Concatenation c = a + b c = a + b
Convert character to Chr() gives the character code value of the Encoding,ASCII,GetBytes () converts a
3 Basic operations in programming languages

character code character character to an ASCII code

Ord() gives the integer value of the [Link]() converts an ASCII code to a
character character
Convert string to integer int() converts a string to an integer .ToInt32 converts a string to a 32-bit integer
str() converts an integer to a string .ToString converts an integer to a string where
the variable before the dot is an integer
Convert string to date-time [Link](format[,t]) converts a ConvertToDateTime(dateString) converts
string into a time with a specified format date-time to string
[Link]() converts the string
contained in the brackets into a date-time format
Convert string to float float() converts string to float .ToFloat converts a string to a float where the
str() converts float to string value before the dot is a string
.ToString converts a float to a string where the
variable before the dot is an integer

Practice questions can be found at the end of the section on

pages 46 and 47.

20
 EXAMPLES OF COMMON OPERATIONS IN PYTHON AND C#
TASKS
1 Write an example of a calculation using each of the arithmetic operators.
2 What is the difference between a division of a real/float and the
division of an integer?
3 Most calculations will get their values from variables. Why are variables
KEY POINTS used in programming rather than just typing the raw values?
• The syntax of a language 4 Use examples to explain the difference between truncation and rounding.
describes the rules that you 5 Why might random numbers be used?
must follow.
6 What is the difference between an OR statement and an XOR
• Arithmetic operations include
statement? Give an example.
common processes such as
add, subtract, multiply and 7 How can you create a substring from a string?
divide. 8 What formats can strings be converted into?
• Other arithmetic operations 9 Why are random numbers generated in programming languages not
include rounding, truncating entirely random?
and exponentiation.
• Most languages include a
random number generator.
• Relational operations
STUDY / RESEARCH TASKS
compare two or more values 1 Write code for a calculator app that allows the user to enter one or
to produce a result. two numbers and then carry out all of the main arithmetic operations.
• Boolean operations return a 2 Write code for an app that allows the user to input two numbers and
true or false value and include then carry out each of the relational operators returning an output of
AND, OR, NOT and XOR. TRUE or FALSE.
• Different types of operations 3 Write code for an app that extracts the vowels from the alphabet.
can be combined to create
more complex expressions. 4 Write code for an app that takes the numbers 1–10 and extracts them
into odd and even numbers.
• String handling is the process
of identifying and extracting 5 Research how Google uses Boolean operators to create accurate
sequences of characters from search results.
a string of characters. 6 Is it possible to produce a completely random number?

21
 4 Subroutines, local
and global variables
SPECIFICATION COVERAGE
[Link] Exception handling
[Link] Subroutines (procedures/functions)
[Link] Parameters of subroutines
[Link] Returning a value/values from a subroutine
[Link] Local variables in subroutines
[Link] Global variables in a programming language

LEARNING OBJECTIVES
In this chapter you will learn:
• what a subroutine is and how they are used to create programs
• how to create subroutines
• what a function is and how to create them
• what parameters and arguments are and how they are used within
a function
KEYWORDS
Subroutine: a named block of
• what local and global variables are.
code designed to carry out a A-level students will learn:
specific task. • what an exception is and how a program should deal with it.
Procedure: another term for a
subroutine.
Subprogram: another term for a
subroutine. INTRODUCTION
Routine: another term for a In programming a subroutine is a named block of programming code
subroutine. that performs a specific task. All programs therefore are made up of a
Local variable: a variable that series of subroutines. They provide structure to programs in the same
is available only in specified way that chapters provide structure to a book. Subroutines are also
22 called procedures, subprograms or routines.
subroutines and functions.
Global variable: a variable that Subroutines use variables that can either be local or global. Local
is available anywhere in the variables are those that can only be used within that subroutine
program. whereas global variables are accessible throughout the program.
 ● Subroutines

SUBROUTINES
A subroutine is self-contained and it carries out one or more related
processes. These processes are sometimes called algorithms, which in turn
are made up of lines of code. Subroutines must be given unique identifiers
or names, which means that once they have been written they can be called
using their name at any time while the program is being run.
For example you may want to write a program to maintain the contents of
a file. You would need to write code to handle tasks such as adding a new
KEYWORD record, amending existing details and deleting an old record. In this case
Event: something that happens you might have a subroutine to handle events that are generated from
when a program is being run. a main menu and then each of the three tasks has its own subroutine.
For example if the variable Selected is set to Add then the procedure
AddRecord would be called.
Subroutine MainMenu
Input Selected
If Selected = "Add" Then Subroutine AddRecord
If Selected = "Amend" Then Subroutine AmendRecord
If Selected = "Delete" Then Subroutine DeleteRecord
End Subroutine
:
Subroutine AddRecord
‘Code to add a new record to a file
End Subroutine
:
Subroutine AmendRecord
‘Code to locate and amend an existing record
End Subroutine
:
Subroutine DeleteRecord
‘Code to delete an existing record
End Subroutine
Breaking up a program into manageable blocks like this has many benefits:
● They can be called at any time using the subroutine’s unique name.
● They allow you to gain an overview about how the program is put 23
together.
● You can use a top-down approach to develop the whole project.
● The program is easier to test and debug because each subroutine is self-

contained.
● Very large projects can be developed by more than one programmer.

Visual Basic forces you to work with subroutines. In Visual Basic as soon
as you try to write code that is connected to a control, Visual Basic creates
a subroutine for you. Object-oriented programming takes this concept
 one stage further by putting all the code and the relevant data in the same
KEYWORD module and the modules are put together to form the overall program. In
Module: a number of subroutines this context a module is one part of a program that may contain several
that form part of a program. subroutines. See Chapter 6 for more details.

● Functions
Functions are similar to subroutines but return a value. For example, most
KEYWORD
modern pocket calculators have a large range of functions. The most basic
Function: a subroutine that are probably the square and square root keys. The idea is that you enter
returns a value.
a number, press the function key you want and the calculator gives you a
result based on that number.
A function in a computer program performs much the same task as the
buttons on a calculator. The user supplies the function with data and the
function returns a value. For example you could create a function that
calculates the volume of a cylinder – you supply the height and radius and
the function returns the volume.
This process is not limited to numeric data; for example, you could create
a function to count the number of times the letter ‘h’ occurs in a given
block of text, or to check to see if a file has read/write or read-only access
restrictions in place.
There are two benefits of using functions in a program:
● Some processes are very complex and involve many lines of code, but in the

end they produce a single result. Including all those lines of complex code
4 Subroutines, local and global variables

Figure 4.1 Function keys on a calculator in the middle of your program will probably make it harder to understand,
so instead you could put the code in a function and put the function itself
somewhere else in the program, away from the main body of the program.
This also means that if you want to alter the function it is easier to find. It
also makes the main body of the code easier to work through.
● If you have to carry out the same process in lots of different places in

the program, then instead of having to rewrite the same code over and
over again, you would create the code once as a function and call it from
KEYWORD the various places through the program. This has the benefit of keeping
Functional programming: programs smaller, and if you need to alter the way the function works,
a programming paradigm you only have to alter one version of it.
that uses functions to create
programs. Functional programming is a method of programming that only uses
functions. There is more on this in Chapters 46 and 47.

● Parameters and arguments

24 In order for a subroutine or function to operate efficiently you need a way to
KEYWORDS control the data that it takes in. This is usually done by using parameters
Parameter: data being passed and arguments. A parameter works like a variable in that it identifies the
into a subroutine. data that you want a subroutine to take in and use. The argument is the
Argument: an item of data being actual value being passed to the subroutine.
passed to a subroutine.
The way that this is implemented varies depending on the programming
Block interface: code that language being used. As the subroutine being called is external to the
describes the data being passed current subroutine, there needs to be a mechanism for ensuring that the
from one subroutine to another.
program knows how to handle the subroutine that has been called. It does
this using a block interface, which is essentially a block of code that
specifies the type and characteristics of the data being passed.
● Local and global variables

LOCAL AND GLOBAL VARIABLES

As we have seen, it is highly likely that your program will be split up into
lots of subroutines and functions. If you do this then you have to decide on
the scope of any variables created. This means you have to construct your
program in a way that either:
● limits the existence of the variable to the subroutine or function in which

it was declared – a local variable, or

● allows the variable to be used anywhere in the program – a global variable.

The value of a variable is constantly changing throughout the program and

as you have seen, values may be passed around between subroutines. If
the subroutine changes the value stored in the variable, this may be passed
back to the original subroutine or on to another subroutine. An important
aspect of programming is keeping track of the state of variables and one
of the main causes of program errors is when the value of a variable is
changed within one subroutine, that then has an impact on another
subroutine. This is known as a side effect.
It is good practice to use local variables wherever possible and using them
has a number of advantages:
● You cannot inadvertently change the value being stored somewhere else

in the program.
● You could use the same variable name in different sections, and each

could be treated as a separate variable.

● You free up memory as each time a local variable is finished with, it is

removed from memory.

You should only use a global variable where it needs to be available
throughout the whole program. For example, you might store the password
to a program as a global variable if you wanted to make a password
accessible to different sections of your code.
When programming, different syntax is required to indicate whether the
variable is local or global. For example in Visual Basic:
● Local variables are declared using the Dim statement:

Dim Age As Integer declares a local variable called Age.

● Global variables are described as public:

Public Password As Text declares a global variable called

Password.
In Python all variables are assumed to be local when they are defined. If
you want a variable to be global you must tell Python to make it global by
using the global keyword, which actually declares functions not local
variables.
● global Password creates a global variable called Password
25
● Password = "password" creates a local variable called Password.

In some programming languages if you declare a variable in your code and

it is not inside a subroutine or function, then it is assumed to be global.
Therefore you need to be careful when declaring variables. The following
extract of code shows how you might set Password as a global variable and
then other variables as local in Visual Basic:
 Public Password As String
Private Sub CalculateMathsGrade
Dim Score As Integer
Dim Grade As String
If Score > 50 then
Grade = "Pass"
Else
Grade = "Fail"
End Sub
Private Sub CalculateEnglishGrade
Dim Score As Integer
Dim Grade As String
If Score > 50 then
Grade = "Pass"
Else
Grade = "Fail"
End sub
There are two subroutines: CalculateMathsGrade and
CalculateEnglishGrade. The variable Password is a global variable
and therefore is accessible from either of the two subroutines. The Score
and Grade variables are local to each subroutine. This means that although
4 Subroutines, local and global variables

they have the same names in both, they are actually different variables
containing different values, a bit like having two people called John Smith
with different characteristics.

● Exception handling A level only

There are many situations where a subroutine has to stop because of an
exceptional circumstance that causes an error. This is not necessarily an
unexpected event, just one that causes the current subroutine to stop. An
example would be a division by 0 error, where the subroutine is expecting a
number, but instead gets an undefined value caused by the division. When
this happens, the subroutine has been ‘thrown’ an error, which it must deal
with. If it is unable to ‘catch’ the error, the program could produce a fatal
error, causing the program to stop running completely.
In the same way that subroutines are triggered by events, there need to
26 be blocks of code that handle errors that are triggered whenever the error
occurs. These are often referred to as catch blocks, which are specific blocks
of code that are triggered in response to specific errors.
The normal procedure when this happens is:
● an error is thrown so the current subroutine stops or is paused
● the current state of the subroutine is saved
KEYWORD
● the exception handling code (or catch block) is executed to take care of
Exception handling: the process
of dealing with events that cause the error
● the normal subroutine can then be run again, picking up from where it
the current subroutine to stop.
was saved.
 Fatal program error

EXCEPTION HANDLING
Exception
unexpected
Normal program flow Exception

Exception
expected

Exception handler
Figure 4.2 The exception handling process
Practice questions can be found at the end of the section on pages
46 and 47.

TASKS
1 Define the following terms and explain the difference between the two:
a) subroutine b) function.
2 Give examples of in-built functions that you might find in a
programming language.
KEY POINTS
• Subroutines or procedures 3 Why is it good practice to construct programs using subroutines?
are a way of breaking up code 4 What is the advantage of using functions?
into manageable blocks of 5 Define the following terms and explain the difference between the two:
code, each of which performs a) algorithm b) code.
a specific task.
6 What is a module and how does it differ from a subroutine?
• Subroutines are likely to have
other related subroutines. 7 Explain how parameters and arguments are used to pass values and
variables into subroutines.
• Breaking a program up into
subroutines is beneficial 8 What is a block interface?
for several reasons, mainly 9 Why is it good practice to use local variables whenever possible?
related to being easier to
10 Give an example of where you might use a global variable.
manage and maintain the
program. 11 Explain how an exception handler works.
• A function is a type of
subroutine that returns a set
value, for example, the square
root function. STUDY / RESEARCH TASKS
• Parameters and arguments 1 Write a program that calculates the square and square root of any
are the data that are passed given number. Try to include the following features:
into the function on which it a) a subroutine
performs its computations. b) a function 27
• Local variables can only be c) a subroutine or function call
used within the subroutine in d) a parameter or argument
which they were created.
e) a local variable
• Global variables can be used f) a global variable.
anywhere in a program.
2 Extend your program to include other common mathematical functions.
• Exception handling is the way
in which the program deals 3 Write a program that takes in a set of numbers and then calculates the
with events that may cause it mean, median and range using either in-built or user-defined functions.
to stop. 4 Find examples of typical events that would require exception handling code.
 5 Structured
programming

SPECIFICATION COVERAGE
[Link] Structured programming
[Link] Design

LEARNING OBJECTIVES
In this chapter you will learn how to:
• use hierarchy/structure charts to plan the design for a program
• use flowcharts to describe a system
• write pseudo-code and test it by dry running
• use sensible naming conventions for program components
• write well-structured commented code.

INTRODUCTION
As we have seen in the first four chapters, there are lots of aspects to
consider when creating a program including:

• working out the main processes

• identifying the data that is needed and how it will be stored
• working through the calculations that will be carried out on the data
• deciding what type of statements are needed
• organising the code into subroutines to create a working program.
Time and effort spent on designing a computer program are always
KEYWORDS well worth it, and good program design should result in a more efficient
28 and error-free result. It will also make creating the code easier if you
Procedural programming
plan ahead.
languages: languages where the
programmer specifies the steps
This chapter looks specifically at the techniques that can be applied
that must be carried out in order
to procedural or imperative programming languages. These
to achieve a result.
languages use sequences of instructions in the form of algorithms
Imperative programming and subroutines as described in the previous chapter. A-level students
languages: languages based on need to be aware of other paradigms including object-oriented and
giving the computer commands functional programming languages. These are covered in Chapter 6
or procedures to follow. and Chapters 46 and 47 respectively.
 ● Hierarchy or structure charts

FLOWCHARTS
Hierarchy or structure charts use a top-down approach to explain
KEYWORDS how a program is put together. Starting from the program name, the
Hierarchy chart: a diagram that programmer breaks the problem down into a series of steps.
shows the design of a system
from the top down. Each step is then broken down into finer steps so that each successive
Structure chart: similar to a layer of steps shows the subroutines that make up the program in more
hierarchy chart with the addition detail.
of showing how data are passed The overall hierarchy of a program might look like this:
around the system.
● programs are made up of modules
Top-down approach: when ● modules are made up of subroutines and functions
designing systems it means
● subroutines and functions are made up of algorithms
that you start at the top of the
● algorithms are made up of lines of code
process and work your way
● lines of code are made of up statements (instructions) and data.
down into smaller and smaller
sub-processes. We have come across all of these before apart from the module. In
larger programs a module is a self-contained part of the program that
can be worked on in isolation from all the other modules. This enables
different programmers to work independently on different parts of large
programs before they are put together at the end to create the program
as a whole.
The text in a hierarchy chart at each level consists of only a few words
– if you want more detail about what the process involves you need to
move further down the diagram. The component parts for each section
are organised from left to right to show how the system will work.
Figure 5.1 shows just part of a structure diagram of a program showing the
program at the top, the modules beneath that and so on.

Program

Initialise Input Process Output

Capture
Enter data Validate
form

Figure 5.1 A simple hierarchy or structure chart

● Flowcharts
29

A flowchart uses a set of recognised symbols to show how the components

KEYWORD of a system or a process work together. Some of the more common symbols
Flowchart: a diagram using are shown in Figure 5.2.
standard symbols that describes
a process or system.
 Input/
Start/stop Process
output

Printed
Decision output Disk

Tape
Connector

Figure 5.2 Flowchart symbols

A system flowchart shows the tasks to be completed, the files that will
KEYWORD
be used and the hardware that will be needed but only as an overview.
System flowchart: a diagram It is normally possible to create just one flowchart that shows the whole
that shows individual processes
system, but this is not always a good idea as modern programs can be
within a system.
very large and cramming every process on to one flowchart might make
it too complex to be of any real use. It might be more advantageous to
create a separate systems flowchart for each section of the project.
The systems flowchart in Figure 5.3 shows the first few processes that are
used when a person starts to use an ATM (Automated Teller Machine) at
a bank.

Put card
in
machine
5 Structured programming

Read details
from chip

Enter
PIN

Is N Display
PIN correct Screen
error message
?

Y
30
Display
Screen
menu

Figure 5.3 An example of system flowchart for an ATM

 ● Pseudo-code

NAMING CONVENTIONS
So far we have looked at diagrammatic ways of organising a program, but
the code that a programmer creates does not use diagrams, it uses lines
KEYWORD of code.
Pseudo-code: a method of Pseudo-code is a way of writing code without having to worry too
writing code that does not much about using the correct syntax or constructs. It consists of a series
require knowledge of a particular of commands that show the purpose of the program without getting
programming language. bogged down with the intricacies of the chosen high-level language. The
programmer will need to convert the pseudo-code into high-level code at a
later date.
Pseudo-code is not a true programming language though it may well use
some of the constructs and language of a high-level language. There is only
one rule that needs to be adhered to if pseudo-code is to be of any use and
that is that the language used needs to be consistent. Using the command
‘Save to File’ in one place then ‘Write to File’ in another will only make the
job of converting to a true high-level language harder.
Pseudo-code can be used at many levels. The line:
Sort NameFile by surname
does exactly the same as these lines:
Repeat
Compare adjacent values, swap if necessary
Until No more swaps are needed
It will be up to the programmer to decide how far down they need to break
their pseudo-code before they can start to actually write the code.
Pseudo-code is very useful in that it allows a programmer to sort out
the overall structure of the program as it will eventually appear. The
fact that it can be used at many levels means the programmer does
not have to work out all the fine detail from the start. The process of
turning pseudo-code into programming code is covered in more detail
in Chapter 17.

● Naming conventions
Adding variables to a program as you go along is a recipe for disaster
KEYWORD and it shows a serious lack of planning. Before you start your actual
Naming conventions: the code you should draw up a list of all the variables you intend to use,
process of giving meaningful including details of the data types and whether they are going to be local
names to subroutines, functions, or global variables. 31
variables and other user-defined
features in a program.
 These are some variables that are being declared so they can be used in a
Visual Basic program:
Dim LoadFileName As String
Dim Counter As Integer
Dim AverageScore as Single
Dim RejectFlag As Boolean
Giving the variables, constants, modules, functions and subroutines in a
program meaningful names is good practice. It makes a lot more sense to
call a variable that stores the number of pupils in a group GroupSize than
to call it Size or C3.
In the same way that programmers should sort out the variables, they
should also draw up a list of the functions and subroutines they intend to
use along with details of what each will do, what it will be called, and what
parameters it will need to have assigned to it.

● Code layout and comments

The final step to good program construction is to use the features of the
programming language to make the code itself as programmer-friendly as
possible. This might include adding suitable comments, especially to more
complex or unusual sections of code, and using gaps and indents to show the
overall structure of a program. Indenting loops can help to identify where a
loop begins and ends. It also helps when you are trying to debug a program.
The following two sets of code do the same thing – they place the first 12
values from the two times table in an array.
This first example provides no support for the programmer at all.
For X = 1 To 12
5 Structured programming

W(X) = 2 * X
Next
This second example has made use of a number of features:
‘routine to place multiples of 2 in array TwoTimes()
For Count = 1 To 12
‘counter counts from 1-12
TwoTimes(Count) = 2 * Count
‘result in array TwoTimes
32
Next Count
‘end loop
The helpful features are:
● comments to show the purpose of the algorithm itself
● comments to show the purpose of each line
● sensible variable names such as Count and TwoTimes
● the contents of the loop have been indented.
 ● Dry runs and trace tables

DRY RUNS AND TRACE TABLES

No matter how careful a programmer is, even the simplest programs are likely
KEYWORDS to contain bugs. These come in a number of guises and some are trapped
Dry run: the process of stepping when the program is compiled, and others are trapped by the operating
through each line of code to system. However some bugs can remain elusive and the programmer might
see what will happen before the have to resort to dry running the appropriate section of code.
program is run.
Dry running is the process of following code through on paper. The variables
Trace table: a method of
recording the result of each
that are used are written down in a trace table. Note that dry running can
step that takes place when dry be done on pseudo-code or actual programming code. It is useful to dry
running code. run pseudo-code as any errors in the overall design of the algorithm can be
identified before too much time has been spent programming it.
This is a simple example of a dry run:
For Counter = 1 To 3
If StoreName(Counter) > StoreName(Counter + 1)_
Then
TempName StoreName(Counter)
StoreName(Counter) StoreName(Counter + 1)
StoreName(Counter + 1) TempName
End If
Next Counter
The array called StoreName has four elements. The initial values for
StoreName and the other variables are shown in the trace table below.
Counter TempName StoreName
1 2 3 4
0 <empty> Kevin Jane Beth Linda

The program is now dry run.

Counter is set to 1 and the contents of StoreName(1) are compared
with the contents of StoreName(2). Because “Kevin” is greater than
“Jane” (alphabetically speaking) TempName takes the value “Kevin”,
StoreName(1) takes the value “Jane” and finally StoreName(2) takes
the value held in TempName – “Kevin”.
Counter TempName StoreName
1 2 3 4
Kevin Jane Beth Linda
1 Kevin Jane Kevin

33
Counter now increments to 2 and StoreName(2) is compared to
StoreName(3). “Kevin” is greater than “Beth” so TempName becomes
“Kevin”. Even though TempName already contains “Kevin” it is important
to realise that this is overwritten by the same name.
Counter TempName StoreName
1 2 3 4
Kevin Jane Beth Linda
1 Kevin Jane Kevin
2 Kevin Beth Kevin
 Counter now increases to 3, and “Kevin” is compared to “Linda”. “Kevin”
is less than “Linda” so the program jumps to the End If statement.
Counter TempName StoreName
1 2 3 4
Kevin Jane Beth Linda
1 Kevin Jane Kevin
2 Kevin Beth Kevin
3

Counter has now reached the end value of the loop so the program moves
on to whatever comes next.
You have probably realised by now that this algorithm is part of a simple
sort routine. Whilst a program is being developed a programmer might
also use techniques such as single stepping, where the program is executed
one line a time. The programmer can see the values of the variables
being used and may choose to insert breakpoints. A breakpoint stops the
execution of a program either so the programmer can check the variables
at that point or possibly just to show that a program has executed a
particular section of code.
Practice questions can be found at the end of the section on
pages 46 and 47.

KEY POINTS
• Hierarchy or structure charts TASKS
use a top-down approach to 1 Draw a systems flowchart that shows how the computer system at a
explain how a program is put supermarket handles the sale of goods at the POS (point of sale terminal).
together.
2 The customers at a supermarket have the option of paying for their
• A flowchart uses a set of
goods by credit or debit card. Draw a systems flowchart to show how
recognised symbols to show
this process works.
how the components of a
5 Structured programming

system or a process work 3 A programmer might choose to use both a flowchart and pseudo-code
together. when developing a program. Describe the benefits and drawbacks of
using each of these systems.
• Pseudo-code is a way of writing
code without having to worry 4 High-level languages support ‘user-defined variable names’. Explain
too much about using the what is meant by this term.
correct syntax or constructs. 5 What steps can a programmer take to make the code they write easier
• All the variables you intend for another programmer to follow?
to use including details of the
data types and whether they
are going to be local or global
variables should be identified STUDY / RESEARCH TASKS
at the start.
1 Why is it considered bad practice to use the GoTo statement when
34 • Good program construction programming?
is to use the features of the
program to make the code 2 An alternative programming paradigm to procedural languages
itself as programmer-friendly is logic programming, for example Prolog. In what way does this
as possible. paradigm differ and what are the implications for the way in which
programs might be designed?
• Dry running is the process
of following code through on 3 ‘All programs can be structured using only decisions, sequences and
paper. The variables that are loops.’ Explain whether you think this is true.
used are written down in a 4 In what way do Pascal, Algol and some other programming languages
trace table. enforce structured design?
6 Object-oriented
programming concepts
A level only
SPECIFICATION COVERAGE
[Link] Programming paradigms
[Link] Object-oriented programming

LEARNING OBJECTIVES
In this chapter you will learn:
• the key principles and methods of object-oriented programming (OOP)
including encapsulation, inheritance, instantiation, polymorphism,
abstraction and overriding
• that OOP programs are made up of classes and objects
• that classes are a blueprint containing properties and methods
• that objects are instances of a class containing the same properties
and methods of the class
• how to create class diagrams.

INTRODUCTION
In Chapter 5 we looked at structure charts as a method of planning
and organising programs. This is a top-down approach that breaks
programs into modules, which in turn get broken down into subroutines
and functions. Object-oriented programming can be thought of as an
extension to this structured approach as it is entirely modular.

The key difference between procedural and object-oriented programming

is that in procedural programming, the lines of code and the data the
code operates on are stored separately. An object-oriented program
puts all the data and the processes that can be carried out on that data
together in one place called an object and allows restrictions to be placed
on how the data can be manipulated by the code. 35

The examples in this chapter are given in Python, but all of the languages
offered by AQA for the Paper 1 exam also support object-oriented
programming.

Object-oriented programming can be described as being organised in a

way that reflects the real world. For example, in real-life you may have an
object, such as a bank. Inside that object there are various other objects
such as customers and financial transactions. Inside each of those objects
there are a number of data items and behaviours. For example, there are
 data about customers. These data are handled in a particular way and
therefore have to be processed accordingly. For example, one process
might be to add new customer data. Another process might be that money
withdrawn needs to be deducted from the balance.
In object-oriented programming, a banking application would be created
to mirror these real-life relationships. So there might be one object for
customers and another for transactions. The customer object will then
contain customer data and all the processes needed for that data.
There are a number of advantages to this approach:
● Programs are written in modules, which means that it is easy to amend

programs as only the effected module needs editing.

● It is also easier to add new functionality to a program by adding a new
KEYWORD module.
Modular design:a method of ● Most programs are written by teams of programmers so the modular
system design that breaks a design approach allows groups of programmers to work independently
whole system down into smaller on self-contained modules.
units, or modules. ● Objects can inherit attributes and behaviours making code reusable

throughout the program.

● Changes carried out to data are made within an object rather than in

the program. This makes it less likely that changes made to code will
inadvertently affect the results of another routine, which is a common
cause of bugs in software programs.
● Libraries can be created enabling code to be reused easily.

●
6 Object-oriented programming concepts

Encapsulation
The concept of keeping the data and the code within the same object is called
KEYWORDS encapsulation. The code is known as methods, which are the subroutines
Encapsulation: the concept of contained within an object that are designed to perform particular tasks on
putting properties, methods and the data within the object. This is the main concept behind object-oriented
data in one object. languages meaning that the objects are self-contained. The implication of this
Method: the code or routines is that there are far fewer side-effects than with procedural languages. A side-
contained within a class. effect is where a subroutine changes the value of a variable which then has
implications for other parts of the program.
In theory this cannot happen in object-oriented programming as the data
can only be directly manipulated by the methods contained within the
object. This concept is sometimes called information hiding, which means
that the data are directly available in the object that actually needs to use it.
Code outside of the class can only access data through the defined methods.

Customer Account
36
Name Account number
Address Properties Balance
Date of birth

Add new customer Check balance

Edit customer Methods Add interest
Delete customer
KEYWORD
Properties: the defining Figure 6.1 Classes containing properties and methods
features of an object or class in
terms of its data. Figure 6.1 shows two classes, Customer and Account, both containing
their own properties and methods.
 The two main building blocks of an object-oriented program are classes
KEYWORDS and objects:

ENCAPSULATION
Class: defines the properties ● A class is a blueprint or master copy that defines a related group
and methods of a group of of things. It contains properties, which describe what the data are,
similar objects. and methods, which describe the way in which the data can behave.
Object: a specific instance of However, it does not store any data. Classes can be created based on
a class. other classes.
● Objects are created from a class. Every object is defined as an instance of
a class so will have the same properties and methods from the class from
which it is built. It will also contain the data on which the methods will
be run.
In the banking example:
● A class might be called Account which defines the properties and
methods of a bank account.
● All accounts have similar properties such as an Account Number and

CurrentBalance.
● They also have the same methods – they can GetCurrentBalance,

AddInterest and so on.

● Each individual type of account would be a subclass of the Account

class and they would have all the properties and methods of the
class Account in addition to properties and methods of their own.
Subclasses are explained later in the chapter.
● For example, two subclasses based on the class Account may be

Current and Mortgage. They both share the properties and methods
from the Account class.
● Current Account will have its own specific properties, such as

Overdraft and PaymentMethods, which are only a feature of

current accounts. Similarly Mortgage will have its own specific
properties, such as EndDate, which are unique to it.
● Objects are created from the class (or subclass) and represent a particular

instance of that class. For example, an object created from the Current
class would be one person’s current account and will contain data about
that specific account.
● Any number of objects can be created from a class.

When designing object-oriented programs, you can see how important

it is to think carefully about the properties and methods of each object
and how these might be organised into classes. Classes are fundamental
to the design of object-oriented programs. Therefore they are stored
where they can be reused either in the future, or by programmers
working on other modules. The definitions of all classes are stored in a
class library.
37
The code below shows a class called Account being created in Python.
This is the base class:
class Account():
def init (self, accountNumber, openingDate,
currentBalance, interestRate):
[Link] = accountNumber
[Link] = openingDate
[Link] = currentBalance
 [Link] = interestRate
def getAccountNumber(self):
return [Link]
def getCurrentBalance(self):
return [Link]
def addInterest(self):
interest = [Link] * self.
interestRate
[Link] += interest
def setInterestRate(self, interestRate):
[Link] = interestRate

● Inheritance
Inheritance in object-oriented languages acts in a similar way to the
KEYWORD biological definition of inheritance. You start out with a set of characteristics
Inheritance: the concept that and add to what already exists. You can add or change features and abilities
properties and methods in one but cannot delete them directly.
class can be shared with a
subclass. Taking the bank account example mentioned earlier you might start with
a base class called Account. This will have properties and methods. For
example the properties may be:
6 Object-oriented programming concepts

AccountNumber: String
DateOpened: Date
CurrentBalance: Currency
InterestRate: Real
When programmed, the properties become variables with an appropriate
data type assigned.
The methods may include:
AddInterest
GetCurrentBalance
GetInterestRate
When programmed the methods become the subroutines (procedures or
functions) required. In this case a procedure or function would be defined
to calculate the amount of interest to add to the account.
38
The properties and methods defined in the base class are common to all
types of account. For example, whether the account was a current account
or mortgage account it would still have the same properties and methods.
In addition, the other account types would have additional properties and
methods so these can now be set up as subclasses along with any properties
and methods that are unique to the subclass.
For example, the current account might have a new property Overdraft,
which indicates whether the customer has an overdraft set up on their
account. This is unique to current accounts so would not appear as a
 property on the mortgage account. A method to set the overdraft called
setOverdraft could be defined in the subclass.

INHERITANCE
The mortgage account might have a property called EndDate, which is the
date that the mortgage is paid off. This is not a property that you would
use in a current account so needs to be set up in the Mortgage subclass.
A method may be set up called GetEndDate to identify the date that the
last payment needs to be made.
Account This relationship between the classes and subclasses can be shown as an
inheritance diagram as in Figure 6.2. Note that the direction of arrows
shows the path of inheritance.
Current Mortgage
Inheritance produces a hierarchical structure. In this scenario, Account
Figure 6.2 An inheritance diagram for could be described as a base class, super class or parent class, as it is the
Account
main class from which other classes Current and Mortgage are created.
Classes that inherit from others are called subclasses, derived classes or
child classes. This example has been simplified to include just two types
of account, but the same principle can now be used to define further
subclasses. For example, subclasses could be defined for savings accounts,
trust fund accounts and so on.
class Current(Account):
def init (self, accountNumber, openingDate,
currentBalance, interestRate, paymentType,
overdraft):
Account. init (self, accountNumber,
openingDate, currentBalance, interestRate)
[Link] = paymentType
[Link] = overdraft
def setPaymentType(self, paymentType):
[Link] = paymentType
def setOverdraft(self, overdraft):
[Link] = overdraft
def getOverdraft(self):
return [Link]
class Mortgage(Account):
def init (self, accountNumber, openingDate,
currentBalance, interestRate, endDate):
Account. init (self, accountNumber, 39
openingDate, currentBalance, interestRate)
[Link] = endDate
def getEndDate(self):
return [Link]
def setEndDate(self, endDate):
[Link] = endDate
 ● Class diagrams for inheritance
Class diagrams are a standard method for representing classes, their
KEYWORD
properties and methods and the relationship between the classes. There are
Class diagrams: a way of different ways of representing the relationships between the classes. This
representing the relationship
section deals with inheritance:
between classes.
● They are hierarchical in structure with the base class at the top and the

subclasses shown beneath.

● A subclass inherits the properties and methods of the base class.
● They use arrows to shows the direction of inheritance.
● Each class is represented with a box made up of three sections to include

the class name, properties and methods.

Name

Properties
Base class or Superclass

Methods

Name Name
6 Object-oriented programming concepts

Properties Properties
Subclasses

Methods Methods

Figure 6.3 A basic class diagram

A class diagram for the account example might look like this:

Account
– AccountNumber: String
– OpeningDate: Date
Base class or Superclass
– CurrentBalance: Currency
– InterestRate: Real
+ getAccountNumber
+ getCurrentBalance
+ addInterest
+ setInterestRate

40

Current Mortgage

– PaymentType: String – EndDate: Date

– Overdraft: Boolean Subclasses
Or Derived Classes

+ setPaymentType + getEndDate
+ setOverdraft + setEndDate
+ getOverdraft

Figure 6.4 A class diagram for Account

 The class diagram:

POLYMORPHISM AND OVERRIDING

● Uses a + or – to indicate the visibility of the properties and methods to
other classes. + means that the properties and methods are public to all
classes. – means that the properties and methods are private and can
only be used in that class.
● Uses a # to indicate that the properties and methods are protected so they
can be used in that class and any of its subclasses.
● Uses arrows with the arrow pointing to the base class to show where the
subclass is inheriting its properties and methods from.
● Defines the data types to be used for each variable.

● Instantiation
Instantiation is the process of creating an object from a class. In other
KEYWORD
words, you are creating an actual instance of an object using the properties
Instantiation: the process of
and methods described in the class. With the Account example, an object
creating an object from a class.
could be created from the class Account, which is a specific customer’s
current account. Many different objects can be created from the same class
so the programmer will need to go through the process of instantiation for
every object needed in the program.
When programming, there is a subroutine called a constructor, which is
called when an object is instantiated from a class to initialise the object.
new_account = Account(41344987, [Link](), 374.34,
0.032)

● Polymorphism and overriding

The literal meaning of polymorphism is to take on many shapes. In
KEYWORD object-oriented programming it describes a situation where a method
Polymorphism: the ability of inherited from a base class can be redefined and used in different ways
different types of data to be depending on the data in the subclass that inherited it.
manipulated with the same
method. It is related to the hierarchy of classes and the way in which classes inherit
properties from other classes. For example, there may be a common
method that you want to carry out as part of your program. As this method
is critical to the program, it could be defined in a base class, which is then
inherited by other classes. However, the data contained in these new classes
is perhaps of a different type. Rather than have to define a new method,
polymorphism enables the original method to be redefined so that it will
work with the new data.
For example, we could define a method that worked out the interest
payment on an account. This method would be stored in the base class 41
Account. It would then be inherited by the Current and Mortgage
subclasses. The data needed to calculate interest might be different, for
example, a current account may have a higher rate of interest, or use a
different time period over which to calculate the payment. Each subclass
would define a different method to calculate the interest, but these would
have the same name as the calculate interest method in the base class.
 When the subclass implements the method it is called overriding because
KEYWORD it overrides (or replaces) the method in the base class. In this example, the
Overriding: where a method
method for calculating interest is overridden for the Current object:
described in the subclass takes # new method added to the Current class overriding
precedence over a method with the addInterest method in the Account class
the same name in the base class.
def addInterest(self):
# if the account has an overdraft, interest is
charged on the debt at 5%
if [Link]:
charges = [Link] * 0.05
[Link] += charges
# otherwise interest is applied in the same way
as the superclass (Account)
else:
[Link](self)

● Abstract, virtual and static methods

Object-oriented languages handle objects in three different ways. You
can think of the code inside an object as subroutines, which are a series
of instructions that it will carry out on the data. Due to the nature of the
6 Object-oriented programming concepts

relationships between objects and classes, it means that methods in one

object may be used on data contained within another object.
In order to define the behaviour of the methods, they can be set up in three
different ways:
● Static: the method can be used without an object of the class being

instantiated.
● Virtual: the method is defined in the base class but can be overridden

by the method in the subclass where it will be used. This is a feature of

polymorphism.
● Abstract: the actual method is not supplied in the base class, which

means that it must be provided in the subclass. In this case, the object is
being used as an interface between the method and the data.
Which one you use depends on the nature of the methods and the data
contained within the class and at what point you want the method to run.

42
● Aggregation
Aggregation is a method of creating new objects that contain existing
objects, based on the way in which objects are related. Object-oriented
programming is concerned with recreating real-life objects as programming
objects. In real life, objects are related to each other. For example, in a
business you might have an object called Workforce and another called
Job Roles. Under Workforce there may be further objects called
Manager and Employee. All of these objects exist in their own right, but
there is also relationship between them. For example:
 ● Managers and employees make up the workforce.

DESIGN PRINCIPLES
● Job roles can be taken on by managers or employees.
● Job roles define what the managers and employees do as part of the
workforce.

Composition aggregation
Workforce is made up of Manager and Employee. If you deleted
KEYWORD Workforce you would by definition be deleting Manager and
Composition aggregation: Employee. This is an example of composition aggregation, sometimes
creating an object that contains just called composition and it is where one object is composed (or made
other objects, and will cease to up of) two or more existing objects. You could say that Workforce is
exist if the containing object is instantiated (created) when Manager and Employee are combined.
destroyed.
This can be shown as a class diagram as follows. Notice the shape of the
arrow head, which indicates that Manager and Employee cannot exist
unless Workforce does.

Workforce

Manager Employee

Figure 6.5 Class diagram showing composition aggregation

Association aggregation
You could now extend the Workforce object to include a Job Role object.
There is a relationship between Manager, Employee and Job Role in
that the managers and employees all have specific job roles that they carry
out. However, if you deleted Job Role, the Manager and Employee
object would still be retained and still be usable objects as would the
Workforce object. This is due to the nature of the relationship in the
KEYWORD real world in that a job role is not fixed and therefore any manager or
Association aggregation: employee could be given any job role. This is an example of association
creating an object that contains aggregation where an object is made up of one or more objects but is not
other objects, which can entirely dependent on those objects for its own existence.
continue to exist even if the
containing object is destroyed. This can be shown as a class diagram as follows. Notice the shape of the
arrow head, which indicates that Manager and Employee can still exist
even if Job Role does not.

Job Role

Manager Employee

Figure 6.6 Class diagram showing association aggregation 43

● Design principles
There are three key design principles that are recognised as producing the
most elegant solution when programming using an object-oriented language.
● Encapsulate what varies: This is related to the concepts of encapsulation

and information-hiding and the basic concept is that everything that varies
should be put into its own class. This means that properties and methods are
subdivided into as many classes as needed to reflect the real-life scenario.
 For example, with our accounts program we could have an Account
base class followed by Current, and Mortgage subclasses and we
could stop at that. However, further analysis would suggest that you
could create a subclass under Current for different types of current
account such as Standard, Premium, Student and Child as these
types of account may have properties and methods that are unique to
them. You would continue with this process until you were sure that you
had created a class for each unique set of properties and methods.
● Favour composition over inheritance: This principle refers to the way in
which classes and objects are instantiated (created). As we have seen objects
can be created from a base class and inherit its properties and methods. The
alternative is to use aggregation or composition to combine existing objects
to make new ones. This method is less error prone and enables simpler
maintenance. For example, with reference to the Workforce example,
rather than creating a new instance for Workforce we only need to create
Manager and Employee and can then combine the two. Providing
Manager and Employee are created correctly, then there should be
no errors in Workforce. Similarly any changes made to Manager or
Employee will be reflected in Workforce.
● Program to interfaces, not implementation: In object-oriented
programming an interface defines methods to be used, which are then
applied when classes are defined. In this sense an interface is an abstract
type which is implemented when a class is created. When a class is
created that adheres to the methods in the interface, it can be seen as
an implementation of the interface. With our accounts example, being
6 Object-oriented programming concepts

able to calculate interest and check the balance were two methods that
all accounts must have regardless of the exact class they are in so these
would be required by the interface. The way in which these operations
are carried out would be defined within any class that wanted to use the
interface. The interface ensures that they must be defined.
Programs can then be written based on the interfaces rather than each
individual implementation of a class. Using this methodology, if classes need
to be added to or amended, this can be done with reference to the interface,
meaning there will be little or no impact on the other classes in the program.
Practice questions can be found at the end of the section on
pages 46 and 47.

TASKS
1 In what way does object-oriented programming reflect the way things
work in real life?
2 Using a real-life example, define the following terms explaining the
relationship between the three:
44
a) class
b) object
c) inheritance.
3 Using the same real-life example, explain what properties and
methods are.
4 Draw a class diagram for your real-life example.
5 How does encapsulation prevent side effects?
6 What are the two main ways to instantiate an object?
 DESIGN PRINCIPLES
7 Explain the difference between static, abstract and virtual methods.
8 Explain the difference between composition aggregation and
association aggregation.
9 What are polymorphism and overriding?
10 What is an interface in the context of object-oriented programming?
11 Explain the three main design principles for effective design.

STUDY / RESEARCH TASKS

1 For your real-life example above, use an object-oriented programming
language to implement a solution. Include the following features:
• objects created using abstract, virtual and static methods
• inheritance
• aggregation
• polymorphism
• public, private and protected specifiers.

KEY POINTS
• Object-oriented programming can be described as being organised in
a way that reflects the real-world.
• An object-oriented program puts all the data and the processes
(methods) that can be carried out on that data in one place called an
object.
• The concept of keeping the data and the code within the same object
is called encapsulation.
• Class diagrams are a standard method for representing classes, their
properties and methods and the relationship between the classes.
• Inheritance in object-oriented languages acts in a similar way to the
biological definition of inheritance.
• Instantiation is the process of creating a real instance of a class,
which is an object.
• Polymorphism describes a situation where a method inherited from a
base class can be used in different ways depending on the data in the
subclass that inherited it.
• When the subclass implements the method it is called overriding
because it overrides (or replaces) the method in the subclass.
• Aggregation is a method of creating objects that contain other sorts of 45
object.
 Section One: Practice questions
1 The following code is part of a stock control system.
Dim Name As String
Dim Price As Real
Const VAT = 0.2
Type RecordDetails
RecordType As String * 14
RecordCurrent As Integer
RecordRestock As Integer
End Type
a) Identify where each of the following have been used, and explain why the type of the variable chosen
is appropriate:
i) a variable that is used to store a whole number
ii) a variable that is used to store a decimal number.
b) Why has a constant been used to store VAT?
c) Some computer languages support ‘user-defined types’. Explain this term and give an example of a
user-defined variable in the code.
2 A program has been written to analyse the results of a survey. For each of the following, name a suitable
data type and give a reason for your choice:
a) the number of pets owned by a household
b) a telephone number such as 0122453322
c) whether a household’s accommodation has central heating or not
d) the average number of children within a household.
Section One: Practice Questions

3 It is considered poor design to define an Age field when storing personal details. Describe a better way
of storing this data.
4 What values can a Boolean expression take?
5 The following section of pseudo-code is used to add and remove data in a queue.
‘routine to add to a circular queue
‘increment Rear pointer
Rear ← Rear + 1
‘Check to see if end of array has been reached
‘If so go back to the start of the array
If Rear = 9 Then Rear ← 0
‘add data
Put DataItem at position Rear in array
46
‘routine to remove data from a circular queue
‘remove data
Take DataItem from position Front in array
‘move Front on
Front ← Front + 1
‘Check to see if the end of the array has been reached
‘If so go back to the start of the array
If Front = 9 Then Front ← 0
 a) State a line of code that has a comment in it.

Section One: Practice questions

b) State a line of code that is an assignment statement.
c) State a conditional statement that has been used.
d) An array contains the characters E, C and F, with the front pointer on E (at index 0 in the array) and the
rear pointer on F (at index 2 in the array). Dry run the code above, showing what would happen if the
characters A, D and G were added to the queue.
e) Why is it good practice to create programs in modules?
6 Write a program to implement the pseudo-code in question 5.
7 Explain what techniques programmers can use to assist with the
design of a piece of software and how they can make their program
code easy to follow.
8 Look at the following section of code and then answer the questions.
For Loop1 = 1 To NameCount - 1
For Loop2 = 1 To NameCount - 1
If NameStore(Loop2) > NameStore(Loop2 + 1) Then
TempStore = NameStore(Loop2)
NameStore(Loop2) = NameStore(Loop2 + 1)
NameStore(Loop2 + 1) = TempStore
End If
Next
Next
a) Name two different data types that are being used.
b) What is the purpose of the first line of code?
c) What is the purpose of the second line of code?
d) What is this algorithm doing?
9 Explain the difference between local and global variables.
10 An object-orientated programming language will be used to create a system related to animals.
a) Suggest suitable properties and methods for a base class.
b) Suggest two further subclasses that could be built from the base class.
c) Explain the difference between an object and a class.
d) Draw a class diagram to show your answers to parts a and b.
e) Give one example of inheritance in this example.
f) Explain how an object can be instantiated.
g) Give one example of where you may need to use overriding.

47
Section Two:
Fundamentals of data
structures
 7 Data structures and
abstract data types
SPECIFICATION COVERAGE
[Link] Data structures
[Link] Single- and multi-dimensional arrays (or equivalent)
[Link] Fields, records and files
[Link] Abstract data types/data structures

LEARNING OBJECTIVES
In this chapter you will learn:
• what data structures and abstract data types are
• what an array is and how to use one to store and access data
7 Data structures and abstract data types

• what a file is and how it is used to store data

• the difference between text files and binary files
• how to read and write data to and from csv and binary files.
A-level students will learn:
• what static and dynamic data structures are
• the different characteristics of static and dynamic data structures.

INTRODUCTION
There is a difference between what is required for AS and A level here
KEYWORDS and this chapter has been split accordingly. AS-level students need only
Data structure: a common study to the end of the section on binary files. A-level students need to be
format for storing large volumes aware of a much wider range of data structures and abstract data types
of related data, which is an and also understand how to implement them in a programming language:
implementation of an abstract
• Chapters 7–11 explain the data structures required for A level,
data type.
50
including coding on how to implement them.
Abstract data type: a conceptual
• Chapters 12–16 cover some common algorithms required for A level,
model of how data can be stored
including how to implement the abstract data types described in
and the operations that can be
Chapters 7–11.
carried out on the data.
In Chapter 1 we looked at the different ways individual items of data
might be stored. For example, we looked at storing a person’s age as
an integer and their name as a string. These are known as data types.
In this chapter we will look at the ways of storing larger volumes of
data in formats that make it easy for programs and users to access and
analyse. These are called data structures and abstract data types.
 ● Data structure and abstract data type

ARRAYS
A data structure is any method used to store data in an organised and
accessible format. Data structures normally contain data that are related
and the way that the data are organised enables different programs to
KEYWORD manipulate them in different ways. Different data structures tend to lend
File: a collection of related data. themselves to different types of applications. For example, a text file
may be suitable for a database whereas a stack is suitable for handling
exceptions.
An abstract data type is a conceptual model of how the data are stored and
the operations that can be performed upon them. The data structure is an
implementation of this in a particular programming language.

● Arrays
We came across the concept of an array in Chapter 1. An array is a list or
KEYWORD table of data that has a variable name that identifies the list or table. Each
Array: a set of related data item in the table is called an element. An array can have many dimensions
items stored under a single but most arrays are either one-dimensional in which case they form a list or
identifier. Can work on one or can be visualised as a two-dimensional table.
more dimensions.
Lists and arrays are static data structures that are created by the
programmer to store tables of data. In some programming languages
programmers need to define just how big an array is going to be at the start
of their program. This means that the size of the array and the amount of
memory put aside for it does not change.
You might find that you want to store a sequence of data in some way. For
example you might want to store the names of pupils in a class:
Name1 = "Derrick"
Name2 = "Peter"
Name3 = "Jill"
Name4 = "Lynn"
Carrying out any sort of work even on just these four names is going to be
very cumbersome. Imagine how difficult this would be if you wanted to
store 30 names or 3000 names. The best solution to this problem is to use
an array. In the example above, we could call the array StudentName.
Each element of the array can now be accessed using its position. For
example, the third element in the array is Jill (assuming indexing starts at 1
and not 0). This would be shown as: StudentName(3) = "Jill"
Another example could be to set up a one-dimensional array called
51
DaysInMonth. The third element would be set to 31 as that is the number
of days in March. As this table contains just one row of data it could also be
described as a list.

Element in 1 2 3 4 5 6 7 8 9 10 11 12
DaysInMonth

Contents of 31 28 31 30 31 30 31 31 30 31 30 31
that element

Figure 7.1 A one-dimensional array or list

 An array has one or more dimensions – for example you might want to
store the mock exam results of a group of pupils. The array then might be
called Results and it would have two dimensions, one for the pupils and
the other for the subjects and might look something like this:

1 2 3 4 5 6 7
1 54 67 76 65 75 32 19
2 32 45 98 32 53 14 88
3 12 32 54 56 59 95 71
4 32 21 12 43 22 26 16
5 15 47 65 35 99 82 41

Figure 7.2 A two-dimensional array

You will note that the rows/columns are not labelled – it is up to the
programmer to remember which axis refers to the pupil and which to
the subject. In this diagram the 65 might represent the mark obtained by
Hilary in the French exam. If the table were called Results then Hilary’s
French mark would be stored in Results(4, 1) where the 4 identifies
the pupil and the 1 identifies the subject.
It is possible to work with multi-dimensional arrays. If you take the mock
exam paper array further, you might decide to store the exam results for
each exam paper. In this case the value in Results(4, 1, 2) could store
the mark Hilary got in the second paper of the French exam.
In fact you can have many more dimensions than this – a four-dimensional
array might store the marks gained for each question in each paper, so
7 Data structures and abstract data types

Results(4, 1, 2, 12) might store the mark Hilary was given for
question 12 in paper 2 of the French mocks. As you add more and more
dimensions to the array it becomes increasingly difficult to conceptualise.

● Files
You will already be familiar with the concept of a file to store data. There
are hundreds of different file types, all of which have their own structure
depending on the specific use of the file. Some files are very specific in that
they can only be used on certain applications. Many file formats however
are portable, which means they can be used in a wide range of programs.
KEYWORDS Two common portable formats that can be used when programming are
Text file: a file that contains text files and binary files.
human-readable characters.
A text file is one that simply contains lines of text or other human-readable
Binary file: stores data as characters, where each line is usually referred to as a record. There may be
sequences of 0s and 1s.
different items of data stored and these are referred to as fields.
Record: one line of a text file.
52 They may contain a header, which explains the content and structure of
Field: an item of data.
the file and an end of file (EOF) marker so that the programs using the file
know when to stop. Common text file formats include txt used for non-
formatted or plain text and csv (comma separated variables), both of which
are used for transferring data between programs.
All files have an internal structure. For example, a csv file has fields that
are split up using commas. Most text files are delimited like this in some
way so that when the file is being used, the program knows where to look
for each item of data in the file. The following examples show a typical
structure where each row represents a record and the fields are separated
either by tabs or commas:

FILES
A tab-delimited text (txt) file:
John Smith 22 Acacia Avenue LE11 1AA
Mary Jones 1 High Street LE12 5BD
Imran Siddiqi 12 Harrow Road LE13 1GG
Yin Li 24 Royal Road LE1 1AA
A comma separate variable (csv):
John,Smith,22 Acacia Avenue,LE11 1AA
Mary,Jones,1 High Street,LE12 5BD
Imran,Siddiqi,12 Harrow Road,LE13 1GG
Yin,Li,24 Royal Road,LE1 1AA
The two main actions you might want to carry out when working with text
files are:
● to write data from the program into a text file
● to read data into the program from a text file.

The following extract of Visual Basic-based code shows how you would
write data to a text file. In this case, data is being written from a two-
dimensional array called ArrayStore:
FileOpen(1, "[Link]", [Link])
‘ look at each row/record in turn
For RecordCount = 1 to 30
‘ load first field from the next record into
the temporary string
RecordString = ArrayStore(recordcount,1)
‘ concatenate all the other fields
For FieldCount = 2 To 4
Recordstring = recordstring & "," & Arraystore
(Recordcount,fieldcount)
Next
‘ write ‘record’ to file
Print(1, OutputString)
Next 53

FileClose(1)
The following extract of code shows how you would read data from a text
file into a program using Visual Basic as an example:
‘load csv file from folder
FileOpen(1, "C:\Users\[Link]", [Link])
Do
 [Link](1)
[Link](1)
Input(1, DownLoadText)
[Link](RowCount).Cells(0).Value =
DownLoadText & RowCount
RowCount = RowCount + 1
Loop Until EOF(1)
FileClose(1)

● Binary files
A binary file is one that stores data as a series of 0s and 1s. Binary
representation is one of the cornerstones of how computers work and is
covered in detail in Chapter 25. At this stage it is important to understand
that all program code and all of the data that you might use in a program
including text, graphics and sound are all made up of 0s and 1s. These are
usually organised into groups of 8 bits, called bytes.
Binary files contain binary codes and usually contain some header
information that describes what these represent. As you can see from
Figure 7.3, binary files are not easily readable by a human, but can quickly
be interpreted by a program.
7 Data structures and abstract data types

11101111 10111011 10111111 00111100 01101110 01101111 01100100 01100101

00100000 01101001 01100100 00111101 00100010 00110001 00110000 00110111
00110000 00100010 00100000 01110110 01100101 01110010 01110011 01101001
01101111 01101110 00111101 00100010 01100101 01100010 01100011 00110111
01100010 01100011 01100001 00110001 00101101 00110011 01100001 01100110
01100010 00101101 00110100 01100001 01100001 00110001 00101101 00111001
01100001 00110100 01100101 00101101 01100110 01100100 00110000 01100100
00110110 00110011 00110110 00110011 01100011 01100010 01100011 00110111
00100010 00100000 01110000 01100001 01110010 01100101 01101110 01110100
01001001 01000100 00111101 00100010 00101101 00110001 00100010 00100000
01101100 01100101 01110110 01100101 01101100 00111101 00100010 00110001
00100010 00100000 01110111 01110010 01101001 01110100 01100101 01110010
01001001 01000100 00111101 00100010 00110000 00100010 00100000 01100011
01110010 01100101 01100001 01110100 01101111 01110010 01001001 01000100
00111101 00100010 00110000 00100010 00100000 01101110 01101111 01100100
01100101 01010100 01111001 01110000 01100101 00111101 00100010 00110001
00110000 00110101 00110110 00100010 00100000 01110100 01100101 01101101
01110000 01101100 01100001 01110100 01100101 00111101 00100010 00110001
00110000 00110100 00110010 00100010 00100000 01110011 01101111 01110010
01110100 01001111 01110010 01100100 01100101 01110010 00111101 00100010
00110010 00100010 00100000 01100011 01110010 01100101 01100001 01110100
01100101 01000100 01100001 01110100 01100101 00111101 00100010 00110010
00110000 00110000 00110111 00101101 00110000 00110100 00101101 00110010
00110101 01010100 00110001 00111000 00111010 00110010 00111000 00111010
00110010 00110110 00100010 00100000 01110101 01110000 01100100 01100001
01110100 01100101 01000100 01100001 01110100 01100101 00111101 00100010

Figure 7.3 Output from a binary file

For example, the PNG image file is a binary file, can be used in a range
54 of applications and requires less memory than some other image formats.
Many program files (executables) are created as binary files so that they can
be used on other platforms.
The two main actions you might want to carry out when working with
binary files are:
● to write data from the program into a binary file
● to read data into the program from a binary file.
 The following code shows how you would write data to a binary file:

STATIC AND DYNAMIC DATA STRUCTURES

OpenFile ("[Link]", Binary) For Output as # 1
Write 1, "Help"
Write 1, True
Write 1, 3.123
Write 1, 5
Close #1
The following code shows how you would read data from a binary file into
a program:
Dim TTData as Binary
Open "TTFile" For Binary As #2
ReDim TTData(1 To LOF(2)) As Byte
Get 2, 1, TTData
Close #2

● Static and dynamic data A level only

structures
The way that data can be stored can be split into two broad categories –
dynamic and static. This reflects the fact that sometimes the programmer
will know how big a data structure will get and therefore how much
memory is needed to store it. More often than not, the amount of data
KEYWORDS stored within a data structure will vary while the program is being run.
Queue: a data structure where Different data structures such as queues and stacks can be implemented
the first item added is the first either as static or dynamic structures.
item removed. ● Static: A static data structure stores a set amount of data which
Stack: a data structure where is usually defined by the programmer. This is done by allocating a
the last item added is the first set amount of memory to the data structure. Accessing individual
item removed.
elements of data within a static structure is very quick as their
Static data structure: a method memory location is fixed. However, the data structure will take
of storing data where the up memory even if it doesn’t need it. Records and some arrays are
amount of data stored (and
examples of static data structures.
memory used to store it) is fixed.
● Dynamic: The word ‘dynamic’ means changeable. Dynamic data
Dynamic data structure: a structures can use more or less memory as needed through the
method of storing data where
use of a heap. In basic terms, unused blocks of memory are placed
the amount of data stored (and
memory used to store it) will
on a heap, which are then usable within a program. A dynamic data
vary as the program is being run. structure is able to take more memory off the heap if it is needed 55
and also put blocks of unused memory back onto the heap if it is not
Heap: a pool of unused memory
that can be allocated to a needed. This is a much more efficient use of resources and a more
dynamic data structure. flexible solution as elements can be added and removed much more
easily. Stacks, queues and binary trees are often implemented as
dynamic structures.
The programmer will normally put a limit on the maximum amount of
memory that any one data structure needs. However, it can lead to errors if
elements are removed from empty structures or added to full ones. There is
more on this in the following chapters.
 Static data structures Dynamic data structures
Inefficient as memory is allocated that Efficient as the amount of memory
may not be needed. varies as needed.
Fast access to each element of data as Slower access to each element as the
the memory location is fixed when the memory location is allocated at run-
program is written. time.
Memory addresses allocated will be Memory addresses allocated may be
contiguous so quicker to access. fragmented so slower to access.
Structures are a fixed size, making Structures vary in size so there needs to
them more predictable to work with. be a mechanism for knowing the size of
For example, they can contain a header. the current structure.
The relationship between different The relationship between different
elements of data does not change. elements of data will change as the
program is run.
Table 7.1 Comparison of static and dynamic data structures
Practice questions can be found at the end of the section on page 90.

TASKS
KEY POINTS 1 How can you access each element in an array?
• A data structure is any 2 Explain how you could use an array to keep track of personal best
method used to store data in times for the members of an athletic club. Your solution may require
an organised and accessible several dimensions.
format.
3 Explain the terms file, record and field in relation to data structures.
• An abstract data type is a
conceptual model of how 4 What are the typical uses of text files?
7 Data structures and abstract data types

data are organised and the 5 What are the typical uses of binary files?
operations on them.
6 Identify two examples of:
• An array is a data structure a) dynamic data structures
that contains data of the same b) static data structures.
type using a single identifier.
7 Identify two advantages of using dynamic data structures.
• A one-dimensional array is
also known as a list. 8 Identify two disadvantages of using dynamic data structures.
• Arrays can be multi- 9 Why are stack and queues considered to be dynamic data structures?
dimensional.
• Files are used to store data.
• A text file is one that simply
contains lines of text or other
STUDY / RESEARCH TASKS
human-readable characters. 1 Write code that will:
• A binary file is one that stores a) write data to a text file / read data from a text file
data as a series of 0s and 1s. b) write data to a binary file / read data from a binary file.
• Static data structures store 2 Write code that will:
a set amount of data which a) create an array
56 is usually defined by the b) read data from an array.
programmer.
3 Find out how a stack is used to manage a memory heap.
• Dynamic data structures can
use more or less memory as 4 PNG is a common binary format. Find out about other commonly used
needed through the use of a binary files.
heap. 5 Why might programmers create executable files as binary files?
 8 Queues and stacks

A level only
SPECIFICATION COVERAGE
[Link] Abstract data types/data structures
3.2.2 Queues
3.2.3 Stacks

LEARNING OBJECTIVES
In this chapter you will learn:
• how stacks and queues work and what they are used for
• the difference between a circular queue, linear queue and priority
queue
• how to write code to implement stacks and queues
• how to use nesting and recursion when implementing a stack.

INTRODUCTION
Queues and stacks are both examples of abstract data types that could
be implemented as dynamic or static data structures. They are also
abstract data types, which means that they do not normally exist as
built-in data types but need to be created by the programmer using
existing data types. For example, a stack might be built from an array.
This chapter looks at the standard uses of stacks and queues and how
to implement and work with them.

● How stacks work

A stack is an example of a LIFO (last in first out) structure that means that
KEYWORDS the last item of data added is the first to be removed. A stack in a computer
57
Stack: a LIFO structure where works in exactly the same way as a stack of books waiting to be marked or
the last item of data added is the a stack of dishes waiting to be washed up – whichever item was added to
first to leave.
the top of the stack last will be the first one to be dealt with.
LIFO: last in first out refers to a
data structure such as a stack However, unlike the washing up where items are literally taken off the stack
where the last item of data as they are needed, the data in a computer stack is not actually removed.
entered is the first item of data What happens is that a variable called the stack pointer keeps track of
to leave. where the top of the stack is.
 The process of adding a new item of data to the stack is called pushing
and taking an item off the stack is called popping. A further action called
peeking is used to identify the top of a stack. When an item is pushed onto
the stack the stack pointer moves up and when an item is popped off the
stack the pointer moves down, but a copy of the data is still left on the stack.
Here is a simplified example of a stack in use. Note that this stack can only
store six data items.

Stack pointer Bert

Cynthia

Cedric

Albert

The stack pointer is used to show where the top of the stack is.

Stack pointer Linda

Bert

Cynthia

Cedric

Albert

“Linda” has been pushed to the top of the stack so the pointer moves up.
8 Queues and stacks

Stack pointer Bert

Cynthia

Cedric

Albert
KEYWORD
Pointer: a data item that The stack is popped so the data at the pointer (“Linda”) is read and the
identifies a particular element in pointer moves down.
58
a data structure – normally the
front or rear. It is possible for the stack to need more memory than has been allocated to
it. In the example given above, assuming that the stack had been set up as
a static data structure, if the CPU tried to push on three more data items,
the last one would have nowhere to go. In this case a stack overflow error
would occur. Similarly if the stack was empty and the CPU tried to pop
an item, this would result in a stack underflow as there is no data to be
popped.
● Implementing a stack

USES OF STACKS
In the following two routines a single-dimension array called StackArray
has been used to represent the stack. The variable StackPointer is
being used to keep track of how far up or down the stack the pointer
should be and StackMaximum stores the maximum number of values
that can be stored on the stack.
‘routine to push on to a stack
‘check there is room on the stack
If StackPointer < StackMaximum Then
‘push on to the stack
StackPointer StackPointer + 1
StackArray(StackPointer) DataItem
Else
Error message "Data not saved – stack full"
End If
The error trap carries out an important task. The stack will only be
allocated a limited number of memory locations, which in this case is kept
in the variable StackMaximum. If the error routine was not there the
stack would overflow – there would be too much data to store in it.
This routine shows how an item can be popped off a stack. Notice that the
first line will trap an underflow error:
‘Routine to pop off a stack
‘check the stack is not empty
If StackPointer > 0 Then
‘pop off the stack
DataItem StackArray(StackPointer)
‘decrease stack pointer
StackPointer StackPointer – 1
Else
Error message "There is no data to pop from the
stack"
End If

● Uses of stacks
59

There are many uses for stacks. Due to their LIFO nature they can be used
anywhere where you want the last data item in to be the first one out. A simple
application would be to reverse the contents of a list as shown below:
1 2 3 4
Andrew Jane Mark Wendy
 The list above would go into the stack as follow:

Wendy

Mark

Jane

Andrew

If you now pull the names off the stack in order you would get:
1 2 3 4
Wendy Mark Jane Andrew

Stack frames
Stacks can be used to store information about a running program. In this
KEYWORDS case it is known as a stack frame and a pointer will be used to identify
Stack frame: a collection of data the start point of the frame. This is used as a call stack when running
about a subroutine call. programs as it can be used when a subroutine is running to call functions
Call stack: a special type of and pass parameters and arguments.
stack used to store information
about active subroutines and Function call and The function is called and data passed to it.
functions within a program. argument data The return address is placed on the stack so that
when the function is finished, it will look at the
return address so it knows where to go back to.
Return address
The subroutine is running using local variables.
When a function is called, the current position is
Saved frame pointer saved in the stack as a saved frame pointer.

KEYWORD This is the same mechanism that is used for handling interrupts and
Interrupt: a signal sent by exceptions in programs. Interrupts and exceptions are events where
a device or program to the hardware or software demand the attention of the processor and cause the
processor requesting its current program to stop. This could be something happening inside the
8 Queues and stacks

attention. program that is running or it could be an external event, such as a power

failure, or a printer running out of paper.
When this happens, special blocks of code called interrupt handlers and
exceptions handlers are loaded into memory and executed. Whilst the new
demand is being dealt with, the details of the first program are stored on a
stack. As soon as the interrupt or exception has been dealt with, the details are
taken back off the stack and the first program can carry on wherever it left off.

Nesting and recursion

60 It is common practice to nest program constructs. For example, you might
KEYWORDS want to put one selection process inside another, or you might have a
Nesting: the process of putting selection process being carried out inside an iterative loop. In this case the
one statement inside another details of the successive nested loops are stored on the stack.
statement.
Recursion: the process of a For HourCounter = 0 To 23
subroutine calling itself. For MinuteCounter = 0 To 59
For SecondCounter = 0 to 59
Output Hour , Minute , Second
 Next SecondCounter

QUEUES
Next MinuteCounter
Next HourCounter
This pseudo-clock won’t keep very good time, but it does show how For/
Next loops can be nested inside each other.
Stacks also play a vital role in a process called recursion. This is where a
subroutine calls itself in order to complete a task.

● Queues
A queue is called a FIFO (first in first out) structure. A queue in a
KEYWORDS computer acts just like people queuing for a bus – the first person in the
Queue: a FIFO structure where queue is going to be the first person to get on the bus and the first item of
data leaves in the order it data to be put into the queue in a computer will be the first to be taken out.
arrives.
A common use of queues is when a peripheral such as a hard disk or a
FIFO: first in first out refers to a
data structure such as a queue keyboard is sending data to the CPU. It might be that the CPU is not in a
where the first item of data position to deal with the data straight away, so they are temporarily stored
entered is the first item of data in a queue. Data being sent from the CPU might also need to be stored,
to leave. and this is certainly the case when a document is sent to a printer. In this
case your document is placed in the queue until the printer (which is a
very slow device compared to the CPU) has the time to deal with the job.
Queues that are used in this way are also known as buffers.
Here is a simplified example of how a queue is used. This queue can only
store six data items.
Front Rear
pointer pointer

Bert Cynthia Cedric Albert

The queue has already been sent four data items, but none has yet been
removed. The first item in the queue is “Bert” indicated by the front pointer.
The last item in the queue is “Albert” indicated by the rear pointer.
When an item is added to the queue it is added at the end. If a new item
(“Linda”) is added, notice that the rear pointer has moved and now points
to the new item “Linda”. The front pointer has not moved.
Front Rear
pointer pointer

Bert Cynthia Cedric Albert Linda 61

When a name is taken from the queue it is taken from the front. In this case
“Bert” is removed from the queue and the pointer moves to the next item in
the queue. The rear pointer does not move.
Front Rear
pointer pointer

Cynthia Cedric Albert Linda

 Linear, circular and priority queues
The examples above show a linear queue, that is, where you can envisage
KEYWORDS the data in a line. The first item in is the first item out. The maximum size
Linear queue: a FIFO structure of the queue is fixed in this case, although it could be dynamic. A typical
organised as a line of data, such method for storing data in a queue is to use a one-dimensional array.
as a list.
Circular queue: a FIFO data A circular queue can be envisaged as a fixed-size ring where the back of
structure implemented as a the queue is connected to the front. This is often referred to as a circular
ring where the front and rear buffer. As with a linear queue, it is the pointers that move rather than the
pointers can wrap around from data. However, with a circular queue the first items of data can be seen as
the end to the start of the array. being next to the last item of data in the queue.
A common implementation is for buffering, when items of data need to be
stored temporarily while they are waiting to be passed to/from a device.
Rear Front

Front Rear
5 1

1 2 3 4 5
4 2

Figure 8.1 Linear and circular queues

KEYWORD
Priority queue: a variation of a A priority queue adds a further element to the queue which is the priority
FIFO structure where some data of each item. For example, if documents are being sent to print on a network
may leave out of sequence where printer then it might be possible for the user or systems manager to control
it has a higher priority than other the queue in some way. They may be able to force print jobs to the top of the
data items. queue or to put print jobs on hold whilst others are pushed through. This is
known as a ‘priority’ queue and requires the programmer to assign priority
ratings to different jobs. Higher priority jobs are effectively able to jump
the queue. Where two jobs have the same priority, they will be handled
according to their position in the queue.

Implementing a linear queue

8 Queues and stacks

A queue is typically made up of a number of data items of the same type.

Therefore, a common implementation is to use an array. To demonstrate the
principle, this example shows a queue with a fixed size of nine elements.
There are currently five items in the queue and FP shows the front pointer
and RP shows the rear pointer.
FP RP
0 1 2 3 4 5 6 7 8
Alice Belinda Carly Daphne Erica
62
Note that it is possible for the queue to become empty or full as data is
added and removed, and that not every element has to have data in it.
Therefore, when the queue is implemented we need to know:
● the name of the array
● the maximum size of the queue
● whether the queue is full or empty
● where the front of the queue is
● where the rear of the queue is.
Assuming that element 0 is the front of the queue and element 4 is the rear,
when an item is removed, the queue will then look like this:

QUEUES
FP RP
0 1 2 3 4 5 6 7 8
Belinda Carly Daphne Erica

The front pointer has moved +1 so that the front is now pointing at
element 1. The rear pointer does not change so remains on position 4.
Any item of data added to the queue is added to the rear. In this case it
would be added in position 5 as this is the next available position. For
example, if we add “Beth”:
FP RP
0 1 2 3 4 5 6 7 8
Belinda Carly Daphne Erica Beth

The front pointer is now on position 1 and the rear pointer is on position 5.
Items can now be added and removed with the front and rear pointers moving
accordingly. For example, if we removed the next two elements and added a
new name “Jessica”, the queue would look like this:
FP RP
0 1 2 3 4 5 6 7 8
Daphne Erica Beth Jessica

The front pointer will have moved forward to position 3 and the rear
pointer will have moved to position 6.
Eventually, if data items keep being added, the rear pointer will reach the end
of the array and there will be no more room in the array to add new elements,
despite some earlier locations in the array being empty because elements have
been removed from the front of the queue. The simplest way to deal with this
is to always keep the front pointer pointing at index 0 in the array, and to move
elements forward in the array each time an item is removed. This method is
simple, but it can be quite time consuming to move the elements along in the
array, especially if the queue is a long one. Therefore a more efficient method
of dealing with this problem, known as a circular queue, is more common.

Implementing a circular queue

A circular queue works in a similar way to a linear queue except the front and
rear pointers move when an item is added or removed, making more efficient
use of memory. For example, in the linear queue above, items 1, 2 and 3 have
all been removed. However, there is no way of adding items into those empty
elements in the array as the front pointer has moved to element 3. 63

The circular queue makes use of the spaces that are freed up at the front
of a queue after they have been removed. It does this by wrapping the
rear pointer around the array starting again at element 0 once the queue
becomes full. If we start with the same queue as before, the front pointer
is 0 and the rear pointer is 4.
FP RP
0 1 2 3 4 5 6 7 8
Alice Belinda Carly Daphne Erica
 If two items are removed, the queue will then look like this:
FP RP
0 1 2 3 4 5 6 7 8
Carly Daphne Erica

Four new items are now added to the queue: “Jane”, “Davina”, “Yvonne “and
“Kelly”. Notice that the rear pointer is now on 8.
FP RP
0 1 2 3 4 5 6 7 8
Carly Daphne Erica Jane Davina Yvonne Kelly

As this is a circular queue, the rear pointer can now wrap back around to
the beginning. If a further item is added, the rear pointer would move to
position 0 as this free. To add “Maria”:
RP FP
0 1 2 3 4 5 6 7 8
Maria Carly Daphne Erica Jane Davina Yvonne Kelly

In the following pseudo-code the variable Rear is used to point to the

end of the queue and Front is used to point to the start of the queue.
The pseudo-code does not deal with the situations of the queue being
either empty or full.
The code for adding a new item to a nine-element queue looks something
like this:
‘routine to add to a circular queue
‘increment Rear pointer
Rear Rear + 1
‘Check to see if end of array has been reached
8 Queues and stacks

‘If so go back to the start of the array

If Rear = 9 Then Rear 0
‘add data
Put DataItem at position Rear in array
The code for taking an item from the front of the queue might look like this:
‘routine to remove data from a circular queue
‘remove data
64
Take DataItem from position Front in array
‘move Front on
Front Front + 1
‘Check to see if the end of the array has been
reached
‘If so go back to the start of the array
If Front = 9 Then Front 0
Implementing a priority queue

QUEUES
A priority queue can also be implemented using an array by assigning a
value to each element to indicate the priority. Items of data with the highest
priority are dealt with first. Where the priority is the same, then the items
are dealt with on a FIFO basis like a normal queue.
There are two possible solutions using an array. One option is to use a
standard queue where items are added in the usual way at the end of the
queue. When items are removed, each element in the array is checked for
its priority to identify the next item to be removed. Where this method is
used, adding data is straightforward but removing it is more complex.
Starting with the same queue, this time a priority is included shown here in
subscript and assuming that 1 is highest priority.
FP RP
0 1 2 3 4 5 6 7 8
Alice2 Belinda1 Carly2 Daphne3 Erica4

If an item is added, it is simply added with its priority at the end and the
rear pointer is moved. If “Jane” were added with a priority of 1:
FP RP
0 1 2 3 4 5 6 7 8
Alice2 Belinda1 Carly2 Daphne3 Erica4 Jane1

When data is removed, it is done so in order of priority. There are two

items with a priority of 1. In this case, “Belinda” would be removed first as
she is closest to the front of the queue. “Jane” would be the next item to be
removed. In this example it shows how the principle of FIFO is still being
used as “Belinda” entered the queue before “Jane”.
An alternative is to maintain the queue in priority order, which means that
when a new item is added, it is put into the correct position in the queue.
Removing items can then be done in the usual way by taking the item
at the front of the queue. Where this method is used, removing data is
straightforward but adding it is more complex.
Working on the same list, this time the names would be in priority order.
To remove the next item is just a case of removing the item at the front of
the queue.
FP RP
0 1 2 3 4 5 6 7 8
Belinda1 Alice2 Carly2 Daphne3 Erica4
65
Therefore the first item to be removed would be “Belinda” as she has the
highest priority:
FP RP
0 1 2 3 4 5 6 7 8
Alice2 Carly2 Daphne3 Erica4
 If a new item is added, it will be put into the correct position based on its
priority. Where it has the same priority it will be added after the existing
items of the same priority. For example, if “Yvonne” is added with a priority
of 1:
FP RP
0 1 2 3 4 5 6 7 8
Yvonne1 Alice2 Carly2 Daphne3 Erica4

If “Kelly” is added with a priority of 2:

FP RP
0 1 2 3 4 5 6 7 8
Yvonne1 Alice2 Carly2 Kelly2 Daphne3 Erica4

Practice questions can be found at the end of the section on page 90.

TASKS
1 What is meant by the terms pushing and popping?
2 The name ”Robert” is pushed on to an empty stack. ”Felicity”, ”Martin”
and ”Sam” are then pushed onto the same stack in that order. What
data will be on the stack after the following operations? Pop one
name, push on ”Henry” then push ”George”, finally pop off one name.
3 Explain the purpose of the stack pointer.
4 A stack can be described as a LIFO and a queue as a FIFO. Use
examples to explain the terms LIFO and FIFO.
KEY POINTS 5 Explain the difference between static and dynamic data structures
• Queues and stacks are with reference to stacks and queues.
dynamic data structures. 6 Explain the difference between linear, priority and circular queues.
• A stack is an example of
a LIFO (last in first out)
structure which means that
STUDY / RESEARCH TASKS
8 Queues and stacks

the last item of data added is

the first to be removed.
1 Explain how a circular queue can be used to cope with a user entering
• A queue is called a FIFO (first data via a keyboard.
in first out) structure which
means that the first item of 2 Write code that demonstrates the use of a flag to indicate if a user has
data added is the first to be pressed an invalid key.
removed. 3 Explore other methods of implementing a priority queue other than
• There are three types of using an array, for example using linked lists or binary trees.
queues: linear, circular or 4 Write code to show how a pointer can be used to indicate the highest
priority. value held in a 20-element array.
66
 9 Graphs and trees

A level only
SPECIFICATION COVERAGE
3.2.4 Graphs

LEARNING OBJECTIVES
In this chapter you will learn:
• what graphs are and how they are constructed and used
• that graphs can be directed or undirected, weighted or unweighted
• how to use adjacency lists and matrices to represent graphs
• what trees are and how they are used
• how to create a binary tree.

INTRODUCTION
A graph is a mathematical structure that models the relationship
KEYWORDS between pairs of objects. The pairs of objects could be almost anything
Graph: a mathematical structure including places, people, websites, numbers, physical components,
that models the relationship biological, chemical data or even concepts. The study of the use of
between pairs of objects. graphs is called graph theory and it is useful in computing as it allows
Graph theory: the underlying the programmer to model real-life situations that would otherwise be
mathematical principles behind abstract.
the use of graphs.
Arc: a join or relationship
between two nodes – also known To start with an example, a graph could be used to model the relationship
as an edge. between two places and how they are connected via a train line. In graph
Vertex/vertices: an object in a theory, objects are called nodes or vertices and each connection is called
graph – also known as a node. an edge or arc. In this simple example, we have two vertices, one for each
(Vertices is the plural.) town and one edge, which in this case will be the train connection between
Weighted graph: a graph that the two towns. A simple graph may look like this:
67
has a data value labelled on each
edge.
Town A Town B

A weighted graph can be created by adding values to the edges. In this

example, we might add the travel time between the two towns, so the
weighted graph would look like this:

30
Town A Town B
 To extend this example, you might add in all of the towns on a particular
network, with the travel time between each point. Figure 9.1 shows a graph
that models the real-life situation so you can see that there is no direct
connection between some of the towns, therefore there is no edge between
some of the vertices.

30
Town A Town B 60

20 20 Town E

30
Town C 30
Town D

Figure 9.1 A graph structure to show journey times between towns

The graph now becomes quite useful as it could be used, for example, to find
the quickest journey times between two towns. For example, to travel by
train from Town A to Town E would be quicker via Town C and Town D
than via Town B.
Graphs can also be directed or undirected, which refers to the direction of
KEYWORDS the relationship between two vertices.
Undirected graph: a graph An undirected graph is when the relationship between the vertices can
where the relationship between be in either direction. In this example, the train will go in either direction
vertices is two-way. between the towns, which means there is a two-way direction between the
Directed graph: a graph where vertices in the graph.
the relationship between vertices
A directed graph (also known as a digraph) is where there is a one-way
is one-way.
relationship between the vertices. For example, we may produce a digraph
to represent a real-life situation where we are creating a family tree.
Figure 9.2 is a graph that shows parents and siblings.

Charles Pauline
9 Graphs and trees

Harry

Dave
Jack

Figure 9.2 Graph to show parents and siblings

In this case, Charles is the parent of Dave and Pauline, Pauline is the parent
of Jack and Harry. The arrows indicate that this is a one-way relationship.
68
● Uses of graphs
Graphs have a wide range of uses in computing, as they are able to model
complex real-life problems. There are a number of applications:
● Human networks: Human beings belong to numerous networks including

family, work and social groups. For example, LinkedIn is an online network
of business professionals and works on links between people. Once you
create a profile, you link to other professionals that you know and they in
turn link to all of the other people that they know. Each person is a vertex,
and each edge is a relationship between one person and another.
 ● Transport networks: All transport works on the basis of a departure

USES OF GRAPHS
point, arrival point and route. The departure and arrival points form the
vertices and the routes form the edges. There are several applications for
graph theory including calculating quickest routes, planning timetables,
scheduling and organising staff.
● The Internet and web: It is possible to ‘map’ the Internet or the World
Wide Web using graph theory. In the case of the Internet, each
connected device is a vertex with the physical connection forming the
edge. With the web, each website is a node, with each linked site forming
the edge. Figure 9.3 shows a map of the Internet.

Figure 9.3 Graph to show a ’map’ of the Internet

Notice that rather than forming a web shape, it looks more like a
fireworks display. Each of the concentrations of colour is where there is
KEYWORD an ISP as all the data is being routed through their servers.
Latency: the time delay that ● Computer science: Latency is a key factor in communication networks.
occurs when transmitting data It refers to the time delay that occurs when data is being transmitted.
between devices. Graph theory could be used to calculate the quickest path to send data
around a microprocessor where each vertex is a processor component
and the edges are the buses that carry the data.
● Medical research: Understanding how diseases spread is critical to their
prevention. For example, if studying the spread of a flu virus, each case
of flu could be a node, or more likely, each location where there has been
an outbreak would be a vertex. The edges would be the distance between
locations. A weighted graph could be used to analyse the extent of outbreaks 69
in particular locations and how much that then spreads between vertices.
● Project management: Any kind of large-scale project can be modelled
using a graph. For example, this might be an engineering, construction
or IT project. In this case the vertices would be each of the actions
needed to complete the project and the edges would be the relationships
and dependencies that exist between the tasks.
● Game theory: This is used in wars and conflicts to try to understand the
causes of conflict and predict the likely actions that people might take
for different strategies. For example, in a battle, the vertices could be the
actions that one group might take, with the edges being the outcomes.
 Graph theory is also an important concept in relation to Dijkstra’s
algorithm. This calculates the shortest path between nodes. It has been
used for applications such as working out shortest distances between cities
and calculating shortest distances between vertices in computer networks.
This is covered in detail in Chapter 13.

● Adjacency list
A graph is an example of an abstract data type. So far we have considered
KEYWORD the graph in graphical form, but we need to represent it in a way that can
Adjacency list: a data structure be stored and manipulated by the computer. The first method is to use a
that stores a list of nodes with list, called an adjacency list.
their adjacent nodes.
Adjacent means ‘next to’, so the idea of the adjacency list is to store the
value of the vertices along with the vertices that they are next to. There are
three basic formats for the list depending on whether the graph is direct or
undirected and whether it is weighted.

Undirected graph
Vertex Adjacent vertices A B
A B,C
E
B A,C,E
C A,B,D
D C,E C
E B,D D

The list shows each vertex and each vertex that it is adjacent to. All
adjacencies are shown as this is a two-way relationship.

Directed graph
Vertex Adjacent vertices A B
A B,D
E
B E
9 Graphs and trees

C
D C,E C
D
E

The list only shows the one-way relationship between the vertices. For
example, D is connected to C but C is not connected to D.

Weighted graph
20
A B
70 Vertex Adjacent vertices 25

A B,20,C,30 30 E
B A,20,C,30,E,25 30

C A,30,B,30,D,35 40
C 35
D C,35,E,40 D
E B,25,D,40

The list shows the value of each edge after each adjacent vertex. For
example, A is adjacent to B with a weighted value of 20, A is adjacent to
C with a weight value for 30 and so on. Notice that this example is an
undirected weighted graph.
 ● Adjacency matrix

ADJACENCY MATRIX
The second method for storing the data is to use an adjacency matrix.
KEYWORD This method uses a two-dimensional array or grid populated with 1s
Adjacency matrix: a data and 0s.
structure set up as a two-
dimensional array or grid that Undirected graph
shows whether there is an edge
between each pair of nodes. A B C D E
A B
A 0 1 1 0 0
B 1 0 1 0 1 E
C 1 1 0 1 0
D 0 0 1 0 1 C
E D
0 1 0 1 0

This works by putting a 1 in each cell where there is an edge and a 0 in each
cell where there is not an edge. For example, A is adjacent to B so there will
be a 1 in the grid where A and B intersect in the matrix. A is not adjacent to
D so there will be a 0 in the grid where A and D intersect in the matrix.

Directed graph
A B C D E
A B
A 0 1 0 1 0
B 0 0 0 0 1 E

C 0 0 0 0 0
D 0 0 1 0 1 C
D
E 0 0 0 0 0

In this case, you read the matrix row by row, inserting a 1 where there is
a one-way relationship between two vertices and 0 where this isn’t. For
example, A has a one-way relationship to B so there is a 1 in the cell where
A and B intersect in the matrix. B does not have a one-way relationship to
A, so there is a 0 in the cell where B and A intersect in the matrix.

Weighted graph
A B C D E 20
A B 25
A ∞ 20 30 ∞ ∞
B 20 ∞ 30 ∞ 25 30 E
30
C 30 30 ∞ 35 ∞
40
D ∞ ∞ 35 ∞ 40 C 35 71
D
E ∞ 25 ∞ 40 ∞

In this case, you follow the same process for an undirected graph, but this
time you input the weighted value rather than a 1. Instead of the 0, the
infinity sign is used.
 ● Adjacency list vs adjacency matrix
When deciding on which implementation to use it usually comes down to
two factors: speed and memory. Speed refers to how quickly the program will
be able to access the data structure and produce a result. Memory refers to
the amount of memory that each implementation will use. Bear in mind that
the graph structure is likely to be used with very large datasets, making these
issues critical. If you consider the simple examples above, five vertices will
produce 25 data items that need storing. 100 vertices would produce 10 000
and 1000 vertices would produce a million data items. If a single byte was
used to store each data item that would create a 1 MB file. If you envisage
thousands or even millions of vertices, the file sizes can get very large.
Table 9.1 shows the main factors.
Table 9.1 Comparison of adjacency list and adjacency matrix

Adjacency list Adjacency matrix

Only stores data where there is an Stores a value for every combination
adjacency (edge) so requires less of node adjacencies so requires
memory. more memory.
The list has to be parsed to identify Adjacencies can be identified more
whether particular adjacencies exist, quickly as every combination is
which increases the time taken to process already stored. Effectively the matrix
the data. forms a look-up table of each node to
every other node.
Where there are not that many edges (few Where there are many edges (lots of
adjacencies), this method would be more adjacencies), this method would be
suitable for the reasons stated above. This more suitable for the reasons stated
is known as a sparse graph. above. This is known as a dense
graph.

There is more information on working out time and size complexity of

different algorithms in Chapter 25.

● Trees
9 Graphs and trees

A tree is an abstract data structure that is very similar to a graph in that

KEYWORDS it has nodes and edges. It is called a tree because it is visualised as a
Tree: a data structure similar to hierarchical structure (like a family tree) with branches. Trees can have a
a graph, with no loops. root node, with all the other nodes branching away from the root.
Node: an object in a graph – also
known as a vertex. The key difference with a tree compared to a graph is that it is connected and
Edge: a join of relationship
undirected and can contain no cycles or loops. For example, A goes to B and
between nodes – also known as C, but you could not go from A to B to C or from A to C to B and back to A.
72 an arc. A tree could be visualised as follows:

A B

C
D

Figure 9.4 A tree structure

 In this example, there are five nodes and four edges:
KEYWORDS

TREES
● A is the root node as all the other nodes branch away from it.
Root: the starting node in a ● A is also a parent node as it has two child nodes B and C.
rooted tree structure from which ● B is also a parent node and has two child nodes, D and E.
all other nodes branch off. ● C, D and E have no child nodes. These are sometimes called leaf nodes.
Parent: a type of node in a tree, ● You can see that there are no cycles. For example, A has an edge with C
where there are further nodes forming a single path. It would not be possible for example to go from A
below it. to C to D and back to A.
Child: a node in a tree that has
Trees have a number of uses. They:
nodes above it in the hierarchy.
● can be used to store data that has an inherent hierarchical structure. For
Leaf: a node that does not have
any other nodes beneath it. example, an operating system may use a tree for directories, files and
folders in its file management system
● are dynamic, which means that it is easy to add and delete nodes
● are easy to search and sort using standard traversal algorithms. There is

more on this in Chapter 16

● can be used to process the syntax of statements in natural and programming

languages so are commonly used when compiling programming code.

Binary search trees

A common implementation of a tree is the binary search tree. This is a directed
and rooted tree, which can have no more than two branches off each node and
is commonly used to store data that are input in a random order. The nature of
the structure means that data are automatically sorted as they are entered and
that it can be ‘traversed’ in order to search for and extract data from it.
The first item of data to be used is stored in the root node. The next (and
any subsequent) data item is dealt with by the following routine:
● If the value of the new data item is less than the value in the current node

then branch left, otherwise branch right.

● Keep repeating this process until you come to an ‘empty’ branch, then

put the new value in the node at the end of the branch.
KEYWORD This sounds awkward but look at the diagram below and try to follow
Binary tree: a tree where each through how the name “Fred” has been added to the binary tree.
node can only have up to two
Daniel
child nodes attached to it.
Charles George

Belinda Cheryl Fred

Figure 9.5 An example of a binary tree

Daniel is the root node. Belinda, Cheryl and Fred can be classed as leaf
nodes because they have no nodes below them. Charles can be described as
the parent and Cheryl the child. 73

Implementing a binary tree

The code for creating a binary tree needs three arrays. The first (called
Node in the example below) stores the data itself. The second (Left in the
example) stores which node the left branch from a node moves to and the
third (Right) copes with branches to the right.
The data to add to the tree is stored in the variable AddItem and the root
node has already been set up with the name “Jim”. The algorithm adds
further data items to the binary tree:
 ‘Find next gap in the Node array
NodeCount 1
While Node(NodeCount) is not empty
NodeCount NodeCount + 1
End While
‘NodeCount stores the next blank
Node(NodeCount) AddItem
‘start at the root node
PresentNode 1
While Node(PresentNode) is not empty do
‘Branch Left or Right?
If AddItem < Node(PresentNode) Then
‘If Left branch is empty then assign NodeCount
If Left(PresentNode) = 0 Then
Left(PresentNode) NodeCount
End If
PresentNode Left(PresentNode)
Else
‘If Right branch is empty then assign NodeCount
If Right(PresentNode) = 0 Then
Right(PresentNode) NodeCount
End If
PresentNode Right(PresentNo)
End If
End While
9 Graphs and trees

If the root starts with the name “Jim”, the arrays should look like this after
you have added the names Kevin, Alice and Belinda to the tree.
Node () Left() Right()
1 Jim 3 2
2 Kevin 0 0
3 Alice 0 4
4 Belinda 0 0
74

The binary tree this represents will look like this.

Jim

Alice Kevin

Belinda
Figure 9.6 The resultant binary tree

Practice questions can be found at the end of the section on page 90.
 TREES
TASKS
1 Create an adjacency list and matrix from the following graphs.
A B A B

C D C D

2 Draw an undirected graph from the following adjacency matrix.

A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 0
D 1 1 0 0

3 Draw a directed graph from the following adjacency list.

Vertex Adjacent vertices
A B
B D
C D
D A

4 Draw a weighted undirected graph from the following data adjacency list.
Vertex Adjacent vertices
A B,5,C,3
B A,5,D,2
C A,3
D B,2

5 Draw a weighted undirected graph from the following data adjacency

matrix.

A B C D
A ∞ 10 20 ∞
B 10 ∞ ∞ 30
C 20 ∞ ∞ 20
D ∞ 30 20 ∞

6 Explain where it might be more appropriate to use an adjacency list

compared to an adjacency matrix.
75
7 Draw a binary tree from the following array:
Sequence Vertex Left Right
1 E 2 0
2 D 3 0
3 A 0 4
4 B 0 5
5 C 0 0
 8 Represent the following binary tree using arrays:
Blue

Aqua Green

Orange Purple

Show what would happen to the tree and the array if the following two
items of data were added: Yellow, Magenta.

STUDY / RESEARCH TASKS

1 Explain how the following well-known abstract problems were solved
using graph theory:
a) bridges in Konigsberg
b) the travelling salesperson problem
c) the four-colour theorem (for colouring maps)
d) six degrees of separation (in social networks).
2 ‘No two web pages are separated by more than 19 clicks.’ How could
graph theory help you work out whether this is true or not?
3 Explain how graph theory could help computer security experts
understand how worms spread.
4 How might graph theory be applied to the problem of timetabling in a
school or college?
5 How might a tree be used to create routing algorithms that define how
data is sent around networks?
6 What are red–black B trees? How do they differ from binary trees?

KEY POINTS
• Graphs are a data structure made up of vertices (nodes) and edges,
9 Graphs and trees

which are the connections between the vertices.

• Graphs can be used to analyse the connections and relationships
between data items and are a useful tool for modelling real-life
situations.
• Graphs can be directed or undirected, meaning that there may be a
one-way or two-way connection between each vertex.
• Graphs can be weighted, meaning that a value can be applied to the
edges between nodes.
• An adjacency list or matrix can be used to identify which vertices
76 are connected to which others and whether there is any weight
associated with the edge.
• A tree structure is a connected, undirected graph that contains no
cycles.
• A binary tree structure is a special type of tree where each vertex can
have no more than two children.
10 Hash tables and
dictionaries
A level only
SPECIFICATION COVERAGE
3.2.6 Hash tables
3.2.7 Dictionaries

LEARNING OBJECTIVES
In this chapter you will learn:
• what hash tables are used for and how to create them
• how to create a hashing algorithm
• how to avoid collisions in hashing algorithms
• what a dictionary data structure is and how to construct one.

KEYWORDS
Hash table: a data structure that INTRODUCTION
stores key/value pairs based Hash tables and data dictionaries are both data structures made up of
on an index calculated from an two parts. They can be viewed as two-dimensional arrays, or tables with
algorithm. one dimension being the data and the other being the key that identifies
Key/value pair: the key and its the location of the data in the table. Each key/value combination is
associated data. unique within the data structure.

● Hash tables
A hash table is a data structure made up of two parts, a table (or array) of
KEYWORD data, and a key, which identifies the location of the data within the table. A
Hashing algorithm: code that hashing algorithm is carried out on the key, which then acts as an index
creates a unique index from to the specific location of that data item within the array. You could think
given items of key data.
of it as a look-up table that uses a key/value combination.
77
When the data need to be retrieved, for example, if a search is carried out
on the data, the same hashing algorithm is used on the key being searched
to calculate the index and therefore retrieve the data in one step. This is
a very efficient search technique and it is why hashing tables are used
extensively in applications where large datasets need to be accessed or
where speed of access is critical.
As an example, a customer database stored as an array may contain
records of millions of customers including CustomerID, Name, Address
and so on. A hashing algorithm could be applied to the CustomerID
 field, which can be used as the key in this case. This would generate
an index for each customer, which would point to the location of the
record in the array.
This could be visualised as follows:
Key Index Key/value pair
014563 01 014564, Mary Jones, 14 Acacia Avenue
02
014564 03 014563, John Smith, 1 High Street
04
014565 05
06 014565, Len Brown, 56 The Pines
Figure 10.1 Visualisation of a hash table

The array into which the data are being stored can be envisaged as a series
of slots, each of which has a unique index. The index can then be used to
access all of the data stored in the record. Note that the key/value pair is the
key and all of the data stored in relation to that key. In this case it would be
a customer record.

Uses of hashing algorithms

Hashing algorithms have many applications:
● Databases: Used to create indices for databases enabling quick storage

and retrieval of data.

● Memory addressing: Used to generate memory addresses where data will

be stored. It is particularly useful for cache memory, where data is placed

KEYWORD temporarily allowing the user fast access to programs and data stored in
Cache: a high-speed temporary the cache.
area of memory. ● Operating systems: As an example of memory addressing, some

operating systems use hashing tables to store and locate the executable
10 Hash tables and dictionaries

files of all its programs and utilities.

● Encryption: Used to encrypt data, hence the term ‘encryption key’. In

this case the algorithm must be complex so that if data is intercepted it is

not possible to reverse-engineer it.
● Checksums: A value calculated from a set of data that is going to be

transmitted. On receipt the algorithm is run again on the data and the
two results are compared as a way of checking whether the data has been
corrupted during transmission.
● Programming: Used to index keywords and identifiers as the compiler

will need access to these quickly as it compiles the program.

Hashing algorithms
To generate the index, you need a suitable algorithm. To start with we will
look at a very simple example to show the concept. You might have an array
78
0 with six elements used to store six values. We could calculate the index
using an algorithm that adds the numbers (digits) in the key together and
1 34255 then performs a modulo 6 sum on the result, as there are six slots in our
2 25463 hash table.
● For the first data item the value of the key might be 25463.
3
● Add the numbers (digits) together 2 + 5 + 4 + 6 + 3 = 20.
4 ● Perform modulo 6 calculation so divide by 6 = 3 r 2.
● Therefore the Index = 2.
5
● The data is placed in slot 2.
 ● The second data item might have a key with the value 34255.
Add the numbers (digits) together 3 + 4 + 2 + 5 + 5 = 19.

HASH TABLES
●
● Perform modulo 6 calculation so divide by 6 = 3 r 1.
● Therefore the Index = 1.
● The data is placed in slot 1.
This process then continues for every key. You can see from this how
the index is created from the data in the key. The real benefit of using an
algorithm is that it is used to store the data in the first place and then used
to locate the data when it is needed. The indices therefore are created and
recreated when they are needed.

Choosing a hashing algorithm

The basic example above demonstrates a few features and associated
problems when creating a suitable algorithm:
● A numeric value needs to be generated from the data in order to perform

the calculation. For non-numeric keys such as text and other characters,
the ASCII or Unicode value of each character is normally used.
● It must generate unique indices. For example, if the next item of data was
KEYWORDS 43525, the algorithm would generate the index of 1 again. There is already
Collision: when a hashing data stored in this location so this has created a collision. It is theoretically
algorithm produces the same possible to create a perfect hashing algorithm that avoids collisions, but
index for two or more different in practice, they are unavoidable. A good algorithm will create as few as
keys. possible and needs a mechanism to cope with collisions as they occur.
Clustering: when a hashing ● It needs to create a uniform spread of indices. For example, if you were
algorithm produces indices that storing millions of items of data into millions of slots the algorithm
are not randomly distributed. needs to provide an even spread of index values from the data and avoid
Load factor: the ratio of how clustering. This cuts down the possibility of collisions.
many indices are available to ● There must be enough slots to store the volume of data. For example,
how many there are in total. if a database is going to store 1 million records, the algorithm must be
capable of producing at least 1 million indices. In fact it would need
more than this to avoid collisions as the table fills up. Hash tables have a
load factor which is the number of keys divided by the number of slots.
A high load factor means that it will become increasingly difficult for the
algorithm to produce a unique result.
● It has to balance the issues of speed with complexity. For example, an

algorithm for a database needs to calculate the index very quickly. An

algorithm for encryption needs to be very complex, but may not need to
calculate the index quickly.
Creating suitable algorithms is sometimes described as a ‘black art’ as
there is no universally accepted method for doing it and the design of the
algorithm depends to a large extent on the application.
79
KEYWORDS Collisions
Index: the location where values One of the main features of a hashing algorithm is that it must produce
will be stored, calculated from a unique index. Where a collision occurs, there must be some way of
the key. handling it so that a unique index can be assigned to the key.
Chaining: a technique for There are two main methods:
generating a unique index when
● Chaining: In this case, if a collision occurs, a list is created in that slot
there is a collision by adding the
key/value to a list stored at the and the key/value pair becomes elements of the list. If another collision
same index. occurs, that key/value pair becomes the next element in the list and so
on. Figure 10.2 shows the concept.
 Key Index Key/Value pair List
00
01234 01 01235 Jones
02
01235 03 01234 Smith
04
01236 05
06
01237 07 01236 Harris 01237 James 01238 Brown
08
01238 09
10

Figure 10.2 Chaining of key/value pairs when there is a collision

Where the index is unique, the key/value pairs work in the normal way.
Where two or more keys generate the same index, a list is formed. It is
called chaining as the additional key/value pairs get chained together
inside a list. Each key/value pair is uniquely identified by its position
within the list. In this example the keys 01236, 01237 and 01238 all
KEYWORD produced the same index so their key/values have been chained together.
Rehashing: the process of ● Rehashing: In this case, if a collision occurs, the same algorithm is run
running the hashing algorithm again, or an alternative algorithm is run until a unique key is created.
again when a collision occurs. This normally uses a technique called probing, which means that the
algorithm probes or searches for an empty slot. It could do this by simply
looking for the next available slot to the index where there was a clash.

Key Index Key/Value pair

00
01234 01 01235 Jones
02
01235 03 01234 Smith
04
01236
10 Hash tables and dictionaries

05
06
01237 07 01236 Harris
08 01237 James
01238 09 01238 Brown
10

Figure 10.3 Probing as a result of a collision

Figure 10.3 shows a simple linear probe where the next available slot is
used. This is not very sophisticated because if the hashing algorithm is
leading to clustering as in this example, the results are still going to be
clustered in around the same slots. A more sophisticated method is to apply
another hashing function to the index where the clash occurred, in order to
generate another one.
80 The following extract of code shows a hashing algorithm that creates a key
using the day and date of birth multiplied by 28 with modulo 100 applied
to the result. Notice that it also rehashes if there is a collision:
Private Sub cmdFindRecord_Click(ByVal sender
As [Link], ByVal e As [Link])
Handles [Link]
 Dim FindRecord As String

HASH TABLES
Dim FindDay As Integer
Dim FindMonth As Integer
Dim HashKey As Integer
‘ calculate hash key
FindRecord = [Link]
FindDay = Val(Mid(FindRecord, 1, 2))
FindMonth = Val(Mid(findRecord, 4, 2))
HashKey = (28 * (FindMonth - 1) + FindDay) Mod 100
[Link] = "(28 * (" & FindMonth & " - 1) +
" & FindDay & ") Mod 100 = " & HashKey
If [Link](HashKey).Cells(3).Value =
[Link] Then
‘ record found using first hash key
[Link](HashKey).DefaultCellStyle.
BackColor = [Link]
MsgBox("Match found using hashing algorithm")
[Link](HashKey).DefaultCellStyle.
BackColor = [Link]
Else
Do
HashKey = HashKey + 1
If [Link](HashKey).Cells(3).Value =
[Link] Then
‘ found using rehashing
[Link](HashKey).DefaultCellStyle.
BackColor = [Link]
MsgBox("Collision occured. Match found
using linear re-hashing")
[Link](HashKey).DefaultCellStyle.
BackColor = [Link]
Exit Sub
End If 81
Loop Until [Link](HashKey).Cells(3).Value
= "" Or HashKey = 100
‘ record not found
MsgBox("No match for that date")
End If
End Sub
End Class
 ● Dictionaries
A dictionary is an abstract data type that maps keys to data. It is called an
KEYWORDS associative array in that it deals with two sets of data that are associated
Dictionary (data structure): a with each other. The dictionary data structure is analogous with a real-life
data structure that maps keys dictionary in that there is a word (the key) associated with a definition (the
to data. data). This is similar to a hash table in that it has key/value pairs.
Associative array: a two-
dimensional structure containing In the same way that a real-life dictionary is accessed randomly, a
key/value pairs of data. dictionary data structure also requires random access. The common
procedures that you would need to carry out on a dictionary would be to
add, retrieve and delete data. Unlike a real-life dictionary however, the data
inside a dictionary data structure is unordered.
We could use the customer database example again here. Each record has
a key, which might be the CustomerID. This key links to all of the data
that is stored about the customer. At any time we may want to retrieve, add
or delete a customer record. Dictionary data structures are often used to
implement databases due to the fact that there will be inherent associations
within the data and that they need to be searched and sorted as a matter of
routine in order to retrieve data.
In simple terms the dictionary data structure can be envisaged as a two-
dimensional array:
Table 10.1 A two-dimensional array

Key Associated data

e.g. CustomerID
01234 James Cochran, 12 Harbour Mews, Leicester
01235 Mary Abbot, 56 Eagle Street, Manchester
01236 Keith Fletcher, 3 Yarborough Road, Leeds
10 Hash tables and dictionaries

01237 Hussain Khan, 68 Lemon Street, Derby

01238 David Lui, 87 Threddle Lane, Northampton
01239 Rachel Young, The Forest Lodge, Kettering

As you can see from this example, dictionaries and hash tables are very
similar and in fact a hash table is one way of implementing a dictionary.
Dictionaries can also be created using binary trees (see Chapter 9).
Some programming languages such as Visual Basic and Python have a
dictionary data type built in. For example, in Python, it is possible to use
a dictionary constructor to build a dictionary directly from the key/value
pairs. Visual Basic has a dictionary object which allows key/value pairs to
be added directly.
82 The following Visual Basic-based pseudo-code shows the implementation of
a dictionary data structure using the data dictionary type. To add an item:
Dim Dict As Dictionary (Of String, Integer)
[Link] ("Anne", 10)
[Link] ("Dave", 52)
[Link] ("Ethel", 17)
 The data in speech marks is the key and the integer is the value assigned
to it in the format ("key", value) where key is a string and value is an

DICTIONARIES
integer. This code simply adds three names to the dictionary.
To retrieve an item from the dictionary the key/value pair need to be identified:
For Each pair As KeyValuePair(Of String, Integer)
In dict
MsgBox([Link] & " - " & [Link])
Next
This code would display the list of all the names in the dictionary in a
message box.
To delete an item:
[Link] ("Anne")
This code would delete the item identified by the value input, in this
case, “Anne”.
Practice questions can be found at the end of the section on page 90.

TASKS
1 What is a hash table data structure?
KEY POINTS 2 Suggest a suitable hashing algorithm that could be used to store
• A hash table is a data the names of everyone in your class. Write code to implement
structure made up of two your solution.
parts, a table (or array) 3 Identify three possible applications for hashing algorithms.
of data, and a key, which
identifies the location of the 4 What are the main features of a good hashing algorithm?
data within the table. 5 What can you do to minimise the likelihood of collisions when creating
• A hashing algorithm is carried a hash table?
out on the key, which then 6 What is load factor?
acts as an index to the specific 7 What is clustering and how is it caused?
location of that data item
within the array. 8 Explain in detail how a hashing algorithm can deal with collisions.
• Hashing algorithms must 9 What is a dictionary data structure and how does it differ from a
create a range of keys hash table?
sufficient to assign unique 10 What are the main actions that you might want to carry out on data
values to each item of data. stored in a dictionary?
• Collisions occur when the
hashing algorithm generates
the same key from two
different items of data. STUDY / RESEARCH TASKS 83
• Chaining or rehashing must
1 How does private/public key encryption use hashing algorithms to
be carried out in the event of a
encrypt data?
collision.
• A dictionary is an abstract data 2 How do hashing algorithms written for encryption vary from those
type that maps keys to data. written for indexing databases?
• Dictionaries and hash tables 3 Is it possible to write a perfect hashing function?
are similar data structures. 4 Research ‘Google Sparse Hash’.
 11 Vectors

A level only
SPECIFICATION COVERAGE
3.2.8 Vectors

LEARNING OBJECTIVES
In this chapter you will learn:
• what vectors are used for
• how to represent vectors as arrays, dictionaries and lists
• how to represent vectors as functions
• how to represent vectors as arrows. How to combine vectors using
addition, multiplication and convex combination
• how to apply vectors.

INTRODUCTION
Vectors can be represented and applied in various ways both
mathematically and geometrically. They are used in different ways in
computing, for example:
• as a data structure
• as a method for mapping one value to another
• as a method of defining geometric shapes.
In this chapter we will look at all three interpretations of vectors.

● Representing vectors as a data structure

When programming, vectors can be implemented as values stored in a
list. For example, the first six values of the Fibonacci sequence could be
84 represented as:
fibonacci[0] = 0; fibonacci[1] = 1; fibonacci[2] = 1;
fibonacci[3] = 2; fibonacci[4] = 3; fibonacci[5] = 5;
This representation could also be described
as a one-dimensional array where each Index 0 1 2 3 4 5
item of data is an element in the array, Data 0 1 1 2 3 5
which can be accessed by its location:
A dictionary is a data structure that maps a key to a value. As we have seen,
we can create sets of real numbers that can then be applied over the vectors.
 The dictionary structure allows us to call an index, which is then used as a
look-up to the real values.

REPRESENTING VECTORS AS ARROWS

{0: Value 1, 1: Value 2, 2: Value 3, 3: Value 4...}
The start of the Fibonacci sequence vector could be represented in a
dictionary as:
{0:0, 1:1, 2:1, 3:2, 4:3, 5:5}

● Representing vectors as a function

A function is a mathematical construct that maps an input to an output. For
example, the function f(x) = x2, simply maps the value of x to its square. A
vector can be used to represent a function. For example:
F = the function to create the vector
S = the complete set of values that the function can be applied to
R = the potential outputs of the function.
Therefore F: S → R
Note that all of the output values must be drawn from R, which is being
treated as a single field from which the function takes its values.

● Representing vectors as arrows

Geometrically, vectors can be represented as arrows as shown in Figure 11.1.

KEYWORDS Figure 11.1 A vector represented as an arrow with magnitude and direction

Magnitude: one of the two The two dimensions of size (or magnitude) and direction are shown. The
components of a vector – refers direction of the arrow is shown by the arrow head and v represents the size.
to its size. The start of the arrow is called the tail and the top of the arrow, the head. To
Direction: one of the two quantify the size and direction of the arrow, think of it plotted on x and y axes:
components of a vector.
Components: the values within 3
a vector.
2

1
0 1 2 3 4 85
Figure 11.2 A vector visualised as an arrow with a measurement

The arrow can be represented as a vector A in the format A = (x,y). x and

y are called the components of the vector and in this case would be the
distance from (0, 0) on an x and y axis. Therefore, this vector is described
4
((
as A = (4, 3) often shown in the format A = 3 to differentiate them from a
coordinate pair used to plot points on a graph.
 Already, you can see how useful vectors can be. With reference to vector
graphics for example, it would now be possible to resize an image simply
by changing the component values in the vector.

Scale 2 Scale 3 Scale 4

Figure 11.3 The effect of scaling a vector

Three-dimensional objects can be represented using the same method with

the addition of a further component, the z axis.
z

z-coordinate
y
x-coordinate

y-coordinate
x
Figure 11.4 A visualisation of a vector in three dimensions

In this example, the vector could be represented as A = (x, y, z).

● Vector addition
It is possible to add vectors together, which has the effect of translating or
displacing the vector. Geometrically, this could be visualised as joining the
tail of one to the head of another.

a
11 Vectors

H
a+b

Figure 11.5 Adding vectors

86 Notice that a new point H has been created which may be used as the head
of a new vector.
The sum of two vectors A and B can be represented as follows:
A = (A1, A2, A3)
B = (B1, B2, B3)
A + B = (A1 + B1, A2 + B2, A3 + B3)
Note that the two vectors must have the same dimension, which in this
case is three components. For example, if:
A = (2, 3, 4) and B = (3, 5, 10) then A + B = (5, 8, 14)
 ● Scalar–vector multiplication

SCALAR–VECTOR MULTIPLICATION
It is also possible to multiply vectors by a number, which has the effect
KEYWORD of scaling. The number is called a scalar as it represents the amount
Scalar: a real value used to by which you want change the scale of the vector. An analogy would be
multiply a vector to scale the changing the scale of a map. If you zoom in you are changing the scale. In
vector. the case of a vector if you scale it by a factor of two, it will have twice the
magnitude. The direction however, will not change as a result of scaling.
You can envisage this geometrically as shown in Figure 11.6.

Figure 11.6 Scaling a vector

The original vector A = (3, 2). Multiply this by the scalar 2 results in vector
B = (6, 4). Notice that the tail position and direction do not change.
Dot product
Dot product is the process of combining two vectors to calculate a single
KEYWORD number. It is calculated in the following format:
Dot product: multiplying two
vectors together to produce a A . B = A xBx + AyBy
number. Ax
A

B
Ay

By

Bx

Figure 11.7 The dot product of two vectors

In this example, A = (3, 5) and B = (7, 2)

Therefore the dot product is 3 × 7 + 5 × 2 = 31
This would also work in three dimensions by including z in the
components. For example, two vectors with the coordinates A = (5, 3, 2)
and B = (2, 7, 4) would result in a dot product of:
5 × 2 + 3 × 7 + 2 × 4 = 10 + 21 + 8 = 39

Convex combinations a×b=c

When two vectors are combined to create a 87
third, a relationship exists between the three
KEYWORDS vectors. In Figure 11.8 you can see that the
Convex combination: a method new vector c has been created at right angles
b
of multiplying vectors that to the other vectors.
produces a resulting vector
within the convex hull. When these combinations are created,
Vector space: a collection of
they have to be done according to certain
elements that can be formed by mathematical principles. For example, a a
adding or multiplying vectors convex combination of vectors is one where
together. the new vector must be within the vector Figure 11.8 Combination of
space of the two vectors from which it is made. vectors
 This could be visualised as follows shown in Figure 11.9.
C E
D
B

A
Figure 11.9 Convex combination of vectors

Vector AD is created by combining vectors AC and AB. Notice an imaginary

line between points B and C. The new vector must fall within the vector
KEYWORD space defined by the points A, B and C in the diagram. This is a visual
Convex hull: a spatial representation of what is called a convex hull that represents all of the
representation of the vector points that make up the vector space. Notice point E, which represents the
space between two vectors. head for another vector. This falls outside the convex hull and is therefore
not a convex combination.
Mathematically, to perform a convex combination, you will be multiplying
one vector either by a scalar, or by another vector. This could be
represented as:
D = AB + AC
where AB and AC are the two vectors
and represent the real number that each vector will be multiplied by.
and must both be greater than or equal to 0 and + must equal 1. D
will then fall within the vector space.

Uses of dot product

Given two vectors u and v, it is possible to generate parity using the bitwise
AND and XOR operations.
For example, where u = [1, 1, 1, 1] and v = [1, 0, 1, 1], the dot product
would be u.v = 1. This is calculated by performing arithmetic over GF(2)
where GF has two elements 0 and 1. This calculation works out the parity
bit for even parity. The first vector will always be [1, 1, 1, 1] and in this
example the second vector is [1, 0, 1, 1]. As you can see, we would expect
the parity bit to be a 1 as the vector v currently has an odd number of 1s.
11 Vectors

The calculation would work as follows:

u.v = [1, 1, 1, 1].[1, 0, 1, 1]
= 1 AND 1 XOR 1 AND 0 XOR 1 AND 1 XOR 1 AND 1
= 1 XOR 0 XOR 1 XOR 1
88
=1
× 0 1
Arithmetic over GF(2) can be summarised in two small 0 0 0
tables. Multiplication can be achieved by bitwise AND 1 0 1
operation:
+ 0 1
Addition can be achieved by bitwise XOR operation: 0 0 1
Subtraction is identical to addition, –1 = 1 and –0 = 0. 1 1 0

Practice questions can be found at the end of the section on page 90.
 SCALAR–VECTOR MULTIPLICATION
TASKS
1 Show how a simple vector could be represented as:
a) a list
b) a function
c) an arrow.
2 Explain how a dictionary data structure can be used to represent a
vector.
3 Use an example to show how you can add two vectors together and
what effect this has on the vector.
4 Use an example to show how you can multiply a vector by a scalar and
what effect this has on the vector.

KEY POINTS 5 Use an example to show the dot product of two vectors.
• Vectors can be represented 6 What is a convex combination of vectors?
as a list of numbers, as a
function and as a geometric
point in space.
• Vectors can be created as STUDY / RESEARCH TASKS
a one-dimensional array or 1 Research how vectors are used to create computer games.
dictionary.
2 Explain how the length of a vector (envisaged as an arrow) is
• Vectors can be combined
determined from its coordinates.
using addition, multiplication
and convex combination. 3 Write code to perform:
• Addition of vectors has a) vector addition
the effect of translation or b) multiplication of a vector by a scalar
displacement. c) dot product calculation.
• Multiplication of vectors by 4 Research other methods of combining vectors including conical
a scalar has the effect of combination and affine combination.
scaling. 5 Vector space has a number of axioms. Look into these and explain why
• Dot product can be used to they are essential in defining vector space. For example, associativity
generate parity. of addition, distributivity of scalar multiplication.

89
 Section Two: Practice questions
1 The following data needs to be stored and accessed:
C, D, B, A, F, G
a) Describe how this data would be added to and then removed from a stack.
b) Describe how this data would be added to and then removed from a queue.
c) Show how these data items would be added to a binary search tree.
d) Assuming the data has been added to a binary search tree, write out the sequence of values that would be
output from the tree following:
i) post-order traversal
ii) pre-order traversal
iii) in-order traversal.
2 The following adjacency list represents a graph.

Node Adjacent nodes

A B, 20, C, 30, D, 10
B A, 20, D, 20
C A, 30, D, 30
D A, 10, B, 20, C, 30

a) Draw the graph.

b) Create an adjacency matrix for the graph.
c) Explain why this graph is not a tree.
3 Vector A is stored in an array A = {4, 5} and vector B is stored in an array B = {6, 12}.
a) What is an array?
b) What is a vector?
Section Two: Practice Questions

c) Calculate the result of adding the two vectors together, showing your working.
d) Calculate the dot product of these two vectors, showing your working.
4 Look at the following section of code that generates a hash value and then answer the questions.
Dim FindRecord As String
Dim FindDay As Integer
Dim FindMonth As Integer
Dim HashKey As Integer
FindRecord = [Link]
FindDay = Val(Mid(FindRecord, 1, 2))

90 FindMonth = Val(Mid(findRecord, 4, 2))

HashKey = (28 * (FindMonth - 1) + FindDay) Mod 100
a) What is the purpose of a hash value?
b) Explain whether or not you think that this is an effective algorithm, justifying your view.
c) Suggest an alternative hashing algorithm for generating the hash value.
Section Three:
Fundamentals of
algorithms
 12 Graph and tree
traversal
A level only
SPECIFICATION COVERAGE
3.3.1 Graph traversal
3.3.2 Tree traversal

LEARNING OBJECTIVES
In this chapter you will:
• consolidate your learning on graphs and trees
• learn how to implement and traverse a graph breadth first
and depth first
• learn how to implement and traverse a binary tree pre-order,
in-order and post-order
• learn how to apply stacks and queues and use recursion.

INTRODUCTION
In Chapter 9 we looked at the graph and tree data types and how they
can be used. In this chapter you will learn how to implement and
traverse the structures. The word ‘traversing’ means ‘to move across’
and that is what you do when you traverse a graph or a tree – you move
across it, visiting nodes as you go.

● Implementing a graph
As we saw in Chapter 9, graphs can be implemented using adjacency
lists or matrices, which represent every vertex (node) and the edges (or
connections) between the vertices.
92
Node Adjacent nodes A B
A B
E
B A, C, E
C B, D
D C, E C
D
E B, D
Figure 12.1 Adjacency list and
corresponding graph
 One possible implementation is to store this in an array showing each
KEYWORDS
vertex and whether there is an edge between vertices. For example, the

TRAVERSING A GRAPH
Implementation: creating code to graph above could be represented by the following two-dimensional array:
produce a programmed solution.
Array: a set of data items of the Table 12.1 A two-dimensional array representing a graph
same type grouped together with A B C D E
the same identifier.
A 0 1 0 0 0
Edge: a connection between
two nodes in a graph or tree B 1 0 1 0 1
structure. C 0 1 0 1 0
Graph: a data type made up of D 0 0 1 0 1
nodes and edges. E 0 1 0 1 0

A 1 represents an edge between the two vertices and a 0 means there

is no edge. This approach can be used to represent any unweighted,
undirected graph.

● Traversing a graph
There are two ways of traversing the graph: depth first or breadth first.
KEYWORDS ● Depth first is a method that explores as far into a graph as possible
Depth first: a method for before backtracking to visit unvisited nodes. It is often implemented
traversing a graph that starts
using a recursive algorithm, which is explained later in the chapter.
at a chosen node and explores
● Breadth first is a method for traversing a graph that visits the nodes
as far as possible along each
branch away from the starting closest to a starting point first. A queue is used to keep track of the
node before backtracking. nodes to visit.
Breadth first: a method for Using the graph in Figure 12.1 as an example, depth first works as follows:
traversing a graph that explores
nodes closest to the starting Table 12.2 Depth first traversal
node first before progressively
Explanation Current node Visited nodes
exploring nodes that are further
away. Select the node to start from (A). A
Queue: a data structure where Mark node A as visited. Choose a node that A A
the first item added is the first is connected to A (B) and recursively call the
item removed. search routine to explore from this node.
Node: an element of a graph Mark node B as visited. Choose a node that is B AB
or tree. connected to B and has not been visited (C) and
recursively call the search routine to explore
from this node.
Mark node C as visited. Choose a node that C ABC
is connected to C and has not been visited
(D) and recursively call the search routine to
explore from this node.
93
Mark node D as visited. Choose a node that is D ABCD
connected to D and has not been visited (E) and
recursively call the search routine to explore
from this node.
Mark node E as visited. All nodes connected E ABCDE
to E have already been visited, so unwind
recursion. There are no nodes left to visit
during this unwinding, so the algorithm will
terminate.
 Using the graph in Figure 12.2 as an example, breadth first works by
A B visiting the starting node and then all of the nodes attached to it in order. It
then moves to the next closest nodes to repeat the process as follows:
E
Table 12.3 Breadth first traversal

C Explanation Contents of queue

D
Add the node to start exploring from (A) to the queue. A
Add all nodes that are adjacent to node at front of queue AB
Figure 12.2 Adjacency list and
(A) and not already full explored to queue (B).
corresponding graph
Remove A from queue as fully explored. B
Add all nodes that are adjacent to B and not already fully BCE
explored to queue (C, E).
Remove B from queue as fully explored. CE
Add all nodes that are adjacent to C and not already fully CED
explored to queue (D).
Remove C from queue as fully explored. ED
Add all nodes that are adjacent to E and not already fully ED
explored to queue (none).
Remove E from queue as fully explored. E
Add all nodes that are adjacent to D and not already fully D
explored to queue (none).
Remove D from queue as fully explored. Queue empty so
algorithm terminates.

The following code shows a Visual Basic implementation of a grid with

eight nodes. The code uses a CSV file to read in the adjacencies. Two
procedures have been created to traverse the tree depth first and breadth
first. The code is commented to explain how each subroutine works:
Public Class frmGraph
12 Graph and tree traversal

Public RouteMatrix(8, 8) As Boolean

Public NodeMatrix(8) As String
Public VisitedMatrix(8) As Boolean
Public NodeCount As Integer
Public DataRow As String
Public ThisNode As Integer
Private Sub frmGraph_Load(ByVal sender As System.
Object, ByVal e As [Link]) Handles MyBase.
Load
94 ‘ count nodes
NodeCount = 8
‘ populate arrays
FileOpen(1, "C:\[Link]", [Link])
DataRow = LineInput(1)
For Loop1 = 1 To NodeCount
[Link]()
 Input(1, DataRow)

TRAVERSING A GRAPH
NodeMatrix(Loop1) = DataRow
VisitedMatrix(Loop1) = False
[Link](Loop1 - 1).[Link] =
DataRow
For Loop2 = 1 To NodeCount
Input(1, DataRow)
RouteMatrix(Loop1, Loop2) = DataRow
[Link](Loop1 - 1).Cells(Loop2 - 1).
Value = DataRow
Next
Next
End Sub
Private Sub btnDepthFirst_Click(ByVal sender
As [Link], ByVal e As [Link])
Handles [Link]
[Link](VisitedMatrix, 0, VisitedMatrix.
Length)
[Link] = ""
‘ start with node ‘A’
Depth(1)
End Sub
Private Sub Depth(ByVal ThisNode)
[Link] = [Link] &
NodeMatrix(ThisNode) & vbCrLf
VisitedMatrix(ThisNode) = True
‘ Look at each node, check for route
For Loop1 = 1 To NodeCount
‘ check for route
If RouteMatrix(ThisNode, Loop1) = True Then
‘check node is unvisited
If VisitedMatrix(Loop1) = False Then
95
Depth(Loop1)
End If
End If
Next
End Sub
 Private Sub btnBreadth_Click(ByVal sender As
[Link], ByVal e As [Link]) Handles
[Link]
‘ reset visited array
[Link](VisitedMatrix, 0, VisitedMatrix.
Length)
[Link] = ""
‘ initialize
Dim Queue(30) As Integer
Dim QueueHead As Integer
Dim QueueNext As Integer
QueueHead = 1
QueueNext = 1
ThisNode = 1
Queue(QueueNext) = ThisNode
VisitedMatrix(1) = True
QueueNext = QueueNext + 1
Do
‘ take next item in queue
ThisNode = Queue(QueueHead)
QueueHead = QueueHead + 1
[Link] = [Link] &
NodeMatrix(ThisNode) & vbCrLf
12 Graph and tree traversal

For Loop1 = 1 To NodeCount

‘ is node connected?
If RouteMatrix(ThisNode, Loop1) = True Then
‘ has node been visited
If VisitedMatrix(Loop1) = False Then
‘ add node reference to queue
VisitedMatrix(Loop1) = True
Queue(QueueNext) = Loop1
96 QueueNext = QueueNext + 1
End If
End If
Next
Loop Until QueueHead = QueueNext
End Sub
End Class
 ● Traversing a binary tree

TRAVERSING A BINARY TREE

Implementing a binary tree was explained in Chapter 9. In this section,
KEYWORDS
you will learn how to traverse a tree. The process of traversing a binary
Binary tree: a structure where tree extracts all the data from the tree in some sort of order. There are three
each node can only have up to
ways of traversing a binary tree – pre-order, in-order and post-order.
two child nodes attached to it.
Pre-order: a method of To traverse a binary tree you start at the root node and move left, right or
traversing a tree by visiting the visit depending on the type of traversal you are using. Moving left or
root, traversing the left subtree right entails ‘looking’ to see if there is a node in that direction and moving
and traversing the right subtree. if there is. Visit entails extracting the data at that node.
In-order: a method of traversing John
Traversing the binary tree in Figure 12.2 gives the
a tree by traversing the left
following results: Helen Kim
subtree, visiting the root and
traversing the right subtree. Table 12.4 Binary tree traversals Figure 12.2
Post-order: a method of Pre-order Visit, Left, Right John, Helen, Kim
traversing a tree by traversing
In-order Left, Visit, Right Helen, John, Kim
the left subtree, traversing the
right subtree and then visiting Post-order Left, Right, Visit Helen, Kim, John
the root.
Traversal: the process of
Note that pre/in/post tells you when you do the visit stage.
reading data from a tree or This algorithm written in pseudo-code carries out an in-order traversal:
graph by visiting all of the nodes.
Set current node as root
Traverse
End
Define Procedure Traverse
If there is a node to the left then
Move left to child node
Traverse
End If
Visit
If there is a node to the right then
Move right to child node
Traverse
End If Colin

End Procedure Bert

Here is how this algorithm traverses the Alison Cedric

binary tree in Figure 12.3. Figure 12.3 97

1 The root node is set as the current node

(“Colin”).
2 The procedure Traverse is called for the first time.
3 There is a node to the left of the current node so move to the node to
the left so that we are now on the node containing “Bert”.
4 The procedure Traverse is called for the second time. The details of
the first call of Traverse are pushed on to the stack.
5 There is a node (“Alison”) to the left of “Bert” so move left. Current node
 6 Traverse is called again. This time there is nothing to the left of the
current node.
7 Visit the node – the term ‘visit’ is deliberately vague. It might mean
‘print it out’ or it might mean ‘enter the person’s date of birth’ or any
other process you want to carry out on each node.
8 Now we need to check if there is a node to the right of “Alison” but
there is not, so move back up the branch to “Bert”.
9 This call of Traverse has now been completed so the details of the
previous call can be popped off the stack.
10 We jumped out of the second call of Traverse after the first question
so we now visit the node “Bert”.
11 Now we look to the right of “Bert”. There is a node there (“Cedric”) so
we go to that node.
12 Traverse is called again so the details of the previous call of
Traverse are placed on the stack.
13 Now we are at “Cedric” we look left, then visit then look right.
14 This call is now finished so back up the branch to “Bert”.
15 We have now finished the call to “Bert” so that call of Traverse is
also complete, so it’s back up to “Colin”.
16 Visit “Colin”.
17 Try to go right, but there is nothing to go to.
18 Finish the first call to Traverse.
If you have followed this process through you should find that you have
visited the nodes in alphabetical order – Alison, Bert, Cedric and finally Colin.
This looks and sounds like a very complex process, but in fact it is a very
elegant solution to the problem. You must remember that although we have
only traversed a tree with four nodes, the process would be exactly the
same for a tree with 400 nodes. The only limitation is the number of calls
of Traverse that the stack can handle.
12 Graph and tree traversal

Traversing a binary tree in pre-order follows the same routine but in this
case you visit the root node as soon as you get to it. Traversing the tree given
above in pre-order would result in Colin, Bert, Alison and Cedric. The only
detail you would need to make the code carry out a pre-order traversal would
be to move the visit to before the first If statement like this.
‘Pre order traversal
Visit
If there is a node to the left then
Move left to child node
Traverse
98
End If
If there is a node to the right then
Move right to child node
Traverse
End If
A post-order traversal would result in the list Alison, Cedric, Bert and
Colin. In this case you visit the node after you have tried to go both left and
right from the node.
 An interesting feature of all this is that no matter how you set out the four
nodes, an in-order traversal will always produce a sorted list, but pre-order

RECURSION
and post-order produce a different set of data if the data are rearranged.
Typical uses of each traversal are:
● Pre-order: This can be used with expression trees to evaluate the expression

using prefix notation. Evaluating an expression simply means that values

are to be placed into the expression to produce a result. Prefix means that
KEYWORD
the operators in the expression are evaluated before the values.
Binary search: a technique ● In-order: This is the equivalent of a binary search of the tree, which is
for searching data that works
by splitting datasets in half
explained in more detail in the next chapter.
● Post-order: This will produce Reverse Polish Notation (RPN) and this is
repeatedly until the search data
is found. covered in detail in Chapter 18. A post-order algorithm can also be used
to empty the contents of a tree.

● Recursion
Recursion is the process of calling a function from within itself. The
KEYWORD concept is very elegant, but trying to understand how it works is rather
Recursion: a technique where a more difficult. The algorithm described above that traverses a binary tree
function can call itself in order uses recursion. Each time a call is made the current state of the procedure
to complete a task. must be stored on the stack.
The process to traverse a binary tree in order goes like this:
Define Procedure Traverse
If there is a node to the left Then
Go Left
Traverse
End If
Visit
If there is a node to the Right Then
Go Right
Traverse
End If
End Procedure
After the procedure Traverse has been called for the first time the
program will check to see if there is a node to the left. If there is it goes left
then calls the procedure Traverse. This means that Traverse has been
called from inside the procedure Traverse, and if the next node also has
99
a node to its left then Traverse will be called from inside itself again.
Recursion has a base case and general cases. The base case is also known as
the terminating case and defines the point at which the recursive function
will stop calling itself. In the example above, the terminating case is when
there are no more nodes left to visit in the tree. The general cases are all of
the inputs which require the function to call itself. In the example above,
Traverse will continue to call itself if there is a node either on the right
or the left of the current node.
Practice questions can be found at the end of the section on page 132.
 TASKS
1 Draw a binary tree for the following data: Rose, Jasmine, George,
Naomi, Trevor and Stanley.
a) List the nodes that will be visited in order to find the node that
stores George.
b) Traverse the tree in pre-order and write down the value at each
node when you visit it.
c) Repeat this process for a post-order traversal.
d) Repeat this process for an in-order traversal.
2 Explain the term recursion and give an example where it might be used.
3 Write pseudo-code to show how the following graph could be
traversed: depth first and breadth first.

A B

KEY POINTS
• Graphs can be represented
using an adjacency list or
matrix.
STUDY / RESEARCH TASKS
• Traversal is the process of
visiting the vertices (nodes) in 1 Write pseudo-code to traverse a binary tree for the following data:
different orders to generate Rose, Jasmine, George, Naomi, Trevor and Stanley.
different results. a) List the nodes that will be visited in order to find the node that
• Graphs can be traversed stores George.
depth first or breadth first. b) Traverse the tree in pre-order and write down the value at each
node when you visit it.
12 Graph and tree traversal

• Breadth first traversal finds

the shortest path between c) Repeat this process for a post-order traversal.
vertices on unweighted d) Repeat this process for an in-order traversal.
graphs. 2 Write code to implement and traverse the following graph.
• Binary trees can be traversed
in-order, post-order to pre- A B
order, to create different
E
outputs.
• Post-order traversal of a
binary tree can be used C
to create Reverse Polish D
Notation.
• Recursion is where a function 3 Turn your pseudo-code from question 1 above into an application
100
calls itself. using a high-level language of your choice.
13 Dijkstra’s shortest
path algorithm
A level only
SPECIFICATION COVERAGE
3.3.6 Optimisation algorithms

LEARNING OBJECTIVES
In this chapter you will:
• consolidate your learning about graphs
• learn what Dijkstra’s shortest path algorithm is and how it can be
applied
• learn how to trace Dijkstra’s shortest path algorithm
• learn how to implement Dijkstra’s shortest path algorithm.

INTRODUCTION
Dijkstra’s shortest path algorithm calculates the shortest distance
between two vertices (nodes) on a graph data type. The algorithm can
be used to find the shortest path from one node to all other nodes in
a graph. It was devised by Dutch computer scientist Edsger Dijkstra
and published in 1959. To understand the algorithm you must have
a good understanding of the graph data type that we looked at in
Chapter 10.

As an example, it can be used to solve problems like working out the

shortest distance between two towns.

30
Town A Town B 60

20 20 Town E 101

30
Town C 30
Town D

Figure 13.1 Graph to show journey time between towns

Consider the problem we looked at in Chapter 10 of working out the

shortest distance between Town A and Town E. On a simple graph like this
we could simply use trial and error to find the result. For example:
 Possible routes Distance Total distance
A to B to E 30 + 60 90
A to C to B to E 20 + 20 + 60 100
A to C to D to E 20 + 30 + 30 80
A to B to C to D to E 30 + 20 + 30 + 30 110

The table shows all of the possible routes that we could take that do not
involve circuits, and also shows the shortest path, which is to go from A to
C to D and then to E.
As a quick reminder, graphs are made up of vertices (or nodes) and edges,
which are the connections between them. Some vertices are not connected
and therefore have no path between them. It is also possible to have
weighted graphs as with the example above, where there is a value attached
to each edge.
KEYWORD Dijkstra’s algorithm works by working out the shortest path between a
Single source: in Dijkstra’s single source (the starting vertex) and every other vertex. As a result
algorithm it means that the it also produces the shortest path between the starting vertex and a
shortest path is calculated from destination vertex, as in the example above. It only works on weighted
a single starting point. graphs with positive values on the edges.
Below are examples of some of the common applications that will require a
shortest path algorithm. Dijkstra’s algorithm is likely to be the basis of all of
these.
● Geographic information systems (GIS) such as satellite navigation

systems and mapping software where the vertices are geographical

locations and the edges show distance or drive-time.
13 Dijkstra’s shortest path algorithm

● Telephone and computer network planning where the vertices are the

individual devices on the network and the edges could either be physical
distance or a measurement of network capability, such as bandwidth.
● Network routing/packet switching: where the vertices are network

devices and the edges are the connections between them. The algorithm
can be used to send data packets along the most efficient route. In fact
there is a routing protocol for TCP/IP networks called OSPF, which
stands for open shortest path first.
● Logistics and scheduling: wherever there is a large network of vehicles,

for example, delivery vehicles, buses or aeroplanes the algorithm can be

used to calculate the optimum routes.

102

Figure 13.2 A graph with multiple vertices and edges

Figure 13.2 is a visualisation of the problem above showing any number of

vertices and edges. As you can see, you could have a very large number of
possible paths, making the trial and error system impractical.
 ● Tracing Dijkstra’s algorithm

TRACING DIJKSTRA’S ALGORITHM

The algorithm works as follows using Figure 13.3 as an example and
KEYWORD assumes that we are looking for the shortest path between vertex A and G
Shortest path: the shortest rather than the shortest path from A to every node.
distance between two vertices
based on the weighting of the 1 Start from the first vertex (in this case A).
edges. 2 Work out the weight (also known as the cost) for each edge between that
vertex and other connected vertices, e.g. A to B is 2 and A to C is 5.
3 Move on to the next nearest vertex and repeat the process. In this case it
would be B. This time you need to add the two weights together to get a
total weight between two points. For example:
● A to B to C would be 6.
● A to B to F would be 9.

4 We now have two options for getting from A to C:

● We could go from A to C direct with a weight of 5.
● We could go from A to B to C with a weight of 6.

5 As we are finding the shortest path, we now know that the quickest
route from A to C is to go direct from A to C. We need to retain this
information and ignore other routes that are longer.
6 Now repeat the process until all vertices have been visited and you get
to the destination vertex, which in this case is G.

2 7
A B F
2

5 4 G
4

4
C 6
D 3 E

Figure 13.3 A map for tracing Dijkstra’s algorithm

The calculations become a little more complicated as you need to keep an

accumulated total of the weights between all sets of connected vertices, and
then choose the shortest one. Table 13.1 traces each stage of the algorithm and
we will work through the table a step at a time.
Table 13.1

Step Vertex A B C D E F G
1 A 0A 2A 5A ∞A ∞A ∞A ∞A
2 B 0A 2A 5A ∞B ∞B 9B ∞B
3 C 0A 2A 5A 11C ∞C 9B ∞C
103
4 F 0A 2A 5A 11C ∞F 9B 11F
5 0A 2A 5A 11C ∞F 9B 11F
 Step 1
● Place A in the first column and complete the distance between it and the

other vertices.
● Notice that A to A is shown as 0. A to B is 2, A to C is 5. These are all

shown with the subscript A to show clearly which vertex is being used.
This becomes important later on.
● Notice that where there is no edge, the value is shown as infinite.
● We have now finished with the vertex A as there are no other edges.

Step 2
● Now move onto the next nearest vertex to A, which is B as it has the
lowest value in the row above. Notice that the same value is placed in the
table for B as in the row above. This is because we already know that this
is the shortest path from A to B. In this case it is 2.
● The subscript A shows us clearly that the shortest path came from vertex A.
● The next path is B to C. This would be 4. However, we need to add on

the 2, which is the shortest path that it took to get from A to B in the first
place. This would give us a result of 6. However, this is higher than the
path we already have between A and C, so we do not include it. Instead
we keep the 5 from the row above. In other words, going from A to C
direct is a shorter path than going from A to B to C.
● As you move through the rows you always keep the lowest value from the

row above as this is the shortest path to that point.

Step 3
● Now move onto the next nearest vertex to B, which is C.
● Notice we can complete the table for the vertices that we have already

visited and finished with in red. This makes it clear that the vertices have
13 Dijkstra’s shortest path algorithm

been dealt with and that we do not need to calculate them again.
● The next edge is between C and D. It has a weight of 6, but we have to add

the shortest weight that it took to get to C in the first place, which you can
see from the row above is 5. Therefore we put 11 in the table for the distance
from C to D with a subscript C to show which vertex we came from.
● C is not connected to any other vertex that has not already been

explored, so a standard way of showing this is to put the infinity sign in

the table against the other vertices.
● Notice that we had a connection between A and F (via B) of only 9, so

this stays in the column. This is because A to B to F is shorter than A to

C to D to F.
Step 4
● Now move on to the next nearest vertex, which is F (with a weight of 9).
● Complete the table in red up to that point as before to show that we have

finished with those vertices.

104 ● Notice that we have been able to skip D and E as we already know that

these will not produce the shortest path as the distance to D is equal to
the shortest distance found to G so far. The algorithm will however have
to calculate these distances first before it can carry out the next step.
● F connects to G in 2, but you have to add on the shortest path to this

point, which is 9 making a total of 11.

 Step 5

IMPLEMENTING DIJKSTRA’S SHORTEST PATH ALGORITHM

● There are no more edges to be compared so this final step simply lists

the final values.
● Reading off the last row of the table you can see that the shortest path

between A and G is 11 and looking at the subscript letters you can see
that the route is A, B, F, G.
You can check this by looking at alternative routes and working out the
total weight. The two other possible paths in this example are:
● A, C, D, E, G with a total weight of 18
● A, C, B, F, G with a total weight of 18.

● Implementing Dijkstra’s shortest path

algorithm
The values for a weighted graph with eight vertices could be represented as
a two-dimensional array as follows:
Table 13.2 A two-dimensional array containing details for a graph

A B C D E F G
A 0 4 3 7 0 0 0
B 4 0 0 1 0 5 0
C 3 0 0 3 5 0 0
D 7 1 3 0 2 2 7
E 0 0 5 2 0 0 2
F 0 5 0 2 0 0 5
G 0 0 0 7 2 5 0

This would produce the following graph:

4
A B

3 7 1 5

3 2
C D F

5 2 7 5

E G
2
Figure 13.4 Graph created from the two-dimensional array in Table 13.2 105

This code reads in the data from an array stored in a csv file. It uses
recursion to visit each node and mark it as visited, recording the shortest
path between each. This means that it is able to produce the shortest path
between any two vertices visited as well as provide a shortest path between
the starting vertex A and the destination vertex G.
 Public MinDist(8) As Integer
Public NodeFixed(8) As Boolean
Public Route(8) As String
Public ThisNode As Integer
Public ThisMin As Integer
Public ThisRoute As String
Public DistToThisNode As Integer
Public NodeCount As Integer
‘ generix ‘load data from file routine’
Private Sub frmGraph_Load(ByVal sender As System.
Object, ByVal e As [Link]) Handles
[Link]
Dim DataRow As String
‘ count nodes
NodeCount = 7
‘ populate arrays
FileOpen(1, "C:\[Link]", OpenMode.
Input)
DataRow = LineInput(1)
For Loop1 = 1 To NodeCount
13 Dijkstra’s shortest path algorithm

[Link]()
[Link]()
[Link](Loop1 - 1).Cells(0).Value =
999
MinDist(Loop1) = 999
Input(1, DataRow)
NodeName(Loop1) = DataRow
[Link](Loop1 - 1).[Link] =
DataRow
[Link](Loop1 - 1).[Link] =
DataRow
For Loop2 = 1 To NodeCount
106
Input(1, DataRow)
RouteMatrix(Loop1, Loop2) = DataRow
[Link](Loop1 - 1).Cells(Loop2 -
1).Value = DataRow
Next
Next
End Sub
Private Sub btnFind_Click(ByVal sender As System.
Object, ByVal e As [Link]) Handles

IMPLEMENTING DIJKSTRA’S SHORTEST PATH ALGORITHM

[Link]
‘ reset tracking table
For Loop1 = 1 To NodeCount
[Link](Loop1 - 1).Cells(0).Value =
999
[Link](Loop1 - 1).Cells(1).Value =
False
Route(Loop1) = "A"
NodeFixed(Loop1) = False
MinDist(Loop1) = 999
Next
‘ start recursive process
MinDist(1) = 0
CurrentNode(1)
End Sub
Private Sub CurrentNode(ByVal ThisNode)
‘ theoretically all distances start as infinity
‘ but infinity is not a concept a computer can
‘ cope with so I have used a value of 999
DistToThisNode = MinDist(ThisNode)
NodeFixed(ThisNode) = True
ThisRoute = "" & Route(ThisNode)
‘ calculate distance using this node
‘ check all the nodes
For Loop1 = 1 To NodeCount
‘ has node been fixed?
If NodeFixed(Loop1) = False Then
‘ is node connected to ThisNode?
If RouteMatrix(ThisNode, Loop1) <> 0 Then
‘ is potential distance shorter? 107

If MinDist(Loop1) > DistToThisNode +

RouteMatrix(ThisNode, Loop1) Then
MinDist(Loop1) = DistToThisNode +
RouteMatrix(ThisNode, Loop1)
Route(Loop1) = ThisRoute &
NodeName(Loop1)
‘ update display
 [Link](Loop1 - 1).Cells(0).
Value = MinDist(Loop1)
[Link](Loop1 - 1).Cells(1).
Value = NodeFixed(Loop1)
[Link](Loop1 - 1).Cells(2).
Value = Route(Loop1)
End If
End If
End If
Next
‘find shortest distance leading to am unfixed node
ThisMin = 999
For Loop1 = 1 To NodeCount
‘ update display to show progress
[Link](Loop1 - 1).Cells(1).Value =
NodeFixed(Loop1)
‘ is node fixed?
If NodeFixed(Loop1) = False Then
‘ is this the shortest unfixed node?
If MinDist(Loop1) < ThisMin Then
13 Dijkstra’s shortest path algorithm

‘ then record which node it leads to

ThisNode = Loop1
ThisMin = MinDist(Loop1)
End If
End If
Next
MsgBox("Current node is " & NodeName(ThisNode) &
vbCrLf & "click to move on", 0, "")
‘ if ThisMin is still 999 then all nodes are fixed
If ThisMin <> 999 Then
CurrentNode(ThisNode)
108 End If
End Sub
End Class
Figure 13.5 is a screenshot from the program that shows the process being
tracked after a vertex has been visited.
 IMPLEMENTING DIJKSTRA’S SHORTEST PATH ALGORITHM
Figure 13.5
Practice questions can be found at the end of the section on page 132.

TASKS
1 Draw the graph that would be produced from the following array.
A B C D E
A 0 3 2 0 0
B 3 0 0 3 0
C 2 4 0 4 2
D 0 3 4 0 4
E 0 0 2 4 0

2 Write the array that would be needed to create the following graph.
4 4
A B E 7
G
2 3
5
KEY POINTS 7 1 5

• Dijkstra’s shortest path C 3 2 F

algorithm calculates the
D
shortest distance between
two vertices (nodes) on a
3 Using this graph, trace Dijkstra’s algorithm to show the shortest path
graph data type.
between A and G.
• Graphs are made up of
vertices (or nodes) and edges,
which are the connections 109
between them. STUDY / RESEARCH TASKS
• Dijkstra’s shortest path 1 Explain why Dijkstra’s shortest path algorithm would not solve ‘the
algorithm only works on travelling salesman problem’.
weighted graphs with positive
values on the edges. 2 What is meant by a greedy algorithm?
• Dijkstra’s shortest 3 Explain the time complexity of Dijkstra’s algorithm using Big O
path algorithm can be notation. (You may need to refer to Chapter 22 for details on Big O
implemented using the values notation.)
of a two-dimensional array. 4 Research the open shortest path first protocol (OSFP).
 14 Search algorithms –
binary, binary tree
and linear search
A level only
SPECIFICATION COVERAGE
3.3.4 Searching algorithms

LEARNING OBJECTIVES
In this chapter you will learn:
• what a linear search is and how it could be implemented
• what a binary search is and how it could be implemented
• what a binary tree search is and how it could be implemented
• to compare the efficiency of the different search methods.

INTRODUCTION
One of the main benefits of using a computer is the ability to search.
Consider how many everyday activities involve searching, for example:

• a cash machine searches for your bank account details to find how
much (or little) money you have left in the account
• the computerised till at your local supermarket searches for the cost
of the goods you are buying
• a search engine on the Internet looks for the cheapest holiday to
the Algarve.
Most searches are carried out on data storage systems, but they are
used in other applications as well, for example, in the find and replace
process on a word processor. A simple search might just look for one
110 keyword, but most search routines allow you to construct more complex
queries using logic statements such as OR, AND and NOT.

There are a number of different searching algorithms that can be used.

Which one you choose depends to a large extent on the data being
searched in terms of its size and complexity. The efficiency of algorithms
is usually represented using Big O notation and there is more on this in
Chapter 22.
 ● Linear search

LINEAR SEARCH
A linear search works by looking at every item or set of data until the
KEYWORD details that you are searching for are found or you fail to find it altogether.
Linear search: a simple search The efficiency of a search can be strongly influenced by the way that the
technique that looks through data is organised. If there is no logical or rational method in the way the
data one item at a time until the data has been stored then the only option is to use a linear search. This is
search term is found. the simplest but also the least efficient method.
You might use a linear search to find a book on a bookshelf – you know it
is there somewhere but unless the books are organised in some way, say by
title or author, then you will have to check every title until you find the one
you want. A search might be coded something like this:
Repeat
Look at the Title
Until Title is the one you want OR there are no more
books

Figure 14.1 Unsorted books

The efficiency of the search also depends on the size of the dataset being
searched and where the search item is within it. The best-case scenario is
that it is near the beginning in which case it could find the result quickly.
However, in the worst-case scenario the search item may be near the end
of the dataset in which case it could take a long time. The speed of the
algorithm therefore is proportionate to the size of the dataset.
Below is a section of commented code from Visual Basic showing a linear
search. It is looking for a text string defined by [Link]. Note that
it also carries out a count to work out how many ‘looks’ it has to do to find
the data:
Private Sub btnSearch_Click(ByVal sender As System.
Object, ByVal e As [Link]) Handles 111
[Link]
Dim CountLinear As Integer = 0
[Link] = ""
[Link] = ""
‘ linear search
Do
CountLinear = CountLinear + 1
 [Link] = [Link] &
CountLinear & "-" & [Link](CountLinear).
Cells(0).Value & vbCrLf
Loop Until CountLinear = RowCount Or grdTable.
Rows(CountLinear).Cells(0).Value = [Link]
[Link] = CountLinear
‘ match found?
If [Link](CountLinear).Cells(0).Value =
[Link] Then
[Link] = "Match Found"
Else
[Link] = "No Match Found"
End If
End Sub
End Class
14 Search algorithms – binary, binary tree and linear search

● Binary search
If the data you want to look through is in some sort of logical order then
KEYWORD you might be able to use a technique called a binary search. This method
Binary search: a technique works in the same way as the children’s game where someone thinks of a
for searching data that works number between say 1 and 100 and you have to guess what it is by being
by splitting datasets in half
told if your guesses are higher or lower than the number.
repeatedly until the search data
is found. A logical person would start with 50, because they could then discount
half of the numbers straight away. Guessing half way into the middle of
the remaining numbers (either 25 or 75) will allow half of the remaining
numbers to be discarded and so on. Each time you make a guess you halve
the number of options that are left to you, and you alter the range within
which the answer must be.
These 15 cells contain 15 numbers arranged in ascending order:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Figure 14.2

Use this method to find the number 51 which is contained in one of these
112 cells. Start in the middle – block 8.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x x x x x x x 37

Figure 14.3

Block 8 contains the number 37, so blocks 1 to 8 can now be discarded.

Half way between 9 and 15 is 12 so look there next.
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

BINARY SEARCH
x x x x x x x 37 57 x x x

Figure 14.4

Block 12 contains the number 57 so blocks 12 to 15 can be discarded. Half

way between blocks 9 and 11 is block 10 so look there.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x x x x x x x 37 51 57 x x x

Figure 14.5

Block 10 contains the number we are looking for. This has taken three
‘looks’ to find the missing number.
This pseudo-code shows how you might set out the process in a program.
In this case the record number that needs to be found is stored in a variable
called FindMe.
FindMe stores the record title that we are searching
for
LowestPointer 1
HighestPointer NumberofRecords
Do
MiddlePointer (LowestPointer + HighestPointer) / 2
If Record at MiddlePointer < FindMe Then
LowestPointer MiddlePointer + 1
End If
If Record at MiddlePointer > FindMe Then
HighestPointer MiddlePointer - 1
End If
Until Record at MiddlePointer = FindMe OR
LowestPointer = HighestPointer
The pointers LowestPointer and HighestPointer point to the first
and last locations in the file where the record you are looking for might be
located. The pointer MiddlePointer stores the number roughly half way
between the two extremes. 113
At first this seems like a very slow system, but in fact it is very efficient. If
you want to search through just three records it will take a maximum of
two ‘looks’ before you find a match and with seven records you will need
three ‘looks’ and so on. If you have one million records you would need
to take a maximum of just 20 ‘looks’, and it would take a maximum of 33
looks to find one person in the world which currently has a population of
over six billion.
 Below is a section of commented code from Visual Basic showing a binary
search. It is looking for a text string defined by [Link]. Note that
it also carries out a count to work out how many ‘looks’ it has to do to find
the data.
Private Sub btnSearch_Click(ByVal sender As
[Link], ByVal e As [Link])
Handles [Link]
Dim MinNode As Integer = 0
Dim MaxNode As Integer = RowCount
Dim LookNode As Integer
Dim LastNode As Integer
Dim CountBinary As Integer = 0
[Link] = ""
[Link] = ""
‘ binary search
14 Search algorithms – binary, binary tree and linear search

Do
CountBinary = CountBinary + 1
LastNode = LookNode
‘ calculate midpoint of remaining nodes
LookNode = Int(MinNode + MaxNode) / 2
‘ determine which half of remaining nodes to
discard
If [Link](LookNode).Cells(0).Value >
[Link] Then
MaxNode = LookNode
Else
MinNode = LookNode
End If
[Link] = [Link]
& LookNode & "-" & [Link](LookNode).
Cells(0).Value & vbCrLf
Loop Until [Link](LookNode).Cells(0).Value
= [Link] Or LastNode = LookNode
114
[Link] = CountBinary
 ● Binary tree search

BINARY TREE SEARCH

Binary trees are often used in programs where data is very dynamic, which
means that data is constantly entering and leaving the tree. Where a binary
tree has been used the process of searching it is similar to the binary search
method described above except that rather than looking through a list
of data items, it must traverse the tree and look at the data item stored at
each node. In this routine the variable FindMe contains the name we are
looking for within the data stored in the tree and you will remember that
the ‘Root node’ is the node the tree is built from.
CurrentNode RootNode
Repeat
If Current_Node > Find_Me then
Move left to child node
Else
Move right to child node
End If
Until CurrentNode equals FindMe Or

KEYWORD CurrentNode has no children

Binary tree search: a technique The following section of commented code shows how the binary tree
for searching a binary tree that search is carried out. [Link] is the name of the variable
traverses the tree until the that will hold the text strings being searched for.
search term is found.
Private Sub txtSearchFor_KeyDown(ByVal sender As
Object, ByVal e As [Link])
Handles [Link]
‘ check for enter key press
If [Link] = [Link] Then
Dim ThisNode As Integer = 1
[Link] = "Root - " & NodeValue(1) &
vbCrLf
Do Until NodeValue(ThisNode) = txtSearchFor.
Text Or ThisNode = 0
‘ move to node at left pointer
If [Link] < NodeValue(ThisNode)
Then
115
ThisNode = PointerLeft(ThisNode)
[Link] = [Link] & "L - " &
ThisNode & " - " & NodeValue(ThisNode) &
vbCrLf
End If
‘ move to node at right pointer
If [Link] > NodeValue(ThisNode) Then
ThisNode = PointerRight(ThisNode)
 [Link] = [Link] & "R - " &
ThisNode & " - " & NodeValue(ThisNode) &
vbCrLf
End If
Loop
If NodeValue(ThisNode) = [Link] Then
[Link] = [Link] & "FOUND"
Else
[Link] = [Link] & "NOT FOUND"
End If
End If
End Sub
End Class
A binary tree search is similar to the in-order tree traversal that we looked
14 Search algorithms – binary, binary tree and linear search

at in the previous chapter.

Practice questions can be found at the end of the section on page 132.

KEY POINTS
• There are three main search TASKS
algorithms: binary, binary tree
and linear.
1 Explain how the three main search algorithms work: linear, binary and
binary tree search.
• A linear search starts at the
beginning of the data and goes 2 Explain the circumstances where you might use a binary search
through each item until it compared to a linear search.
finds the search item. 3 Why might a programmer use a binary tree structure?
• A binary search works by 4 Why is a binary search considered to be more efficient than a linear
splitting the data in half each search on large datasets?
time until it finds the search
item.
• A binary tree search traverses
a binary tree until it finds the
search item. STUDY / RESEARCH TASKS
• The selection of an 1 Write code to implement, populate and search a binary tree.
appropriate search method 2 Write code to carry out a linear search on a text string input by the
depends on the how much user.
data is being searched and
how it is organised. 3 Write code to carry out a binary search on a set of numeric data.
116 4 Research other search techniques and the circumstances under
• Different search algorithms
have different time which they might be used.
complexities, meaning that 5 Find out about the Google search algorithm and explain its
some will be more efficient advantages and limitations compared to other web search
than others. algorithms.
15 Reverse Polish
Notation
A level only
SPECIFICATION COVERAGE
3.3.3 Reverse Polish

LEARNING OBJECTIVES
In this chapter you will learn:
• how to evaluate mathematical expressions
• the difference between infix, prefix and postfix expressions
• what Reverse Polish Notation (RPN) is and how it is used
• how to convert expressions from infix to postfix and vice versa
• how to trace an RPN algorithm
• how RPN can be implemented.

INTRODUCTION
Reverse Polish Notation (RPN) is a way of writing mathematical
KEYWORD expressions in a format where the operators are written after the
Reverse Polish Notation (RPN): operands. For example, the expression: 5 + 3 becomes 5 3 +. The main
another term for postfix notation. advantages of this method are that it eliminates the need for brackets
and it puts the expression in a sequence that is more convenient for an
interpreter. To get a fuller understanding of RPN you need to know how
mathematical expressions are constructed and the sequence in which
they are evaluated.

● Evaluating expressions
To start with a simple example, if we have the expression 5 + 3, we know to
KEYWORDS
add the 3 to the 5 to create the result. This is known as an infix expression
Infix: expressions that are because the operator (+) is between the operands (5 and 3). 117
written with the operators within
the operands, e.g. 2 + 3. This gets slightly more complicated where the expression is longer. For
Operator: the mathematical example, 3 * 2 + 5 is another infix expression, which we would evaluate by
process within an expression. multiplying 3 and 2 and then adding 5 to the result to get 11. We evaluate
BODMAS: a methodology it in this way according to certain rules, which tell us which part of the
for evaluating mathematical expression to evaluate first.
expressions in a particular Brackets (or parentheses) are often used in expressions to make these rules
sequence.
clearer. For example, (3 * 2) + 5 makes the sequence we must use much
clearer. These rules are sometimes referred to as BODMAS, which means
Brackets, Order, Division, Multiplication, Addition, Subtraction. This means:
 ● Evaluate the expression inside the brackets first.
● Then evaluate any orders, which are calculations like squares or square
roots.
● Carry out any division or multiplication. If both appear in the expression
then they have equal importance so you work from left to right.
● Then carry out any addition or subtraction. Again, if both operators
appear in an expression, they have equal importance so work left to right.
If we had the infix expression: 3 + (18 / 32 * 3) – 4 and evaluated it using
these rules we would:
● Evaluate the expression in the brackets first:

– Square the 3 to get 9.

– Work out 18 / 9 to get 2.
– Multiply 2 * 3 to get 6.
● Now we can carry out the addition 3 + 6 to get 9.
● Then subtract the 4 to get an answer of 5.

● Polish and Reverse Polish Notation

Polish Notation was invented by Polish mathematician Jan Lukasiewicz in
KEYWORDS
1924 and therefore pre-dates computers as we know them. It was developed
Polish Notation: another way of as a way of simplifying mathematical expressions, eliminating the need
describing prefix notation.
for brackets completely, while still producing expressions without any
Interpreter: software that ambiguity as to how they should be processed. In the 1950s, it was adapted
translates and executes to become Reverse Polish Notation (RPN) because it was evident that this
programs line by line by
way of writing expressions was a convenient format for an interpreter as
converting programming
statements either into machine
it evaluates lines of programming code.
code or by calling instructions When code is written using a programming language, it has to be converted
to carry out the high-level from that language into machine code (0s and 1s) so that it can be
language statements. processed. The interpreter is a piece of software that carries out this task
Operand: a value within an
15 Reverse Polish Notation

by parsing each line of code. This means that it analyses each line of code
expression. to check that it adheres to the rules of the language, known as the syntax.
When parsing expressions, the interpreter analyses the operands first and
then the operators. Therefore, it needs the operators to be on the right-hand
side of the expression.
● Polish Notation (also known as prefix) is a method of rearranging an

expression so that all of the operators are on the left and the operands
are on the right. For example: 7 + 3 becomes + 7 3.
● Reverse Polish Notation rearranges an expression so that all the operators

are on the right-hand side of the operands. So 7 + 3 becomes 7 3 +.

118
● Converting expressions
Notice that if you do change an infix notation to either prefix or
KEYWORDS postfix, you do not change the order of the operands within the
Prefix: expressions that are expression. In the example above, the operands must appear in the
written with the operators order 7 followed by 3.
before the operands, e.g. + 2 3
Postfix: expressions that are Where there are brackets in an expression, the same rule applies to RPN;
written with the operators after you evaluate the expression in the brackets first. For example, the infix
the operands, e.g. 2 3 + expression (5 + 4) / (4 – 1) would have an RPN of 5 4 + 4 1 – /.
 ● Notice how this is made up of two parts. The 5 + 4 is evaluated first and
the RPN is created for this part of the expression: 5 4 +.

EVALUATING RPN EXPRESSIONS

● The second part of the expression of / (4 – 1) is then evaluated and
becomes 4 1 – /. Notice that the 4 – 1 is evaluated first as this is in
brackets and the final operator is the divide, which will then divide the
contents of the two bracketed expressions.
● Therefore, 5 + 4 = 9, 4 – 1 = 3 and 9 / 3 = 3.
Table 15.1 shows some more examples of expressions in infix format with
their equivalent postfix notation.
Table 15.1 Table to show conversion from infix to postfix notation

Infix Postfix Result Explanation

(6 * 3) – 1 63*1– 17 Multiply 6 by 3 to get 18 and then minus 1
(6 * 2) / 3 62*3/ 4 Multiply 6 by 2 to get 12 and then divide by 3
to get 4
(4 * 3) / (6 * 2) 4 3 * 6 2 * / 1 Multiply 4 by 3 to get 12, then multiply 6 by 2
to get 12, divide the two answers to get 1.

It is possible to convert infix to postfix and vice versa. For example, the
postfix notation 3 4 + would equate to an infix notation of 3 + 4. Similarly:
● The postfix expression 18 3 / 2 + would become the infix expression

(18 / 3) + 2
● The postfix expression 20 5 / 6 2 + – would become the infix expression

(20 / 5) – (6 + 2)

● Evaluating RPN expressions

The most common method for evaluating postfix notation is to use a stack.
Consider the infix expression (2 * 3) + 5. The postfix notation would be
2 3 * 5 +. To evaluate this using a stack:
1 Push 2 onto the stack.
2 Push 3 onto the stack.
3 Push * onto the stack.
4 As * is an operator (multiply) we need to pop this and all of the operands
currently in the stack (2 and 3) and evaluate the expression 2 3 *
5 Push the answer (6) back onto the stack.
6 Push 5 onto the stack.
7 Push + onto the stack.
8 As + is an operator (plus) we need to pop 6 5 + and evaluate the
expression.
9 Push the result (11) onto the stack.
119
The stack could be visualised during the process as shown in Figure 15.1.

Steps 1–3 Steps 4–5 Steps 6–7 Steps 8–9

* +
3 5
2 6 6 11

Figure 15.1 Representation of a stack implementing RPN

 The following code shows how an expression in the format A operand
B could be converted from infix to postfix notation. String-handling
expressions are used to identify and extract each part of the expression that
are stored temporarily before being rearranged into postfix notation.
Public Class frmConvert
Public Source As String
Public BracketL As String
Public BracketR As String
Public Expression As String
Public Number1 As Integer
Public Number2 As Integer
Public Operand As String
Public MainOperand As String
Public Pointer As Integer
Public AddToOutput As String
Private Sub btnParse_Click(ByVal sender As System.
Object, ByVal e As [Link]) Handles
[Link]
[Link] = ""
MainOperand = ""
‘store original expression in variable ‘Source’
Source = [Link]
Do
15 Reverse Polish Notation

‘ remove trailing spaces

Source = Trim(Source) + " "
‘ analyse next character in variable ‘Source’
Select Case Mid(Source, 1, 1)
Case "("
‘ extract part of main expression that is
in brackets
AddToOutput = Brackets(Source)
Case "+”, "/”, "*”, "-”
120
‘ next character is an operand
‘ store for now, add to end of expression
MainOperand = Mid(Source, 1, 1)
AddToOutput = ""
Source = Mid(Source, 3, 255)
Case Else
 ‘ next character(s) in expression is
numeric

EVALUATING RPN EXPRESSIONS

Pointer = InStr(Source, " ")
Number1 = Mid(Source, 1, Pointer - 1)
‘ source contains remainder of the
original expression
Source = Mid(Source, Pointer + 1, 255)
AddToOutput = Number1 & " "
End Select
[Link] = [Link] & AddToOutput
Loop Until Len(Source) < 2
[Link] = [Link] & MainOperand
End Sub
Private Function Brackets(ByVal SplitMe)
‘ extract contents of brackets
BracketL = InStr(source, "(")
BracketR = InStr(source, ")")
Expression = Mid(source, BracketL + 1, BracketR
- BracketL - 1)
‘ source holds the remainder of the original
expression
source = Mid(source, BracketR + 1, 255)
‘expression is presumed to be in form A operand B
BracketL = InStr(Expression, " ")
Number1 = Mid(Expression, 1, BracketL - 1)
Operand = Mid(Expression, BracketL + 1, 1)
Number2 = Mid(Expression, BracketL + 3, 255)
‘return RPN formatted expression
Brackets = Number1 & " " & Number2 & " " &
KEYWORDS Operand & " "
In-order traversal: a method End Function
of extracting data from a binary
tree that will result in an infix End Class 121
expression.
You may have noticed a similarity between the terminology used in this
Post-order traversal: a method chapter and the terminology used to traverse a binary tree. In fact there is
of extracting data from a binary
a direct relationship between the two:
tree that will result in postfix
● In-order traversal of a binary tree for an expression would produce an
expressions.
Pre-order traversal: a method expression in infix format.
● Post-order traversal would produce an expression in postfix format
of extracting data from a binary
tree that will result in prefix or Reverse Polish Notation (RPN).
expressions. ● Pre-order traversal would produce an expression in prefix format or

Polish notation.
 Working with the same example, a binary tree can be built using the
postfix expression. In this case, 2 3 * 5 + could be represented in a binary
tree as shown in Figure 15.2.

× 5

2 3

Figure 15.2 A binary tree showing the two parts of the mathematical expression

Note that the left subtree carries out the multiplication and the right
subtree carries out the addition:
● A post-order traversal traverses the left subtree, traverses the right subtree

and then visits the root, giving the result 2 3 * 5 +.

● An in-order traversal traverses the left subtree, visits the root and

traverses the right subtree giving the result 2 * 3 + 5.

● A pre-order traversal visits the root, traverses the left subtree and then

traverses the right subtree giving the result + * 2 3 5.

● Applications of RPN
The code used in this chapter has been produced in Visual Basic, which is
considered to be a general purpose imperative language. Some languages
are specifically designed to be stack-oriented and would therefore be ideally
suited to this application. In these cases, the interpreter or compiler checks
15 Reverse Polish Notation

all of the syntax with reference to the postfix (or RPN) notation of each
KEYWORD expression. Perhaps the most common of these is PostScript, which is used
Vector graphics: an image made to create vector graphics. This works by pushing operands onto the stack
up of objects and coordinates. until an operator is pushed on. At that point it pops the operands off the
stack with the operator, performs the calculation and pushes the answer
back to the stack.
RPN is closer to the way in which computers actually carry out
computations. You can look at infix as the way in which humans work,
that is, we expect an operand followed by an operator. Postfix is the way
in which processors work in that they are made up of a series of registers
and units all of which carry out different functions. For example, one
register will store values, while another (the arithmetic logic unit) carries
122
out calculations. Therefore, it needs to know all the operands first so it can
put them into the appropriate registers. At this point the processor needs to
know which operators to use so it knows what to do with the operands.
As you know, there are many different types of programming languages.
Some of these are high level, which means that the programmer can write in
code that is similar to normal language. Others are low-level, which means
that they are closer to the machine code (or 0s and 1s) that processors actually
use. Some of these low-level languages such as bytecode use postfix notation .
Practice questions can be found at the end of the section on page 132.
 APPLICATIONS OF RPN
TASKS
1 Convert the following expressions from infix to postfix (Reverse
Polish) notation.
a) 5 * 6 b) (5 * 4) – 3 c) (6 * 3) / (2 + 4)
2 Convert the following expressions from postfix to infix.
a) 12 4 / 2 + b) 4 4 * 2 2 * + c) 24 6 / 3 2 + 2 /
3 Draw a binary tree for the expression (5 + 6) * 3.
4 What would be the result of the following traversals on the tree you
KEY POINTS made for question 3?
• Reverse Polish Notation a) in-order b) post-order c) pre-order
(RPN) is a way of writing
5 What is the purpose of Reverse Polish Notation?
mathematical expressions in
a format where the operators 6 Explain why infix notation is used by humans whereas postfix notation
are written after the operands. may be used by an interpreter or compiler.
• RPN is useful as it puts
expressions in a format
that can be used more
straightforwardly by an
interpreter. STUDY / RESEARCH TASKS
• Infix refers to expressions that 1 Research programming languages that use either prefix or postfix
are in the order that humans notation. Why do they use this particular form of notation?
work with, e.g. 5 + 3.
2 Write code to convert:
• Postfix refers to expressions
a) infix expressions to postfix
that are in RPN, e.g. 5 3 +.
b) postfix expressions to infix.
• Prefix refers to expression
where the operators are first, 3 Find out how Java converts high-level code to bytecode using postfix notation.
e.g. + 5 3. 4 Why was RPN used as a way of programming early calculators?
• RPN can be evaluated using a 5 Explain how a stack can be used to convert an infix expression to
stack. a postfix expression.

123
 16 Sorting algorithms–
bubble and merge
A level only
SPECIFICATION COVERAGE
3.3.5 Sorting algorithms

LEARNING OBJECTIVES
In this chapter you will learn:
• what a bubble sort is and how to implement one
• what a merge sort is and how to implement one
• how to compare the efficiency of the two sorting methods.

INTRODUCTION
Sorting is one of the most common processes you would normally want
to carry out on a set of data. Sorting simply means that the data are
put into a particular order, typically alphabetical or numerical in either
ascending or descending order.

There are lots of different ways of sorting data, and one of the skills that
programmers need, is to decide which method suits their needs best.
Some are particularly good when there are a lot of data to sort, others
are particularly good when the data are almost, but not quite in the right
order, and so on.

● Bubble sort
If the data are held in an array you can sort the data by comparing each
KEYWORD element in the array with the following element. If the first item is bigger
Bubble sort: a technique than the second then you swap them. If you repeat this process enough
for putting data in order by times the data will eventually be sorted in ascending order.
124 repeatedly stepping through
an array, comparing adjacent In this example the data are stored in an array called Storage and the
elements and swapping them if array holds NumberOfRecords records. The numbers at the start of
necessary until the array is in each line are there to help with the explanation – they are not part of the
order. algorithm.
1 For Loop1 = 1 To NumberOfRecords – 1
2 For Loop2 = 1 To NumberOfRecords – 1
3 If Storage(Loop2)> Storage(Loop2 + 1) Then
 4 Temporary Storage(Loop2)

BUBBLE SORT
5 Storage(Loop2) Storage(Loop2 + 1)
6 Storage(Loop2 + 1 ) Temporary
7 End If
8 Next Loop2
9 Next Loop1
Suppose the array Storage had eight elements.

Element 1 2 3 4 5 6 7 8
Data 12 3 16 9 11 1 6 8

Figure 16.1

The algorithm would work like this:

● For now we will ignore lines 1 and 9 in the algorithm and start with lines
KEYWORD 2 to 8.
Iteration: repeating the same ● Lines 2 to 8 are a For/Next loop – a form of iteration. In this case the
process several times in order process is going to be repeated seven times. The instructions that are
to achieve a result. going to be repeated are lines 3 to 7.
● Line 3 compares each element in the array with its neighbour. So the first

time the loop is processed Loop2 contains the value 1 so the contents
of Storage(1) is compared with the contents of Storage(2). In this
case these values would be 12 and 3, respectively.
1 2 3 4 5 6 7 8 ● 12 is greater than 3 so lines 4, 5 and 6 are carried out and the values are

3 12 16 9 11 1 6 8 swapped round to leave the array as shown in Figure 16.2.

● The value of Loop2 is now incremented to 2 so the contents of
Figure 16.2 Storage(2) is compared and swapped if necessary with the contents of
Storage(3) and so on.
1 2 3 4 5 6 7 8 ● This whole process of comparing and swapping carries on until all the
3 12 9 11 1 6 8 16 elements in the array have been examined. At the end of the loop the
Figure 16.3
array now looks like Figure 16.3.
● As you will have noticed this isn’t very sorted yet. That is why lines 1 and 9
1 2 3 4 5 6 7 8 are there. They now repeat the process all over again until the array is
1 3 6 8 9 11 12 16 finally sorted as shown in Figure 16.4.
Figure 16.4 This algorithm is called a bubble sort because each time the algorithm
carries out one pass of the array the larger numbers are bubbling to one end
of the array and the smaller ones to the opposite end.
This first example is actually very inefficient – it gets carried out regardless
of whether it needs to be or not, and there is a lot of unnecessary work for
the computer to do. 125

The second algorithm below carries out exactly the same process, but
in a more sophisticated way. This time the algorithm uses a flag called
CompletedFlag to record whether or not a swap has been made. If no
swaps have been made then the data must be sorted so there is no point in
carrying on.
 Repeat
CompletedFlag True
For Counter = 1 To NumberOfRecords - 1
If Storage(Counter) > Storage(Counter + 1) Then
Temporary Storage(Counter)
Storage(Counter) Storage(Counter + 1)
Storage(Counter + 1) Temporary
CompletedFlag False
End If
Next
Until CompletedFlag = True
The Visual Basic code below shows a bubble sort routine for text strings.
Private Sub btnSort_Click(ByVal sender As System.
Object, ByVal e As [Link]) Handles
[Link]
Dim Loop1 As Integer
Dim Loop2 As Integer
Dim TempStore As String
16 Sorting algorithms–bubble and merge

Dim RowsToSort As Integer

RowsToSort = [Link] - 2
For Loop1 = 1 To RowsToSort - 1
For Loop2 = 1 To RowsToSort - 1
‘compare each value in the table with the
following value
‘changing the inequality will sort high to low
If [Link](Loop2).Cells(0).Value >
[Link](Loop2 + 1).Cells(0).Value Then
‘swap values to move larger values to later
cells
TempStore = [Link](Loop2).Cells(0).
Value
[Link](Loop2).Cells(0).Value =
126
[Link](Loop2 + 1).Cells(0).Value
[Link](Loop2 + 1).Cells(0).Value =
TempStore
End If
Next
Next
End Sub
 ● Merge sort

MERGE SORT
A merge sort is classified as a ‘divide and conquer’ algorithm, which breaks
KEYWORD a problem down into smaller and smaller units until it gets to a level where
Merge sort: a technique for the problem can be solved. What this means in the case of the sort routine is
putting data in order by splitting that if you had a list with one element it is, by definition, sorted. Therefore, if
lists into single elements you start with a large list of elements, all you need to do is break the list down
and then merging them back into a series of smaller lists each containing one single element. You can then
together again.
compare the lists and merge them back together to produce a sorted list.
The merge process works as follows. Assume you have two lists that are
already sorted in order:
List 1 List 2
3 2
5 6
8 9
10 12

Figure 16.5
● Compare the first element of each list. In this case 3 would be compared
to 2. Put the lowest number in the new merge list. In this case we move
the 2. Our lists would now look like this:
List 1 List 2
3 2
5 6
8 9
10 12
Merge list = 2

Figure 16.6

● Repeat the process comparing the first element in each list and placing
the lowest item in the merge list. We now have 3 compared to 6, so our
lists will now look like this:
List 1 List 2
3 2
5 6
8 9
10 12
Merge list = 2, 3
Figure 16.7

● Repeat this process until there is only one element left and put this at the
end of the list. You now have one list containing the sorted elements.
To sort an unordered list, you first need to break the list down. For
example, if we have a list with eight elements as shown:
5 3 8 10 9 2 6 12
127
Figure 16.8
● Split the list into half.
5 3 8 10 9 2 6 12

Figure 16.9

● Keep splitting the list in half until each list only has one element:
 5 3 8 10 9 2 6 12

5 3 8 10 9 2 6 12

Figure 16.10

You now effectively have eight lists, all containing one element. We need
to merge a pair of lists at a time until we have one complete list.
● Compare the first two lists, which are 5 and 3 and put the lowest number
first. We get:
3 5

Figure 16.11

● Compare the next two lists, which are 8 and 10 and put the lowest
number first. We get:
8 10

Figure 16.12

● Do this for the next two pairs of lists:

2 9 6 12

Figure 16.13

We now have four lists:

3 5 8 10 2 9 6 12
16 Sorting algorithms–bubble and merge

Figure 16.14

● Repeat the process merging these lists together. Start by comparing the
first element in each list and putting the lowest first as shown earlier. For
the first pair of lists:
– Comparing 3 and 8, we would put 3 in the merge list.
– Comparing 5 and 8 we would put 5 in the merge list.
● We then merge the 8 and the 10, which we know are already in the right
order to get:
3 5 8 10

Figure 16.15
● Repeat this process for the other two lists and you get:
2 6 9 12

Figure 16.16
● Now merge these two lists together in the same way to get:
128 2 3 5 6 8 9 10 12

Figure 16.17

This is an efficient method of sorting where there are lots of elements in the
original list. This is because the algorithm works by halving the lists each
time. However, in terms of space, the merge sort will require more space
than a bubble sort to create the intermediary lists and the final merge list.
There is more on the efficiency of algorithms in Chapter 23.
As you have probably worked out, you can use a loop to split down the
elements as many times as required to create single-element lists. Each

MERGE SORT
pair of lists can then be compared and merged as many times as needed
to reconstruct the list in the correct order. The following code shows the
process in Visual Basic.
Public Sub MergeSort(ByVal ptrFirst As Integer,
ByVal ptrLast As Integer)
Dim ptrMiddle As Integer
If (ptrLast > ptrFirst) Then
‘ split list in half and carry out recursive call
ptrMiddle = (ptrFirst + ptrLast) \ 2
MergeSort(ptrFirst, ptrMiddle)
MergeSort(ptrMiddle + 1, ptrLast)
‘ Merge the results.
Merge(ptrFirst, ptrMiddle, ptrLast)
End If
End Sub
‘ Merge two sorted sublists.
Public Sub Merge(ByVal beginning As Integer, ByVal
ptrMiddle As Integer, ByVal ending As Integer)
ReDim TempStore(RowCount)
Dim CountLeft As Integer
Dim CountRight As Integer
Dim counterMain As Integer
‘ Copy the array into a temporary array
For LoopCount = 1 To RowCount
TempStore(LoopCount) = DataStore(LoopCount)
Next
‘ CountLeft and CountRight point to next item to
save from left / right halves of the list
CountLeft = beginning
CountRight = ptrMiddle + 1
129
‘ counterMain is the index where we will put the
next item in the merged list.
counterMain = beginning
Do While (CountLeft <= ptrMiddle) And (CountRight
<= ending)
‘ Find the smaller of the two data at the top of
the left and right lists
 If (TempStore(CountLeft) <= TempStore(CountRight))
Then
‘ smaller value is in left half
DataStore(counterMain) = TempStore(CountLeft)
CountLeft = CountLeft + 1
Else
‘ smaller value is in right half
DataStore(counterMain) = TempStore(CountRight)
CountRight = CountRight + 1
End If
counterMain = counterMain + 1
Loop
‘ copy any data from the end of the list
If CountLeft <= ptrMiddle Then
‘ copy from left half
For LoopCount = 1 To ptrMiddle - CountLeft + 1
DataStore(counterMain + LoopCount - 1) =
TempStore(CountLeft + LoopCount - 1)
16 Sorting algorithms–bubble and merge

Next
Else
‘ copy from right half
For LoopCount = 1 To ending - CountRight + 1
DataStore(counterMain + LoopCount - 1) =
TempStore(CountRight + LoopCount - 1)
Next
End If
End Sub
Notice that the code uses recursion, where a subroutine calls itself. In this
example the MergeSort subroutine calls itself.
Practice questions can be found at the end of the section on page 132.

130
 MERGE SORT
TASKS
KEY POINTS 1 Explain how you could use a bubble sort and a merge sort to sort the
following list of data:
• Sorting means that the data
12, 3, 4, 8, 2, 6, 10, 5
is put into a particular order,
typically alphabetical or 2 Explain why a bubble sort requires data to be stored in an array.
numerical in either ascending 3 Would a bubble sort or merge sort be the quickest way of sorting this
or descending order. list? Explain your answer.
• There are different algorithms 4 What if there were one million items in a list? Which would be the
that can be used to sort data. quickest then? Explain you answer.
• If the data is held in an array 5 Bubble sort uses ‘iteration’ and a merge sort uses ‘recursion’. What
you can sort the data by do these terms mean and why are they needed?
comparing each element in
the array with the data in the
following element.
• A merge sort is classified
as a ‘divide and conquer’ STUDY / RESEARCH TASKS
algorithm, which breaks a
problem down into smaller 1 Write code to carry out a bubble sort and a merge sort on a list of
and smaller units until it gets characters.
to a level where the problem 2 Research other algorithms that could be used to sort data. Explain the
can be solved. circumstances where you might use one rather than the other.

131
 Section Three: Practice questions
1 Two methods for searching a dataset are a binary search and a linear search.
a) Write pseudo-code to show how a binary search works.
b) Explain how efficient this method is on a large ordered set of data, compared to a linear search.
2 The following graph shows the distance between five towns.

10
Town A Town B 20

30 20 Town E

10
Town C 30
Town D

a) Show this as an adjacency matrix.

b) Show this as an adjacency list.
3 Convert the following infix expressions into Reverse Polish Notation (RPN).
a) 5 + 6
b) 4 * 7 + 12
4 Explain one advantage of using RPN over infix notation.
5 A binary search tree is used to store data arriving in this sequence: d, c, a, f, b, g.
a) Draw a binary search tree to show how this could be implemented.
b) Write pseudo-code to add data to this binary search tree.
c) Write pseudo-code to carry out a traversal that will put this data into alphabetical order.
Section Three: Practice Questions

132
Section Four:
Fundamentals of
computational
thinking
 17 Abstraction and
automation
SPECIFICATION COVERAGE
3.4.1 Abstraction and automation

LEARNING OBJECTIVES
In this chapter you will learn how:
• to use logical reasoning
• to take a systematic approach to problem solving
• to define problems using abstraction
• algorithms can be used to solve problems
• to hide the complexity of a problem from the user
• to decompose a problem and compose a solution
• to use computer models to recreate real-life problems and solutions.

INTRODUCTION
Computing is about processing data to solve a problem, for example
doing calculations using data. The modern definition of the term implies
the use of computer technology although much of the work needed to
KEYWORDS solve the problem is actually done away from the computer itself. There
Problem solving: the process are techniques that programmers can use to help with problem solving
of finding a solution to real-life and in this chapter we will be looking at:
problems. • abstraction, which is the concept of picking out common concepts
Automation: creating a in order to reduce the problem to its essential defining features,
computer model of a real-life ignoring less significant details
situation and putting it into • automation, which is the process of creating a computer model and
action. putting it into action.
Logical reasoning: the process
134 of using a given set of facts to The focus of this chapter is on problems that typically require
determine whether new facts are mathematical calculations to solve them, as opposed to information
true or false. processing systems.

● Logical reasoning
Logical reasoning is the process of using a given set of facts to determine
whether new facts are true or false. More formally it is concerned with
the concept of deductive reasoning which originates from the study of
mathematics and philosophy which identifies rules or premises and then
applies these to statements to come to a conclusion.
 Using logical reasoning is an important skill for you as computer scientists
as it is closely related to the issue of solving problems. Logical reasoning

PROBLEM SOLVING
helps you to understand the nature of problems, to identify the facts that
are relevant to the problem and to then be able to draw conclusions. It also
enables you to identify new facts that you can deduce are true based on
existing facts.
For example, we might have the following fact: ‘Alex is a boy’. From this
we might conclude that Alex is a boy’s name. We might have another fact:
‘Alex is a girl’. From this we might conclude that Alex is a girl’s name. By
combining the two facts we might reach a more accurate conclusion that
Alex can be a boy’s or a girl’s name.
Consider the following example:
Four friends sit at a concert together. Jane was sitting in seat A3.
Kian was sitting to the right of Jane in seat A4. In the seat to the
left of Jane was Ravi. Dev was sitting to the left of Ravi. Which
seat is Dev sitting in?
To reason this out you will notice that the seats are sequentially ordered
and there are just four people, so the answer is going to be somewhere
between A1 and A6. Ravi is to the left of Jane so must be in seat A2 and
Dev is to the left of Ravi so must be in seat A1.
The example below shows some facts that we might use when developing
a satnav system. It shows how new facts can be determined from existing
ones:
● Motorways have higher speed limits than single-lane roads.
● Single-lane roads have speed limits of between 30 mph and 60 mph.
● Dual carriageways have the same speed limits as motorways.
● Most roads in urban areas are single carriageway.

From these facts, we could determine further facts:

● A single-lane road could have a 40 mph speed limit.
● The speed limit on motorways must be more than 60 mph.
● Subject to traffic conditions, a journey would typically be quicker on a

dual carriageway than on a single-lane road.

● Journeys through towns are likely to be slower that journeys along

motorways.

● Problem solving
People have been solving problems using computational thinking for thousands
of years. In simple terms, it concerns identifying a problem and then working
out the steps required to solve it. In doing this, you need to take account of any 135
constraints that would impact on the solution. The objective is always to create
the most efficient solution to any given problem and to be able to apply the
solution to other, similar problems.
For example, humans have always travelled. The problem in this
scenario is how to get from the start to the destination in the quickest
and easiest way. Before humans were able to write things down, they
would give each other verbal instructions on how to get from A to B.
The next piece of technology to be used was the map, which provided
a more efficient and reusable method for solving the problem. Maps
 have become increasingly sophisticated over the years to include more
information for the user, although a certain amount of skill is required
in order to read them.
The latest technology is the ‘satnav’, which combines large datasets, often
being updated in real time with traffic information, being transmitted
wirelessly to small portable devices using a very simple user interface that
only requires the user to input the destination and then follow the verbal
and visual instructions.
17 Abstraction and automation

Figure 17.1 A very early map

136

Figure 17.2 A modern map

 ALGORITHMS
Figure 17.3 A satnav

Defining and solving problems

This example demonstrates some of the key aspects of problem solving. In
the first instance the problem needs to be clearly defined. In this case the
problem is quite simple: How do I get from A to B? The solution however,
is complex. As a user, all you want to do is type in the destination and
then follow the instructions. However, as a computer scientist, you need to
consider a large range of issues and constraints in order to come up with a
solution. For example:
● How to define the start and end points of each journey, e.g. town name,

grid reference.
● What form of transport will be used, e.g. car, cycle, walking.
● What routes will be used, e.g. roads, ferries.
● What data is available, e.g. road networks, traffic information.
● How data is kept up to date.
● How to calculate the quickest or shortest route to the destination.
● How to recalculate the route in case of traffic jams or road closures.
● What communication channels will be available to transmit the

relevant data.
● How to present the information to the user in the most user-friendly way.

Having identified the problem you would then develop the most efficient
solution, which may require several iterations. One of the key aspects of
computing is that solutions must be checked to ensure that they do solve
the problem. With our satnav example, extensive testing will be undertaken 137
in-house by the manufacturers of the devices. They will also beta-test by
getting users to use the systems in real-life situations before releasing the
technology to the general public. The manufacturers will then constantly
review feedback from customers in order to refine the technology.

● Algorithms
You have already come across algorithms in Section One. Basically an
algorithm is a step-by-step procedure for carrying out a particular task.
 Algorithms are the building blocks of computer programs and ultimately
KEYWORD
all problems are solved by writing algorithms. To take a very simple
Algorithm: a sequence of example, to calculate how long it takes to do a journey you could use the
instructions.
following algorithm:
TimeDeparted = 15:00
TimeArrived = 16:00
Drivetime = TimeArrived - TimeDeparted
This is an example of pseudo-code, which is a way of expressing the
algorithm without having to use any specific programming language.
The start point for programmers is often to work out what algorithms are
needed to solve a problem and then to write these in pseudo-code during
the planning stage. This can be a time-consuming process depending on
the complexity of the solution.
Programmers use a technique called hand-tracing or dry running to work
through their code. This means that they follow the code line by line to work
out what is happening. This can help them to identify any problems with
the code before it is implemented. There is an example of dry running in
Chapter 5. Most programs are made up of multiple related procedures so it is
important to identify how these link together to create the program as a whole.
When all of the procedures have been identified, the pseudo-code can
be converted into proper programming code using whatever language is
considered the most appropriate for solving the problem.

● Abstraction
The concept of abstraction is to reduce problems to their essential features.
17 Abstraction and automation

Another way of explaining abstraction is that it is the process of finding

similarities or common aspects about the problem, while ignoring differences.
This is a useful concept for programmers as they can view the problem from
a high level, concentrating on the key aspects of designing a solution whilst
ignoring the detail, particularly during the initial design stages.
Once a solution has been identified for the current problem, a feature of
abstraction is that the abstraction from one problem can be applied to
another similar problem, which shares the same common features.
Broadly speaking there are two main type of abstraction.

Representational abstraction
This is the process of removing unnecessary details until it is possible to
KEYWORD represent the problem in a way that can be solved. This level of abstraction
138 Representational abstraction: could be described as viewing the ‘big picture’ – working out what is
the process of removing relevant to solving the problem and what is unnecessary detail that can be
unnecessary details so that only
ignored.
information that is required to
solve the problem remains. With the satnav problem, at a basic level, the problem can be reduced to
finding the shortest distance between point A and point B. An abstraction
of that would be to:
● identify point A and point B in some way
● identify the connecting paths between A and B
● calculate the shortest path between A and B.
 Now that the abstraction is complete a solution can be created to solve the
problem. For example, a variation of Djikstra’s shortest path algorithm

ABSTRACTION
could be developed. In addition, related problems can be solved using the
same abstraction.
Some information that would be found on a map would not be required to
find a shortest route. For example, the location of rivers, railway lines and
landmarks could be ignored, so the map stored by the satnav would be an
abstraction of the real location.

Abstraction by generalisation/categorisation
This is the process of placing aspects of the problem into broader categories
KEYWORD to arrive at a hierarchical representation. This involves recognising common
Abstraction by generalisation/ characteristics of representations so that more general representations
categorisation: the concept of can be developed. We have already seen this concept applied with object-
reducing problems by putting oriented programming in Chapter 6, where subclasses are defined from the
similar aspects of a problem into characteristics of a base class.
hierarchical categories.
For example, to represent information about cars and buses, we recognise
that they have a lot in common so generalise/categorise them both as
vehicles. When programming using an object-oriented language we can
represent this generalisation using inheritance.

Vehicles

Car Bus Lorry Van

Figure 17.4 Abstraction by generalisation for vehicles

The principle of abstraction can also be applied to various elements of

computing including:
● Procedural abstraction: This is the concept that all solutions can be

broken down into a series of procedures or subroutines. This in fact is

the way that all procedural languages work, enabling the programmer to
identify the main processes needed to complete the task and to contain
these within procedures. At the design stage it is sufficient for the
programmer to work out what each procedure will do without defining
how it will do it. The procedure may in turn call other procedures
KEYWORDS although it does not need to know how these work in order to call them.
Top-down design: related to the This is the basis for top-down design that we looked at in Chapter 5.
modular approach, this starts Other considerations include what event will trigger the procedure, how
with the main system at the top procedures will link together, including any possible side effects, and
and breaks it down into smaller how errors will be handled.
and smaller units a bit like a ● Functional abstraction: Similar to procedural abstraction, functional
139
family tree. abstraction focuses on common functions that can be used to solve
Functional abstraction: breaking problems. Functions are a feature of procedural languages and the
down a complex problem into a cornerstone of functional programming, where all the main processes
series of reusable functions. are defined in terms of functions. Functions can be created for any
common procedure and functions can be built on top of other functions
producing higher levels of abstraction. All the program needs is for the
parameters to be input into the function in order to generate a result.
Using functions reduces complexity as the function only needs to be
written once.
 ● Data abstraction: This is the process of organising and structuring data
in a way that produces a particular view of the data that is useful for
the programmer. Almost all data is abstracted, hence the term abstract
data types that we looked at in Chapter 7. For example, a queue is an
abstract data type, which may be made up of an array. By abstracting
the data into a queue, all the programmer has to do is push and pop to
KEYWORD the queue without having to worry about the structure of the underlying
Data abstraction: hiding how dataset. Another feature of data abstraction is that the data can be
data is represented so that it is implemented in different ways. For example, once data is abstracted into
easier to build a new kind of data an array, it could be used to create other abstract data types such as stack
object, e.g. building a stack from or a binary tree. This is known as data composition where data objects
an array.
are combined in order to create a compound structure.
Data abstraction involves separating the actual implementation from the
interface. In the satnav example, the algorithm needs to find the shortest
journey between two points. The interface provides this information but
how it is implemented is hidden. It doesn’t matter whether the data is
being stored in an array, as a vector or in a relational database, providing
KEYWORD the relevant answer is provided by the program.
Problem abstraction: removing ● Problem abstraction: This is the process of reducing a problem down
unnecessary details in a to its simplest components until the underlying processing requirements
problem until the underlying that solve the problem are identified. By doing this, these underlying
problem is identified to see if this processes can be applied to solve analogous problems. For example,
is the same as a problem that satnavs use vectors (see Chapter 11) and a variation of Dijkstra’s
has already been solved.
algorithm (see Chapter 13). Neither of these concepts were developed
specifically for the satnav, but both have been adopted to create the
required solution. Therefore, the underlying principles used to solve one
problem been applied to different problem with similar characteristics.
Another example is the use of graphs in general. In Chapter 9 we
looked at the use of graphs to explain relationships between nodes.
17 Abstraction and automation

Many problems have been solved using graph theory, as the underlying
requirements of the problems are the same even though they may not
appear to be. For example, graphs are used to optimise the transmission
of data on computer networks, to model atomic and chemical structures,
to predict the spread of disease and to analyse social networks.

● Information hiding
In broad terms, information hiding is the process of providing a
KEYWORD definition or interface of a system or object, whilst keeping the inner
Information hiding: the process workings hidden. A common example of the principle is the car. All cars
of hiding all details of an object have a common interface in that they have a steering wheel, gearbox, pedals
that do not contribute to its etc. By operating this common interface it is possible to operate the car. The
essential characteristics. actual mechanics of how the car works is hidden. In fact, the mechanics of
140
how the car works may change without it impacting on the interface. For
example, changing from a petrol to a hybrid engine does not change the
basic principles of how to drive a car.
An example in computing is where a common interface such as a GUI is
used. With our satnav example, the interface prompts the user to input an
end point. The complexity of calculating the route is hidden. If the way in
which the route was calculated changed, it would not necessarily affect the
interface. In this way, information hiding separates the user interface from
the actual implementation of the program.
 More specifically when programming, information hiding can be used
to define a set of behaviours on a dataset, where the data can only be

DECOMPOSITION/COMPOSITION
accessed through those behaviours. It is not possible for other parts of
the program to access the dataset directly. This prevents unintended
damage to the dataset and also means that how the dataset is stored can
be changed without affecting any programs that use it, as they do not
access it directly.
Information hiding is closely related to the concept of encapsulation
where data and behaviours are stored together within a class or object.
Encapsulation can be seen as a method of implementing the information-
hiding principle.

● Decomposition/Composition
A broad definition of decomposition is breaking large complex tasks
KEYWORDS or processes down into smaller, more manageable tasks. Abstraction
Decomposition: breaking down techniques will be used in order to decompose the system requirements.
a large task into a series of
subtasks. Procedural decomposition is the process of looking at a system as a
Composition: building up a whole and then breaking that down into procedures or subroutines
whole system from smaller needed to complete the task. This process is very similar to the idea of
units. The opposite of the top-down approach we looked at in Chapter 5 where each main task
decomposition. is identified, then the subtasks that make up each task. Depending on
the complexity of the system, subtasks may be further subdivided until
the designer reaches a level of detail that is sufficient to start building
the system.
Procedural composition is then the process of creating a working system
from the abstraction. This involves:
● writing all the procedures and linking them together to create compound

procedures
● creating data structures and combining them to form compound

structures.
A satnav system could be decomposed as follows:

Satnav system

Journey Travel Road network

141
Input Input travel National International
Start point End point
travel data updates roads roads

Calculate route

Figure 17.5 Decomposition of a satnav system

 ● Automation
Automation in this context is the process of creating computer models of
real-life situations and putting them into action. Most computer programs
are created to solve real problems. One of the objectives of creating
computer systems is to create elegant solutions to difficult problems.
The key to this is:
● understanding the problem
● being able to create suitable algorithms
● building the algorithms up into program code
● using appropriate data in order to solve the problem.

For example, computer models are widely used to analyse traffic flows
and to control traffic lights across road networks. Major cities and towns
often have severe traffic congestion and by controlling the traffic lights it
is possible to keep traffic moving more freely.
17 Abstraction and automation

Figure 17.6 Computer model for traffic flow system

The screenshot in Figure 17.6 is from a software model called TRANSYT

and demonstrates the problem. Where one set of lights is on green you may
assume the traffic is flowing freely. However, by definition it means that
142 there is likely to be a queue of stationary traffic (or pedestrians) waiting at
a red light. Where there are several sets of traffic lights close together, the
problem becomes more difficult to solve.
Therefore, the outcome is simply to keep traffic moving as freely as possible
around the network. The solution is far more complex. The designer needs
to consider:
● the location of all traffic lights
● the number of roads that meet at each set of traffic lights

how many lanes of traffic there are at each set of lights

● how much traffic there is on each of the lanes
 what time of day it is, i.e. is it rush-hour and whether people are
generally heading into or out of the city

AUTOMATION
● whether the lights control a pedestrian crossing as well as a road.
There are probably many other considerations, but the challenge for the
designer is to identify the key factors that will make the model accurate. In
addition they need to consider what data to use and where to get it from. As
a minimum they will need data for:
● the roads in the network
● the physical location of the lights
● the volume of traffic on the road, which will either be historical or real-

time data.
Having collected all of this data, code must be written to optimise traffic
flows, which involves switching the signals and leaving them on green or
red for the correct amount of time. For example, if there is a busy main
road with heavy traffic, more time on green must be allowed at the expense
of traffic on the side roads.
Using automated models in this way requires constant calibration of the model.
This means that the designers need to see how well their modelled system works
in real life. If traffic is not flowing as expected they need to make changes either
to their algorithm or to their data in order to make the model more accurate.
Practice questions can be found at the end of the section on
pages 179 and 180.

TASKS
1 From the following facts, use logical reasoning to determine further
facts that you know to be true:
a) every cat eats mice
b) some animals that eat mice are fat
c) all mice carry diseases
d) mice can run fast.
2 You are asked to work out the timetable for all the students in the
sixth form.
a) What factors do you need to take into account in order to solve this
problem?
b) Give an example of representational abstraction and abstraction by
category / generalisation in this scenario.
c) Explain how you might decompose the problem.
3 Define the following terms:
a) procedural abstraction
b) functional abstraction
c) data abstraction 143
d) problem abstraction.
4 Define information hiding and give an example of where it might be used.
5 Create a specification for a model to simulate any or all of the
following scenarios:
a) the likelihood of a particular team winning a competition
b) the speed at which a concert hall could be evacuated in the event of
a fire alarm
c) how many people and households there will be in the UK in 2050.
 STUDY / RESEARCH TASKS
1 Explore the concept of computational thinking and consider examples
that predate the invention of the computer.
2 Models have been built to predict how many gold medals Britain will
win during Olympic Games. Find out what variables go into these
models and how accurate the predictions have been.
3 Research what data and algorithms are used in order to predict:
a) weather
b) tornados
c) tsunamis.
4 Find examples, other than those in this chapter, where an algorithm
developed to solve one problem has been used to solve a different
problem.

KEY POINTS
• Logical reasoning is the process of using a known set of facts to
defermine whether new facts are true or false.
• Problem solving is identifying a problem and then working out the
steps required to solve it.
• Simple problems may have complex solutions.
• An algorithm is a step-by-step procedure for carrying out a
particular task.
• Abstraction reduces unnecessary detail instead focusing on the
essential features that will solve the problem.
• Information hiding is the process of hiding all details of an object that
17 Abstraction and automation

do not contribute to its essential characteristics.

• Decomposition is breaking large complex tasks or processes down
into smaller, more manageable tasks.
• Composition is then the process of creating a working system from
the abstraction.
• Automation in this context is the process of creating computer models
of real-life situations and putting them into action.

144
18 Finite state machines

SPECIFICATION COVERAGE
3.4.2 Finite state machines

LEARNING OBJECTIVES
In this chapter you will learn:
• what a finite state machine is and how it can be used
• how to use state transition diagrams
• how to use state transition tables.
A-level students will learn:
• how to use finite state machines with outputs.

KEYWORDS INTRODUCTION
Finite state machine (FSM): any In general terms a finite state machine (FSM) is any device that can
device that stores its current store its current status (or state) and can change state based on an
status and whose status can input. The FSM may receive further inputs, which in turn change the
change as the result of an input. state again. There are a finite (countable) number of transitions that may
Mainly used as a conceptual take place. Some FSMs also have outputs, one type of which is called
model for designing and a Mealy machine. Knowledge of these is only required for A level and is
describing systems. covered at the end of the chapter.
Finite: countable.
As a simple example, an automated door is an FSM:
Input: Button pressed
State 0: Door closed State 1: Door open
Input: Button pressed
Figure 18.1 A simple example of an FSM
Finite state machines are common in everyday life and include any devices
where there are a predefined set of steps and outcomes involved in the
145
operation of the machine.
In practice, finite state machines are used as a conceptual model to design
and describe systems. They are particularly useful at the design stage as
they force the designer to think about every possible input and how that
changes the state of the machine. As a result they are commonly used to
develop computer systems or design logic circuits and can also be used to
check the syntax of programming languages.
There are two main ways of representing an FSM: a state transition diagram
or a state transition table.
 ● State transition diagrams
State transition diagrams use circles to represent each state and
KEYWORDS arrows to represent the transitions that occur as the result of an input.
State transition diagram: a For example, a ticket machine in a car park requires two inputs: money
visual representation of an FSM to be put in and the green button to be pressed. A double circle represents
using circles and arrows. the accepting or goal state, which in this case is the state that is required
Accepting state: the state that in order to issue a ticket. FSMs do not necessarily need to have an
identifies whether an input has accepting state.
been accepted.
Input: Money inserted Input: Button pressed
S0 S1 S2

Figure 18.2 A simple state transition diagram

In this case:
● S0 is the machine in its idle state, waiting for an input.
● S1 is its state after the money has been put in.
● S2 is its state after the button has been pressed. This is the accepting state.

The FSM has sequence and memory in that each transition is based on
the one before. For example, the button can only be pressed after the
money has been inserted. Whole systems or individual procedures can be
modelled using state transition diagrams. For example, the procedure for
logging onto a computer network might look like this:

Username
incorrect

S0
Username
correct
18 Finite state machines

Password
S2 S1
incorrect

Password
correct
Figure 18.3 State transition diagram to show the process of
logging onto a computer network

This shows the dependency of one state on the next. If the username is
correct it can change to the next state. If the password is correct it can move
on to the accepting state. Without the correct inputs the state will not change.
146 The example in Figure 18.4 shows an FSM that is used to check that the
rules of a programming language are being followed. It is a simplified
example using just the letters a, b and c, though in real life the FSM
could be set up to represent all of the acceptable words and combinations
of words usable in any particular programming language. Notice the
addition of a start arrow.
 a
S0 S1

STATE TRANSITION TABLES

b, c a, c

a, b, c S4 b b

a
a, b
c
S3 S2

c
Figure 18.4 State transition diagram to show syntax rules

Looking at the diagram you can see whether certain combinations of letters
are acceptable or not. For example:
● abc is an acceptable combination.
● abcc is an acceptable combination.
● acb is not acceptable. This would end in S4.
● abca is not acceptable as S3 is the accepting state so the final letter must

be a c. This would end in S4.

● State transition tables

The same information can also be represented as a table. These show the
KEYWORD input and the current state, which is the state before the input. It then
State transition table: a tabular shows the state after the input. For example, a state transition table for
representation of an FSM the automated door in Figure 18.1 would be:
showing inputs, current state
and next state. Input Current state Next state
Button pressed Door closed Door open
Button pressed Door open Door closed

The table for the ticket machine in Figure 18.2 would be:

Input Current state Next state

Money inserted S0 S1
Button pressed S1 S2

147
 The table for processing the letters in Figure 18.4 would be:

Input Current state Next state

a S0 S1
b S1 S2
c S1 S4
a S1 S4
b S2 S1
KEYWORDS c S2 S3
Mealy machine: a type of finite a S2 S4
state machine with outputs. b S0 S4
Cipher: an algorithm that c S0 S4
encrypts and decrypts data, also
a S3 S4
known as code.
b S3 S4
Shift cipher: a simple
substitution cipher where the c S3 S3
letters are coded by moving a S4 S4
a certain amount forwards or b S4 S4
backwards in the alphabet.
c S4 S4

A/D ● Finite state machines

A level only
with outputs
S0 B/E
Some finite state machines will produce output values based on the
input values. An example of this is a Mealy machine, named after the
man who invented it. An example of an application of a Mealy machine
C/F
could be a simple cipher where the letter input becomes transformed
Figure 18.5 State transition into another letter. Figure 18.5 shows a simple three-letter shift cipher,
diagram with outputs
where A becomes D, B becomes E and so on.
18 Finite state machines

1/1
This is a simple example that shows the concept of the Mealy
machine where the current state is transformed to a new state with
S1
the output being shown. Mealy machines were originally devised to
define electronic circuits and are commonly used to express bitwise
1/0
operations. For example, Figure 18.6 shows a right arithmetic shift on a
binary value, which will have the effect of halving the value.
S0 1/0 0/1
The state transition table for this would be:

0/0 Input Current state Output Next state

148 S2 0 S0 0 S2
1 S0 0 S1
0 S1 1 S2
0/0
1 S1 1 S1
Figure 18.6 A Mealy machine
performing a right shift 0 S2 0 S2
1 S2 0 S1

Practice questions can be found at the end of the section on

pages 179 and 180.
 FINITE STATE MACHINES WITH OUTPUTS
TASKS
1 Looking at Figure 18.4, which of these are acceptable?
a) caabb
b) bac
c) aaabbccc
d) abc
KEY POINTS e) aabbca
• A finite state machine (FSM) is 2 Draw a state transition diagram and table that evaluates whether a
a concept that shows a device sequence of bits has an even number of zeros.
that stores the current state 3 What is a Mealy machine?
and how the state will change 4 Draw a state transition diagram from the following table:
as the result of an input.
• FSMs are used as a Input Current state Output Next state
conceptual model for 1 S0 A S1
designing and describing 2 S2 B S1
computer systems.
3 S1 C S3
• FSMs can be used to check the
4 S3 D S2
syntax of language including
programming languages. 5 Draw a state transition diagram that will carry out a bitwise
• State transition diagrams are XOR operation.
a visual way of showing how
states change as the result of
an input.
• State transition tables are an STUDY / RESEARCH TASKS
alternative way of showing
how states change as the 1 Draw a state transition diagram and table that flips 0s to 1s within
result of an input. a binary string.
• A special type of FSM called 2 Draw a state transition diagram and table to control the pointer in
a Mealy machine can also a stack.
produce outputs. 3 Research other practical applications of the FSM.

149
 19 The Turing machine
SPECIFICATION COVERAGE
3.4.5 A model of computation
A level only

LEARNING OBJECTIVES
In this chapter you will learn:
• that a Turing machine is a theoretical model for identifying whether a
problem is computable
• how the Turing machine works
• how state diagrams can be used to represent the workings of the
Turing machine
• how a universal machine can be constructed.

INTRODUCTION
The Turing machine is a theoretical model developed by Alan Turing in
1936 as a way of trying to solve what was called ’the decision problem’.
In simple terms, the problem was whether it was theoretically possible
to solve any mathematical problem within a finite number of steps given
particular inputs. Turing developed a theoretical machine that was able
to carry out any algorithm and in doing so essentially produced a model
of what is computable.

It is worth noting that the Turing machine was devised as a concept rather
than as an actual machine and its invention predates microprocessors
and computing as we know it today. Scientists have since created physical
machines according to Turing’s model and software simulations have
also been made.

A Turing machine is a finite state

KEYWORDS Read/write
machine (FSM) with the ability to head
Turing machine: a theoretical read and write data to an unlimited
model of computation. Finite state
tape. It can be visualised as shown machine
Finite state machine (FSM): any in Figure 19.1.
150 device that stores its current
status and whose status can The basics of its operation are:
change as the result of an input. ● The tape is divided into an
Mainly used as a conceptual infinite number of cells. The
model for designing and tape is used as memory.
describing systems. ● Each cell will contain a
Tape
symbol. This could be
a character or number.
Commonly the contents of the
tape are binary digits, i.e. 0s
and 1s, and the blank symbol, Figure 19.1 A Turing machine
 sometimes shown as a . The acceptable symbols are known as the
alphabet.

19 THE TURING MACHINE

KEYWORDS
● The read/write head can either read what is in the cell or write into
Alphabet: the acceptable
the cell. It can also erase the current contents of the cell, effectively
symbols (characters, numbers)
overwriting the contents.
for a given Turing machine.
● The tape can move left or right one cell at a time so that every cell is
Read/write head: the theoretical accessible by the read/write head.
device that writes or reads from ● The machine can halt at any point if it enters what is known as the
the current call of a tape in a halting state, or if the entire input has been processed.
Turing machine.
Despite being invented before computers as we know them now, you can
Halting state: stops the Turing
see that this model sounds very much like a modern PC, with the tape
machine.
representing memory and the cells representing memory addresses. Moving
Start state: the initial state of a the tape through the read/write head will produce sequences of characters,
Turing machine.
which is analogous to a computer executing instructions in a program.
Transition function/rule: a
method of notating how a Turing To represent programs in Turing machines you need:
machine moves from one state ● a start state – the state of the machine at the start of the program
to another and how the data on ● a halting state – the state that will stop the program running
the tape changes. ● an alphabet – this is a list of the acceptable symbols that can go into each cell

State transition diagram: a ● movement – the ability to move the head so that you can read/write to

visual representation of the every cell

transition function of a Turing ● a transition function – indicating what should be written at each cell
machine. and whether to move left or right based on the input read.
Controlling the machine is represented through state diagrams very similar
to the state transition diagrams that we looked at for FSMs. You can
visualise the tape as follows:

® 1 1 1 0 0 ® ®

Read/write head
Figure 19.2 The tape and read/write head

At the moment the read/write head is either reading or writing a 1 in the

current cell. In the examples used in this chapter the read/write head starts
with the left-most non-blank location. Note that the symbols in the other
cells are 0s, 1s or blanks. The arrows indicate that the head can move left
or right.

Figure 19.3 shows a state transition diagram for the transition function of a
Turing machine.

0/0,R 0/0,R
1/1,R
151

S0 S1
1/1,R

/1,R /0,R

SH

Figure 19.3 State diagram to show the operation of a Turing machine

 ● S0 represents the starting state.
● SH represents the halting state.
● This diagram has one other state, S1, although it would be possible to
have as many states as required to represent an algorithm.
● Moving from one state to the next requires a transition function or transition
rule. These are determined by the arrows in the transition diagrams. The
rules are shown on the diagram in the format 1/1,R which means in this
case that if the input symbol is a 1, keep the symbol on the tape as a 1 and
then move the head right. Another example is /0,R which means if the
input symbol is blank, change it to a 0 and move the head right.
● Writing the transition rules effectively creates an algorithm.
It is useful to be able to trace the steps that the machine will go through,
looking at the current state after each movement.
The Turing machine is in state S0 and the input symbol is 1. Therefore the
rule 1/1,R is applied which writes a 1 to the tape, moves the head right and
changes to state S1. The machine will now look like this:

® 1 1 1 0 0 ® ®

Read/write head

We are now on S1 in the state diagram. The rule 1/1,R is applied which writes
a 1 to the tape, moves the head to the right and changes back to state S0:

® 1 1 1 0 0 ® ®

Read/write head

The next step reads a 1, writes a 1, changes to state S1 and moves the head
19 The Turing machine

right. Then the next two steps read a 0, so write a 0, move right and stay in
state S1 so the tape now looks like this:

® 1 1 1 0 0 ® ®

Read/write head

With the machine in this position, we are now in state S1 reading a . The
rule now is to write a 0 to the tape, move right and move to the halting
152 state. The program now stops as the algorithm is complete and the final
contents of the tape are:

® 1 1 1 0 0 0 ®

Read/write head
 This algorithm is an odd parity generator that ensures the number of 1s in
a binary string is odd:

UNIVERSAL MACHINE
● The start point is the left-most non-blank symbol in the binary string.
● Scanning the digits, if there are an even number of 1s then a 1 needs to
be added to ensure that it becomes odd.
● When a blank is reached, if there are already an odd number of 1s, a 0 is
added to maintain this number as odd.
KEYWORD ● The program then halts.
Instruction table: a method of This could be represented by the following instruction table:
describing a Turing machine in
tabular form. State Read Write Move Next state
S0 1 R SH
S0 0 0 R S0
S0 1 1 R S1
S1 0 R SH
S1 0 0 R S1
S1 1 1 R S0

Another way of notating the Turing machine is to show the transition rules
in the following format:
(Current State, Input Symbol) = (Next State, Output Symbol,
Movement)
The transition rules for the odd parity generator therefore could be written
with the following functions:
(S0, ) = (SH, 1, R)
(S0, 0) = (S0, 0, R)
(S0, 1) = (S1, 1, R)
(S1, ) = (SH, 0, R)
(S1, 0) = (S1, 0, R)
(S1, 1) = (S0, 1, R)
Note the use of for a blank cell and the use of L and R for left and
right. Other notation may be used, for example, it is common to use
a B to represent a blank and left and right arrows ( ) to show
movement.

● Universal machine 153

At a theoretical level you can use the Turing machine on any problem that
is computable. The limitation of the Turing machine is that every process
we need to carry out requires its own Turing machine to do it. For a large
program, this could quickly become problematic. You could view this as
 a black box model where you define the inputs, the process carried out, and
the output:

Input Turing Output

machine

If we want to add A and B:

A, B Turing A+B
machine

To multiply A and B:

A, B Turing A×B
machine

Every computation requires its own Turing machine and its own tape on
which to work. However, it is inevitable that you will want to combine
KEYWORD the results of several computations and this is why Turing developed the
Universal machine: a machine concept of a universal machine.
that can simulate a Turing
Rather than defining each individual process within a single machine, the
machine by reading a description
of the machine along with the universal machines takes two inputs:
input of its own tape. ● a description of all the individual Turing machines required to perform

the calculations
● all the inputs required for the calculations.

Descriptions of
machines Universal Outputs

Inputs machine

Figure 19.4 The universal machine

Perhaps the easiest way to think of it is as a series of individual Turing

19 The Turing machine

machines all linked together that can take any input and perform any
calculation defined by any of the component machines.
This is stored on one tape (rather than lots of individual tapes) with one block
of cells containing the instructions and one block of cells containing the
inputs. The result of this is a machine that can simulate any number of Turing
machines with their corresponding inputs and produce a range of outputs.
This is often seen as the earliest form of the stored program concept
(see Chapter 33) where instructions and data are stored in the same place
in memory. This is one of the key principles of modern computing even
154 though it was devised as long ago as 1936. As Turing machines break down
processes to small steps, this equates to many of the other techniques we
have looked at in this section, such as decomposition, where large problems
are broken down until a programmable solution can be found.
The concept of the Turing machine and the universal machine is closely
linked with the concept of computable problems (see Chapter 22) in that
they define what is computable. If it is possible to describe a Turing machine
to solve a problem, then it will be possible to write an algorithm to solve it.
Practice questions can be found at the end of the section on
pages 179 and 180.
 UNIVERSAL MACHINE
KEY POINTS TASKS
• The Turing machine is a 1 Define the components of a Turing machine.
theoretical machine that
2 Why did Alan Turing develop the Turing machine?
is able to carry out any
algorithm and in doing so 3 Why did he develop the universal machine?
essentially produces a model 4 Identify two states that a Turing machine should have.
of what is computable. It 5 Draw a state transition diagram and instruction table and write the
works with a tape of an infinite transition rules (functions) for the following:
length split into cells.
a) Create a counter that starts at 1 and adds 1 each time.
• Each cell has a value in it, b) Perform a bit universion, i.e. change Os to 1s and 1s to Os.
typically a 0, 1 or a blank, but c) Carry out a unary addition in the format: 1 + 1 = 11, or 11 + 1 = 111,
could have any symbols. or 1 + 11 + 1 = 1111.
• The read/write head can move The alphabet will consist of blank, 1 and +.
in any direction along the
6 Choose one of the above and draw a series of diagrams to show the
entire length of the tape.
current state of the tape after each step.
• The read/write head reads
and writes values to the cells.
7 Why are the Turing machine and universal machines still relevant to
modern computing?
• A universal machine is a
machine that can simulate
any other Turing machine by
processing a description of STUDY / RESEARCH TASKS
how the other Turing machine
works, that is, its transition 1 Research the ‘Busy Beaver’ and how it can be solved using a Turing
function, that is stored on the machine.
tape alongside the data that is 2 Find a Turing machine simulator on the Internet and use it on the
to be processed. algorithms described in question 5 above.

155
 20 Regular and context-
free languages A level only
SPECIFICATION COVERAGE
[Link] Regular expressions
[Link] Regular languages
3.4.2 Context-free languages

LEARNING OBJECTIVES
In this chapter you will learn:
• what regular expressions are and how they can be used to define
and search sets
• how regular expressions can be used on text strings
• how to search using strings of regular expressions
• how context-free languages can be used to describe the syntax of
a programming language
• how Backus–Naur Form (BNF) is used
20 Regular and context-free languages

• how syntax diagrams are used.

INTRODUCTION
A regular language is one that can be represented using regular
KEYWORD expressions. Regular expressions contain strings of characters that can
Regular language: any language be matched to the contents of a set allowing you to find patterns in data.
that can be described using They are a powerful tool for searching and handling strings. They also
regular expressions. provide a shorthand definition of the contents of the set.

● Regular expressions
To start with an example, the expression a|b|c is a regular expression, which
KEYWORD means that the set will contain either an ‘a’ or a ‘b’ or a ‘c’. A set is a collection
Regular expression: notation of data that is unordered and contains each item at most once. It is written as
156 that contains strings of follows showing the name of the set and the contents within the brackets:
characters that can be matched
● alphabet = {a, b, c, d, e, f, g, ...}
to the contents of a set.
● integers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}

The contents of a set are typically characters and numbers and a regular
expression can be used to define and search the set. There are regular
expressions for handling text strings (covered in this chapter) and for
handling numbers (covered in the next chapter). There is also a relationship
between regular expressions and finite state machines in that all regular
expressions can be expressed as state transition diagrams for an FSM and
vice versa, and there is more on this in this chapter.
Common regular expressions are shown in Table 20.1.

REGULAR EXPRESSIONS
Table 20.1 Regular expressions with examples of outputs

Regular expression Meaning Strings produced

a|b|c a or b or c a
b
c
abc a and b and c abc
a*bc Zero or more a followed bc
by b and c abc
aabc
aaabc
(a|b)c a or b and c ac
bc
a+bc One or more a and b and c abc
aabc
aaabc
ab?c a and either zero or one b ac
and c abc

You can see that there may be many permutations of strings that might be
produced by a regular expression. For example, a*bc could produce a text
string with an infinite number of the letter ‘a’ at the beginning, but it would
have to end in bc.
Consider the following examples:
● (a|b|c)d*e would produce the following possible strings: ade, ae, be, bde,

ce and cde. There could in fact be an infinite number of the letter ‘d’ but
it would have to end in an e.
● (a+(b|c))d would produce abd or aabd or aaabd (and so on with the

preceding ‘a’) or the ‘b’ could be replaced by a ‘c’ in each string.

Perhaps the easiest way to understand all the permutations is to produce a
state transition diagram.
a

b c
S0 S1 S2

a, b
c a, b, c

S3

157

a, b, c
Figure 20.1 FSM to represent the regular expression a*bc

Figure 20.1 shows that ‘a’ can repeat any number of times and it must then
be followed by ‘b’ and a ‘c’. S2 represents the accepting state, so the last
letter produced by this expression has to be a ‘c’.
If you consider the expression a(bc)* it means that ‘a’ will be the first letter
followed by any number of ‘bc’. So ‘a’ would be one outcome as would abc
or abcbc or abcbcbc. This could be represented as a state transition diagram
as shown in Figure 20.2.
 b

a
S0 S1 S2

c
c
b, c a, b

S3

Figure 20.2 FSM to represent the regular expression a(bc)*

Here the string must start with an ‘a’ and end with a ‘bc’. It is not possible
for the outcome to be a ‘c’ on its own.
It is also possible to write the regular expression from the state transition
diagram.
Consider the FSM in Figure 20.3; this diagram can only produce an ‘a’ or ‘b’
followed by a ‘c’, which would be written as (a|b)c.
a

c
S0 S1 S2
b

a, b
c a, b, c

S4
20 Regular and context-free languages

Figure 20.3 FSM to represent the regular expression (a|b)c

● Searching strings
The power of regular expressions in this context is in using them to
identify patterns in strings. Common uses include data validation,
find and replace or searching for files with a particular file name. Most
programming languages support the use of regular expressions and
although the syntax and delimiters used may vary, the underlying
principle remains the same. There is a standard set of expressions
defined by POSIX.
Table 20.2 Standard expressions

Expression Definition Example

. Effectively a wildcard and matches .ole would match to mole,
158 any character hole, vole etc.
[] Matches to a single character within [mh]ole would match to mole
the brackets and hole but not vole.
[^] Matches to any character except [^ m]ole would match to hole
those in the brackets and vole but not mole.
* Matches the preceding characters m*ole would match ole,
zero or more times mole, mmole, mmmole, etc.
{m,n} Matches the preceding character at a{2,5} would match to aa,
least m but no more than n times aaa, aaaa and aaaaa.
 The following is an extract of Visual Basic-based pseudo-code showing how
a search string could be implemented using a regular expression to identify

CONTEXT-FREE LANGUAGES
numbers 0 to 9:
‘Set a variable that contains the search string
Dim myString As String = "Software Version 3"
‘Define the alphabet
Dim regex = New Regex("[0-9]")
‘Set a variable to store the matching characters
Dim match = [Link](myString)
‘Where a match is found between the alphabet and
the search string, write the matching characters to
the screen
If [Link] Then
[Link]([Link])
End If
This code would produce the output “3”. To use this code you will need to
import [Link] into your program.

● Context-free languages
A context-free language is a method of describing the syntax of a
KEYWORD language used where the syntax is complex. As we saw in the previous
Context-free language: an chapter, one of the applications of state transition diagrams is to check that
unambiguous way of describing the syntax rules of a language are being followed. The technique can be
the syntax of a language useful
used to check that different components of the code are in the correct place.
where the language is complex.
Regular expressions map directly to state transition diagrams. However,
there are situations where the grammar used within a language is too
complex to be defined by regular expressions. The key problem with
regular expressions is that they only work when matching or counting
other symbols in a string where there is a finite limit.
For example, consider a binary palindrome. This is a binary number that is the
same backwards as it is forwards, e.g. 01110. If you think about a palindrome
in normal language, for example, ‘anna’ or ‘level’, it would not be possible to
create a regular expression that describes the syntax as there is no regular
expression that can describe how each letter is used. Similarly with binary
palindromes, there is no regular expression for the patterns of zeros and ones.
Where the counting and matching is infinite, a context-free language is 159
needed. Context-free languages can also support notation for recursion
and are sometimes a clearer way of defining syntax even where regular
expressions can be used.
KEYWORD Backus–Naur Form (BNF)
Backus–Naur Form (BNF):
The concept of context-free languages is that rules can be written that
a form of notation for
define the syntax of the language which are completely unambiguous and
describing the syntax used by a
programming language. that can work beyond the current state. One method for doing this is to use
Backus–Naur notation, known as BNF (Backus–Naur Form).
 In common with regular expressions, BNF produces a set of acceptable
KEYWORDS strings, which effectively describe the rules of the language. It uses a set of
rules that define the language in the format:
Set: a collection of symbols in
any order that do no repeat. <S> ::= <alternative1> | <alternative2> |
Terminal: in BNF, it is the final <alternative3>
element that requires no further <alternative1> ::= <alternative2> | <alternative4>
rules.
<alternative4> ::= terminal
BNF works by replacing the symbol on the left with the symbols on the
right until the string is defined. The idea is to keep going until you reach a
terminal, which is a rule that cannot be broken down any further. In the
example above:
● each symbol or element is enclosed within angle brackets <>
● the ::= means ‘is replaced with’ and defines the rule for the symbol
● each symbol needs to be split down further until you reach a terminal.

To define integers, a BNF expression may look like this:

<integer> ::= <digit> | <digit> <integer>
<digit> ::= 0|1|2|3|4|5|6|7|8|9
This shows that an integer is defined as either a digit or a digit followed
by another integer. A digit is defined as the numbers 0 to 9 and this is a
terminal as there is no further rule needed to define digits. This expression
would be recursive as integer is defined in terms of itself.
Consider a more complex example, for customer details held in a database:
20 Regular and context-free languages

<customerdetails> ::= <name> <address>

<name> ::= <title> <firstname> <lastname>
<address> ::= <housenumber> <streetname> <town>
<county> <postcode>
...
<housenumber> ::= <integer>
<integer> ::= <digit> | <digit> <integer>
<digit> ::= 0|1|2|3|4|5|6|7|8|9
...
This example shows how BNF can produce simple rules, which can be
written as:
● customer details must be made up of name and address.
● name must be made up of title, first name and last name.
160
address must be made up of house number, street name, town, county
and postcode.
house number must be made up of an integer.
● integer must be made up of a digit or another integer.

This is only a partial BNF definition and could be continued to further split
down the name into a series of acceptable characters, or the postcode into a
series of letters and numbers and so on.
 Syntax diagrams

CONTEXT-FREE LANGUAGES
KEYWORD Another way of representing BNF expressions or any kind of context-free
Syntax diagram: a method language is a syntax diagram. These map directly to BNF and use the
of visualising rules written in symbols:
BNF or any other context-free
language. text Represents a terminal element.

Represents a non-terminal element and therefore will have another syntax

text
diagram that breaks it down into more detail.

text
Represents a non-terminal element that may be used more than once.

Figure 20.4 Syntax diagram symbols

Syntax diagrams are modular so there are likely to be many syntax

diagrams required to represent a whole language. Each has an entry and
exit point to identify the start and end of each particular part. For example,
an integer would be represented as shown in Figure 20.5.

Integer
digit

integer

Digit
0
1
2
3
4
5
6
7
8
9

Figure 20.5 Syntax diagram to represent an integer

Figure 20.6 shows how you could break the customer details example into a
series of syntax diagrams. This is just a partial diagram to demonstrate how
to get to a terminal. In this case there are a series of non-terminal stages
before you arrive at the terminal element, which are the actual characters 161
that comprise a person’s name.
 Customer details
Name Address

Name
First name Last name

First name
Character

Character
A
B
C
D

Figure 20.6 A syntax diagram for customer details

A worked example will help to explain this.

Suppose you wanted to create rules for a password that stated that for each
character within the password the user must select either a capital letter, a
lower case letter, a special character or a digit in any order. The BNF may
look like this:
<character> ::= <uppercase>|<lowercase>|<number>|<spe
cialcharacter>
<uppercase> ::= "A" – "Z"
20 Regular and context-free languages

<lowercase> ::= "a" – "z"

<number> ::= 0|1|2|3|4|5|6|7|8|9
<specialcharacter> ::= *| - | _ | % | ^
Note that we have reached a terminal on all our elements.
Suppose we wanted to insist that the first character was a capital letter
followed by any combination of other characters. The syntax diagram
would look like Figure 20.7.
Password
Upper
case
Upper
case

Lower
case

162 Number

Special
character

Figure 20.7 Syntax diagram to represent the creation of a valid password

Practice questions can be found at the end of the section on

pages 179 and 180.
 CONTEXT-FREE LANGUAGES
TASKS
1 Explain the difference between regular expressions and context-free
languages.
2 Identify two text strings that would be acceptable for the following
regular expressions:
a) a|b+c
b) (a|b)c*
KEY POINTS c) a*b*c
• Regular expressions are 3 Draw state transition diagrams for the three regular expressions in
a method of defining and question 2.
searching sets of data.
4 Write a regular expression for each of the following descriptions that
• Regular expressions can uses an alphabet of 0 and 1:
be used to handle text and a) must start with a 1
numeric strings. b) any number of 0s followed by any number of 1s
• A regular language is one that c) any combination of 0s and 1s.
uses regular expressions.
5 Use BNF to define the syntax of a car registration number in the
• Context-free languages are format LLNN LLL.
methods that can be used
to describe the syntax of 6 Draw a syntax diagram for question 5.
programming languages.
• Backus–Naur Form (BNF) is a
notation for describing the syntax STUDY / RESEARCH TASKS
of a programming language in
an unambiguous way. 1 Use BNF to try and explain some of the rules of constructing a
sentence using the English language.
• Syntax diagrams are a method
of visualising the syntax of 2 Research Extended Backus–Naur Form (EBNF).
a particular programming 3 Look into the work of Panini and the Sanskrit language. How does this
language. relate to BNF?

163
 21 Maths for regular
expressions
A level only
SPECIFICATION COVERAGE
[Link] Maths for regular expressions

LEARNING OBJECTIVES
In this chapter you will learn:
• how sets can be created using set comprehension
• how sets can be represented in a programming language
• what the empty set is and how it is used
• what operations can be carried out on sets
• how sets can be finite or infinite
• what a subset is and how they are created.

INTRODUCTION
In the previous chapter we looked at how to use regular expressions to
define and search strings within a set. In this chapter we will be looking
at how regular expressions can be used on sets of numbers.

● Sets
As a reminder, a set is a collection of unordered values where each value appears
only once in the set. The values in the set are sometimes referred to as elements,
objects or members. The common format for representing a set is as follows:
A = {1, 2, 3, 4, 5}
where A is the name of the set and 1 to 5 are the values or elements within
KEYWORDS it. Any value can be represented in a set. For example:
164 Natural number: a positive ● = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...} where represents natural numbers
whole number including zero. ● = {..., –3, –2, –1, 0, 1, 2, 3, ...} where represents integers.
Set comprehension: see Set
There is more on different sets of numbers in Chapter 27.
building.
Set building: the process of Set comprehension
creating sets by describing them
using notation rather than listing
In the example for A above, the set is defined by listing the actual numbers
the elements. within the set. It is also possible to define the contents or members of a
set using set comprehension. This means that the set is defined by the
properties that the members of the set must have. This is sometimes called
set building.
 For example:

SETS
A = {x | x ∈ x ≥ 1}
where:
● A is the name of the set
● the curly brackets { } represent the contents of the set
● x represents the actual values of the set that will be defined after the pipe |
● the pipe | means ‘such that’, meaning that the equation after the x defines
KEYWORD the values of x
Member: describes a value or ● ∈ means ‘is a member of’
element that belongs to a set. ● is all of the natural numbers, e.g. 0, 1, 2, 3 etc
● means ‘and’
● ≥ 1 means greater than or equal to one.

In this case we have used set comprehension to create a set of values

that are the natural numbers from 1 upwards, which we could show
as {1, 2, 3, 4, ...}. Note the use of the ellipsis (...) to indicate that the
sequence continues.
Let’s look at another example:
A = {x ∈ | x = x2}
In this case x is a real number where the value of x is the same as the value
of x2. There are only two values that meet this criterion, which are 0 or 1.
Therefore A = {0, 1}.
Set comprehension is a powerful tool as it can be used to define complex
sets of values, without having to define every value. It means that the set
can be represented in an efficient and compact form. For example:
A = {2x | x ∈ } would produce the elements {0, 2, 4, 6, 8, ...}
A = {x2 | x ∈ } would produce the elements {0, 1, 4, 9, 16, ...}
Let’s look at an example using binary values. Standard notation for binary
values would be:
∑ = {0, 1}
This shows that the elements of the set of binary values are 0 or 1. To build
a set of all binary strings containing two bits, you could use ∑2 where the 2
indicates two bits. Therefore:
∑2 = {00, 01, 10, 11}
∑3 = {000, 001, 010, 011, 100, 101, 110, 111}
Again this shows how simple notation can be used to define a large number
of elements. In some cases the number of elements may be infinite. For
example: 165

A = {0n1n | n ≥ 1} would produce the set {01, 0011, 000111, 00001111, ...}
representing all binary stings with an equal number of 0s and 1s with the
0s preceding the 1s.
 Representing sets in programming languages
Most programming languages have set-building routines enabling you to
create sets either by entering values or using set comprehension techniques.
For example:
● In Python you can write the code a = set ([0, 1, 2, 3]) where

the contents of the square brackets form the set.. Alternatively, you could
write the code a = set ([x**2 for x in [1, 2, 3]]), which
would produce the set {1, 4, 9}.
● In Haskell you can write the code [1..100], which makes a

list containing the values 1 to 100. This can be combined with

other functions to define a more complex list, for example
[x*2 | x <- [1..100]], will produce a list of the doubles of all the
numbers between 1 and 100.
● In C# you could write the code IEnumerable<int> numbers =

[Link] (0,9) to produce the integers 0 to 9. The code

var evens = from num in numbers where num % 2 == 0
select num; would then extract the even numbers.

The empty set

There is a special set known as the empty set which is represented either
KEYWORD as {} or as Ø. The empty set has no elements. However, it is not to be
Empty set: the set that contains confused with zero. The easiest way to think about it is as a container that
no values.
could contain something, but it is empty.
Consider the following question: How many countries begin with the letter
X? If you tried to put this answer in the container there would be nothing to
put in so you might put a zero in the container. The problem with this is that
the container is no longer empty as we now have one element in it – a zero.
21 Maths for regular expressions

Therefore in scenarios where an operation results in no answer we can use

the empty set. Consider the following operation:
A = {1, 3, 5, 7, 9, ...}
B = {2, 4, 6, 8, 10, ...}
A∩B=Ø
The ∩ represents intersection so this equation is looking for elements that
are in the first set that can also be found in the second set. As there aren’t
any, the answer is represented as the empty set by the Ø symbol.

Finite and infinite sets

We have already seen that some sets may contain a finite number of
KEYWORDS elements, or that they may contain an infinite number of elements. For
166 Finite set: a set where the example:
elements can be counted
● A = {1, 2, 3, 4, 5} is a finite set with five elements
using natural numbers up to a
● A = {1, 2, 3, 4, 5, ...} is an infinite set made up of natural numbers
particular number.
● A = {x | x ∈ x ≥ 1} is an infinite set of natural numbers greater than zero.
Infinite set: a set that is not finite.
Cardinality: the number of Where a set is finite it has cardinality, which means that it can be
elements in a set. counted using natural numbers. It is also referred to as a countable
Countable set: a finite set where set. The cardinality of a set is simply the number of elements in the set.
the elements can be counted We may also refer to this as the size of the set. For example, the first set
using natural numbers. above has a cardinality of five as it has five elements. The empty set has a
cardinality of zero.
 Infinite sets do not have cardinality as we do not know the total size of the
KEYWORDS set. However, for some infinite sets it is possible to go through the process

SETS
of counting the elements, even though you would never reach the end.
Countably infinite sets:
These are described as countably infinite sets as they can be counted off
sets where the elements
can be put into a one-to-one
against the natural (countable) numbers.
correspondence with the set of
natural numbers. Set operations
Cartesian product: combining It is possible to join two or more sets together to create a new set. This is
the elements of two or more sets known as the Cartesian product. For example:
to create a set of ordered pairs. A = {a, b, c}
Union: where two sets are joined
and all of the elements of both B = {1, 2, 3]
sets are included in the joined set. A × B would produce a set of all possible ordered pairs where:
Intersection: describes which ● the first member of A is paired with the first member of B
elements are common to both ● then the first member of A is paired with the second member of B and so
sets when two sets are joined.
on for every member of B
Difference: describes which ● then the second member of A is paired with the first member of B
elements differ when two sets ● the process is repeated until every member of A has been paired with
are joined together.
every member of B.
The resulting set or Cartesian product of the two sets would be: {(a,1), (a,2),
(a,3), (b,1), (b, 2), (b,3), (c,1), (c,2), (c,3)}. This could also be written as:
A × B = {x , y | x ∈ A y ∈ B}
Notice that the cardinality of the output set is always going to be the same
as the product of the two input sets. In this case, A and B both had a
cardinality of three, which means that our output set will have a cardinality
of nine (3 × 3).
When working with two or more sets there are different ways of defining
Figure 21.1 Venn diagram to represent the relationship between the members of the two sets. There are three main
the union of two sets
operations:
● Union: This means joining together two or more sets so that the new

set is a combination of both sets. This can be represented as A ∪ B. For

example, if A = {0, 1, 3, 5, 7, 9} and B = {0, 2, 4, 6, 8} then A ∪ B will be
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Note that the 0 is the only value common to
both sets and will only appear once in the combined set. This could be
represented visually as shown in Figure 21.1.
● Intersection: This means when two sets are joined together, the

Figure 21.2 Venn diagram to represent resulting set contains those elements that are common to both. It can
the intersection of two sets be represented as A ∩ B. For example, if A = {1, 3, 5, 7, 9} and B = {1, 3,
4, 6, 8} then A ∩ B would be {1, 3}. This could be represented visually as
shown in Figure 21.2.
● Difference: This means that when two sets are joined together the 167
resulting set contains elements that are in either set, but not in their
intersection. This can be represented as A   B or A ∆ B. For example,
if A = {1, 2, 3, 4, 5, 6, 7, 8} and B = {2, 4, 6, 8, 10} then the difference
would be {1, 3, 5, 7, 10}. This could be represented visually as shown
in Figure 21.3.
Figure 21.3 Venn diagram to represent
the difference between two sets
 Subsets
Where all of the elements of one set are also contained within another set,
KEYWORDS it is said to be a subset. For example, A = {1, 3, 5, 7, 9, ...} is a subset of
Subset: a set where the elements B = {1, 2, 3, 4, 5, ...} as all of the elements of A are contained within B. This
of one are entirely contained can be shown as A ⊂ B where the symbol means ‘is a proper subset of’.
within the other; can include two The definition of a proper subset is one that has fewer elements than the
sets that are exactly the same. set. In this case, the subset A contains just the odd numbers from the other
Proper subset: where one set is set. Similarly we could say that A ⊂ B where A = {1, 2, 3, 4, 5] and B = {1, 2,
wholly contained within another 3, 4, 5, 6} as there is at least one number in B that is not in A.
and the other set has additional
elements. The notation of a subset (as opposed to a proper subset) is A ⊆ B and
the distinction is that two sets that are the same can be said to be
subsets of one another. For example, where A = {1, 2, 3, 4, 5} and
B = {1, 2, 3, 4, 5} we can say that A is a subset of B because it contains
everything within B.
Practice questions can be found at the end of the section on
pages 179 and 180.

TASKS
1 What is cardinality?
2 Use set comprehension to represent all real numbers greater
than zero.
3 Use set comprehension to define all negative integers.
4 Use set comprehension to define the cube of all natural numbers.
5 Explain why the empty set is not the same as zero.
6 Use examples to explain the difference between union, intersection
21 Maths for regular expressions

and difference when joining two or more sets together.

KEY POINTS 7 Define the Cartesian product that would result from A = {x, y, z}
• A set is a collection of and B = {1, 2}.
unordered, non-repeated data 8 What is the cardinality of a set resulting from the Cartesian product of
items of the same type. A with 8 elements and B with 9 elements?
• Set comprehension is the 9 Use an example to explain a proper subset.
process of building a set using
an expression.
• Programming languages
support set-building STUDY / RESEARCH TASKS
techniques.
• The empty set is a set with no 1 Write code to define sets for:
values in it. a) all rational numbers greater than zero
• Sets can have a finite or b) all negative integers
168
infinite number of elements in c) the cube of all natural numbers.
them. Research other ways in which sets can be joined together including
• Sets can be combined in supersets, power sets and complements.
different ways to create new 2 Find out about ‘Hilbert’s paradox of the Grand Hotel’ to help you
sets. understand the concept of countably infinite sets.
22 Big O notation and
classification of
algorithms
A level only
SPECIFICATION COVERAGE
3.4.4 Classification of algorithms

LEARNING OBJECTIVES
In this chapter you will learn:
• some algorithms are more efficient than others
• how to classify algorithms by their time and space complexity
• how the basic mathematical functions describe time and space
complexity work
• how Big O notation classifies algorithms in terms of their time and
space complexity work
• that some problems are tractable (solvable within a reasonable
amount of time on a computer) and some are intractable (not solvable
within a reasonable amount of time on a computer).

INTRODUCTION
An algorithm is a sequence of steps designed to perform a particular
task. As we have seen, programs are constructed from algorithms, which
may comprise a few lines of code or whole blocks of code, depending
on the complexity of the problem. For example, an A-level project might
have a few hundred lines of code. A typical phone app has around 100 000
lines of code and according to some estimates, the latest version of MS
Office uses around 45 million lines of code. This illustrates that there is
usually a relationship between the size and scope of the problem and the
size and the scope of the code needed to provide a solution.

This chapter looks at how you can classify algorithms by their complexity 169
in terms of how much time code takes to achieve a result and how much
memory it requires. The method of describing the complexity of algorithms
is called Big O notation.

● Classifying algorithms
KEYWORD Faced with a problem, a programmer may come up with different algorithms
Algorithm: a set of instructions that provide a solution. One of the objectives for writing good code is to produce
required to complete a an efficient solution. Efficiency is usually measured in terms of time and space:
particular task.
 ● Time: how long does the algorithm take to run compared to other
algorithms.
● Space: how much space (memory) is required by the algorithm compared
to other algorithms.
The key consideration is what is called input size or problem size. Typically
this is the number of parameters or values that the algorithm will be
working on. For example, a search routine written to work on a dataset
with only a few values may not work as efficiently on a larger dataset with
hundreds of values.
The code below shows a bubble sort which is inefficient as it has to loop
through the whole dataset every time comparing and swapping two
adjacent items on each pass. If there were a million items of data it may
have to go round approximately 1 000 0002 times.
For Loop1 = 1 To NumberOfItems - 1
For Loop2 = 1 To NumberOfItems - 1
‘ if the following name is smaller then swap
If NameStore(Loop2) > NameStore(Loop2 + 1) Then
SwapData = NameStore(Loop2)
NameStore(Loop2) = NameStore(Loop2 + 1)
22 Big O notation and classification of algorithms

NameStore(Loop2 + 1) = SwapData
End If
Next
Next
The code could be made more efficient by checking whether any swaps
have taken place in each pass of the data. If a swap has taken place between
two data items than they do not need to be compared again on the next
iteration of the loop:
Do
SwapData = ""
For Loop2 = 1 To CountTo
If NameStore(Loop2) > NameStore(Loop2 + 1) Then
SwapData = NameStore(Loop2)
NameStore(Loop2) = NameStore(Loop2 + 1)
NameStore(Loop2 + 1) = SwapData
170
End If
Next
CountTo = CountTo - 1
Loop Until SwapData = ""
In this chapter we will look at how to compare algorithms by analysing the
time and space requirements in response to changes in input size.
 ● Functions

BIG O NOTATION
Comparing algorithms uses a technique called Big O notation. This uses
standard mathematical functions. Before we look at Big O, we need to
KEYWORDS understand the functions it uses.
Function: relates each element A function simply relates an input to an output. For example f(x) = x2 is
of a set with the element of an example of a function. It means that you take the input value for the
another set. function, x, and produce an output, which in this case is the squared value
Domain: all the values that of x. The set of values that can go into a function is called the domain and
may be input to a mathematical the set of values that could possibly come out of it is called the codomain.
function. The set of values that are actually produced by the function is called the
Codomain: all the values that may range. It is always the case that the range will be a subset of the codomain.
be output from a mathematical
function. Another important mathematical concept for understanding Big O is that
of permutations. If you consider an item of data such as a text string, or a
Factorial: the product of all
number, there are different ways in which the characters or digits can be
positive integers less than or
equal to n, e.g. 3! is 3 × 2 × 1. put together. For example:
● A word with two letters has two permutations: ‘to’ can be ‘to’ or ‘ot’.
● A word with three letters has six permutations: ‘dog’ can be ‘dog’, ‘dgo’,

‘odg’, ‘ogd’, ‘gdo’ or ‘god’.

● A word with four letters can have 24 permutations. Rather than work

through them the basic formula is that there are four ways to pick the
first letter, followed by three ways to pick the second letter followed by
two ways to pick the third letter and finally one way to pick the last
letter. This could be shown as 4 × 3 × 2 × 1, which gives 24.
● A word with five letters therefore has 5 × 4 × 3 × 2 × 1 = 120

permutations.
This is called the factorial function and can be denoted by n! Where n is
an integer. For our five-letter word, we could show this as 5! which means
5 × 4 × 3 × 2 × 1 = 120.

● Big O notation
Big O notation is a method of describing the time and space complexity
KEYWORDS of an algorithm. It looks at the worst-case scenario by essentially asking
Space complexity: the concept the question: how much slower will this code run if we give it 1000 things
of how much space an algorithm to work on instead of 1? For example, if you had a bubble sort routine that
requires.
compared the first two items of data and swapped them if necessary, then
Input size: in Big O notation the compared the next two items of data and so on, this might work quite quickly
size of whatever you are asking on a list of 10 items. But what if you asked it to sort a list of 1 million items?
an algorithm to work with, e.g.
data, parameters. Big O notation provides a measure of how much the running time
Time complexity: the concept requirements of the code will grow as the magnitude of the inputs changes. 171
of how much time an algorithm Big O calculates the upper bound, which is the maximum amount of time
requires. it would take an algorithm to complete. The notation refers to the order of
growth, also known as the order of complexity, which is a measure of how
much more time or space it takes to execute the code as the input size
increases. The format is a capital letter O followed by a function. All of the
explanations below relate specifically to time complexity, rather than
space complexity.
 Big O notation uses five main classifications:
KEYWORD ● O(1), known as constant time, means that the algorithm will always
Constant time: in Big O notation execute in exactly the same amount of time regardless of the input size.
where the time taken to run an Accessing an array would be an example of this as each element of the
algorithm does not vary with the array is accessed directly by referring to its position. Therefore, it would
input size. not take any longer to access a single element if there were one or ten
million items in the array. Note that O(1) does not necessarily mean that
the code will run quickly, it just means that it will take the same amount
of time (it is constant) regardless of the input.
If you were to represent this as a graph, it might look like Figure 22.1.
This shows that however much the input size increases, the time taken to
run the algorithm remains the same.

Time

O(1)
22 Big O notation and classification of algorithms

Input size
Figure 22.1 Graph to represent constant function

● O(N) represents a linear function and it means that the runtime of the
KEYWORD algorithm will increase in direct proportion with the input size. For
Linear time: in Big O notation example, there could be a relationship where if you input twice as much
where the time taken to run an data, the algorithm will take twice as long.
algorithm increases in direct
This could be represented as y = x where every change in x produces
proportion with the input size.
a corresponding change in y. The linear relationship may be more
complex. Another example of O(N) is y = 2x which means that every
change in x would produce double this change in y. This could be
represented graphically as shown in Figure 22.2.
Time

O(N)

172
Input size
Figure 22.2 Graph to represent linear function

Looping around a list would be an example of this because the code needs
to access every element of the list. If you increase the size of the list the
amount of time taken to carry out the loop will increase by a linear amount.
● O(N2) is an example of a polynomial function and it means that the runtime
of the algorithm will increase proportionate to the square of the input size.
To take a simplified example, let’s say that one item takes 1 second (12). Ten
 items therefore would take 100 seconds (102) and 100 items would take
10 000 seconds (1002). This could be represented as y = x2. This could be

BIG O NOTATION
represented graphically as shown in Figure 22.3.

Time
O(N2)

Input size
Figure 22.3 Graph to represent polynomial function

Iterative or nested statements such as bubble sorts and insertion sorts

are examples of these as the program has to go back through itself again
with each iteration. The following code shows a bubble sort using a loop:
Private Sub btnSort_Click(ByVal sender As System.
Object, ByVal e As [Link]) Handles
[Link]
Dim Loop1 As Integer
Dim Loop2 As Integer
Dim TempStore As String
Dim RowsToSort As Integer
RowsToSort = [Link] - 2
For Loop1 = 1 To RowsToSort - 1
For Loop2 = 1 To RowsToSort - 1
‘ compare each value in the table with the
following value
‘ changing the > operator will sort high
to low
If [Link](Loop2).Cells(0).Value >
[Link](Loop2 + 1).Cells(0).Value Then
‘swap values to move larger values to
later cells
TempStore = [Link](Loop2).Cells(0).
Value 173
[Link](Loop2).Cells(0).Value =
[Link](Loop2 + 1).Cells(0).Value
[Link](Loop2 + 1).Cells(0).Value =
TempStore
End If
Next
Next
End Sub
 ● O(2N) is an example of an exponential function where the runtime
KEYWORDS will double with every additional unit increase in the input size. To
take a simplified example, one item might take 1 second, two items
Exponential time: in Big O
notation where the time taken would take 2 seconds, three items 4 seconds and so on. Ten items of
to run an algorithm increases data would take 512 seconds. This can be expressed as y = 2 x where
as an exponential function of the x is each individual item being input and y represents the time taken.
number of inputs. For example, Obviously the amount of time taken to process each input will start to
for each additional input the time become unworkable. Problems with an exponential order of growth are
taken might double. often referred to as intractable problems, which means that they can’t
Logarithmic time: in Big O be solved with a computer in a reasonable time. There is more on this
notation where the time taken later in the chapter.
to run an algorithm increased
or decreases in line with a

Time
logarithm. O(2N)

Input size

Figure 22.4 Graph to represent exponential function

22 Big O notation and classification of algorithms

● O(logN) represents a logarithmic function which uses an exponent to

raise the value of a base number in order to produce the desired number.
For example, with y = log2x, this means we are using base 2. If x = 8 then
y must equal 3 as you have to multiply 2 by 2 by 2 or 23 in order to get 8.
In base ten, y = log10x, if x = 10 000 then y must equal 4 as 10 × 10 × 10 ×
10 or 104 equals 10 000.
The usefulness of this can be shown by looking at a binary search.
These work by continually splitting the data in half until the item being
searched for is found (see Chapter 9). It is called a binary search as it
splits the data in two each time. Therefore it has a time complexity of
O(log2N) as each subsequent split of the data takes less time as only
half the data is being searched. The number of data items is halving
each time so even large datasets can be searched with a relatively small
number of comparisons:

Table 22.1

Number of data items Number of comparisons needed in a binary search

2 1
174 4 2
8 3
16 4
128 8
65 356 16
1 048 576 20
4 294 967 296 32
 Table 21.1 shows the way in which the size of the input data that can
be searched increases exponentially with each comparison. Therefore

DERIVING THE COMPLEXITY OF AN ALGORITHM

to carry out a binary search of over 4 billion items would only actually
take up to 32 comparisons within the dataset.
This could be represented graphically as shown in Figure 22.5.

Time
O(logN)

Input size
Figure 22.5 Graph to represent logarithmic function

The value of using Big O notation is that you can find the most efficient
solution for your problem. Remember that Big O uses the upper bound so is
a good measure of how scalable your solution is, that is, how efficient it will
be as the input size increases. As a broad rule of thumb:
● An O(1) algorithm scales the best as it never takes any longer to run.
● An O(logN) algorithm is the next most efficient.
● An O(N) algorithm is the next most efficient.
● An O(N2) algorithm is a polynomial and is considered to be the point

beyond which algorithms start to become intractable. Note that the

superscript number could be any value.
● An O(2N) algorithm is the least efficient and considered intractable.

● Deriving the complexity of an algorithm

It is possible to derive the time complexity of an algorithm by looking at the
contents of the code. For example:
● An algorithm that requires no data and contains no loops or recursion,

such as a simple assignment statement or comparison statement, will

have a time complexity of O(1).
● An algorithm that loops through an array accessing each data item once

will have a time complexity of O(N).

● An algorithm with inner and outer loops will be polynomial with

runtime increasing depending on the depth of the nesting and the

KEYWORD number of loops. In this case it will be O(N 2).
Polynomial time: in Big O ● The addition of a loop within the inner loop would alter the polynomial 175
notation where the time taken to time to O(N 3).
run the algorithm is a polynomial ● An algorithm that uses recursion to call itself could have a time
function of the input size, e.g. the complexity of O(a N).
square of the input size.
It is not always easy to work out the precise time complexity of an algorithm as
it may depend on how many times parts of the algorithm may run, based on
the outcome of conditional statements. For example, with an If statement, part
of the algorithm will only need to run if a condition is true. Therefore the actual
number of times that some of the program code executes will depend upon the
data that is input to the algorithm when it is carried out.
 With Big O notation, to describe the complexity of a problem, the usual
practice is to quote the worst-case scenario for the most efficient algorithm.
However, in choosing a suitable algorithm it is possible to make a
comparison between the worst, best and average cases based on time
complexity.
Some common algorithms are known to have certain time complexities as
shown in Table 22.2.
Table 22.2 Common algorithms with time complexity in Big O notation

Complexity Algorithms
O(1) Indexing an array
O(logN) Binary search
O(N) Linear search of an array
O(N2) Bubble sort
Selection sort
Insertion sort
O(2 N ) Intractable problems

● Tractable and intractable problems

A tractable problem is one that is said to be solvable in polynomial time.
KEYWORDS
22 Big O notation and classification of algorithms

In simple terms this means that the algorithm that solves the problem runs
Tractable problem: a problem quickly enough for it to be practical to solve the problem on a computer.
that can be solved in an
acceptable amount of time. Intractable problems are those which are theoretically possible to solve,
Intractable problem: a problem but cannot be solved within polynomial time. The problem may be solvable if
that cannot be solved within an the input size is small, but as soon as the input size increases it is considered
acceptable time frame. impractical to try and solve it on a computer. A classic example is ‘the
Heuristic: with algorithms it is a travelling salesman’ problem, which is primarily a conceptual problem that has
method for producing a ‘rule of been tackled by mathematicians and computer scientists for over 100 years:
thumb’ to produce an acceptable ● A salesman has to travel between a number of cities.
solution to intractable problems. ● The distance between each pair of cities is known.
● He must visit each city just once and then return to his start point.
● He must calculate the shortest route.

On the face of it, there may be a simple solution to this problem, particularly
if there are only a small number of cities to visit. However, as the number of
cities increases, the permutations of routes grow at a much faster rate.
There are many similar problems that involve calculating distances between
pairs of points. For example, some analysis looks at points on a circuit board
in order to optimise data transmission. As we have seen, the time complexity
of a problem is typically concerned with looking at the worst-case scenario,
176 so must consider thousands of points. To date, algorithms have been created
that can calculate the actual shortest distance between around 85 000 pairs
of points. These algorithms have a very large time complexity that go well
beyond polynomial time and are therefore considered intractable.
Faced with intractable problems, programmers often produce heuristic
algorithms. Having accepted that the perfect solution is not possible, a
solution that provides an incomplete or approximate solution is seen as
being preferable to no solution at all. Often this will involve ignoring certain
complex elements of the problem, or accepting a solution that is not optimal.
 Heuristics often uses ‘rules of thumb’ and therefore cannot guarantee
accurate results for every possible set of inputs. Instead they produce results

UNSOLVABLE PROBLEMS
that may be accurate for common uses of the program, but less accurate
where the program is being used with less likely inputs. The objective with
a heuristic algorithm is to produce an acceptable solution in an acceptable
time frame, where the optimum solution would simply take too long.
For example, several heuristic solutions have been developed for the travelling
salesman problem that theoretically enable millions of cities to be considered.
None of these compare every possible pair of cities so they do not create an
actual solution. Instead they produce an approximate solution, which may
well be very accurate. Estimates of some of these methods produce results
that may be within 5% degree of accuracy of the optimum solution.

● Unsolvable problems
Unsolvable problems are those which will never be solved regardless of
KEYWORDS
how much computing power is available either now or in the future and
Unsolvable problem: a problem regardless of how much time is given to solve it. The ‘halting problem’
that it has been proved cannot
is an example of a problem that is proven to be unsolvable. In simple
be solved on a computer.
terms, the halting problem is whether it is possible to make a program to
Halting problem: an example of determine if a program will finish running for a particular set of inputs.
an unsolvable problem where it
is impossible to write a program The question devised by Alan Turing in the 1930s asks whether it would be
that can work out whether possible to write a computer program to solve the halting problem. The
another problem will halt given a conclusion is that the problem is unsolvable, as it is proven that it cannot be done.
particular input.
The halting problem is considered to be one of the first unsolvable problem
ever identified and has led to the discovery of many other unsolvable
problems. This area of computing has led to a general acceptance that there
are some problems which:
● simply cannot be solved by computers (unsolvable problems)
● can theoretically be solved by computers but it is not possible within a

reasonable time frame (intractable problems)

Practice questions can be found at the end of the section on
pages 179 and 180.

TASKS