 how algorithms are represented using flowcharts and pseudocode

 the different programming structures (sequence, selection and repetition)

 the different constructs used in object-oriented programming
 the difference between local and global variables
 the importance of using self-documenting identifiers and annotation
 the importance of using subroutines
 about various string handling, mathematical and logical operations
 about various searching and sorting algorithms
 the importance of testing programs

Specification reference (2.2)

 Use common methods of defining algorithms, including pseudo-code and flowcharts.
An algorithm is a sequence of steps or instructions that are carried out
to solve a problem or perform a task. We can create algorithms using
programming languages, but it is better if we plan our algorithm first.
We can use two methods to plan an algorithm: flowcharts and
pseudocode.
A flowchart is a diagram that we can create to plan and demonstrate the
flow of data in a solution. When creating flowcharts, we use a series of
symbols to represent the different elements of the program; these are:

Symbol Explanation

Start/stop – used to show where the beginning and end of our flowchart is.

Input/output – used to demonstrate where our flowchart will take in an input,

or provide us with an output.

Process – used to show any processes or calculations that are happening in

our flowchart.

Decision – used to demonstrate a decision or choice that needs to be taken in

our flowchart. It will have a ‘yes’ and a ‘no’ path from the decision symbol.

Subroutine – used to show where a subroutine will occur in our algorithm.

Arrow – used to show the flow of data through our flowchart.

Connector - used to connect parts of the same flowchart that are drawn in
different places, such as on different pages

When we create a flowchart, we combine these symbols together in the order in which we want instructions to
occur. We then join the symbols together with an arrow to show the direction of the flow.

GCSE Computer Science Course Companion (Chapter 12) Page 1 of 17 © ZigZag Education, 2018
Let’s take a simple password verification
START
program. This is a program that will ask a user
to set a password and re-enter it to verify they
originally entered the password they were
‘Please enter your
meant to. We want our solution to allow our
password’
user to do the following:
 Input their choice of password
 Re-enter their password ‘Please re-enter your
 Make sure the first password entered is password’
the same as the second password
entered NO
Do passwords ‘Your passwords did not
 Output a message to say whether the match? match. Please try again.’
password has been successfully set or not YES
 Keep asking the user to set their
password until they are successful ‘Your password is now
set’
We have decomposed our problem. We can
now create a flowchart to represent a design for
our solution: END

START
Let’s create another flowchart for part of our earlier problem. We want
to create a program that will calculate the average mark for an exam. We
want our solution to do the following: count = 0

 Allow the user to input the number of marks they want to enter
 Keep a count of the marks entered total = 0
 Keep a total of the marks entered
 Allow the correct number of marks to be entered
 Calculate the average mark ‘How many marks
would you like to enter?’
 Output the average mark

We have decomposed our problem. We can now create a flowchart to

represent a design for our solution: ‘Please enter your mark’

count = count + 1

total = total + mark

is count < number

of marks

average = total/count

output average

END

GCSE Computer Science Course Companion (Chapter 12) Page 2 of 17 © ZigZag Education, 2018
We can also represent a design for an algorithm using pseudocode. Pseudocode is a way of writing a program
in programming-type statements that are not specific to any programming language.

Note there is no single standard for pseudocode, but your exam have specified their preferred standard for
pseudocode, so this is what we will use.

When writing programs in pseudocode we can use the following statements:

Statement Description
set variable = "data" This allows us to declare a variable and assign data to it.
set variable = input("user prompt") This allows the user to input data and assign it to a
variable.
output variable This allows us to provide a user with an output that
gets printed to the screen.
for i = 0 to 3 This allows us to create a counting loop so that we can
output variable perform a set of instructions a set number of times.
next i
while variable == false This allows us to create a condition loop where the
set variable = input("user prompt") condition is checked at the start of the loop.
endwhile
do This allows us to create a condition loop where the
set variable = input("user prompt") condition is checked at the end of the loop.
while variable == true
if variable == 1 This allows us to create selection in our program.
output "1"
We can add multiple selection statements through the
else if variable == 2
use of else if.
output "2"
else
output "0"
end if
set name[3] This allows us to create arrays. The first is a one-
dimensional array, the second is a two-dimensional
set name[3,5] array.

set name[0] = "entry1" We can then assign, amend and extract values from
set name[1] = "entry2" each element in the array.
set name[0, 0] = "entry1"
set name[0, 1] = "entry2"

output name[1]
output name[0, 1]
[Link] These are string manipulation statements. They allow
us to find out the length of a string.
[Link](start, noOfCharacters)
They also allow us to extract sections of characters out
of a string.

GCSE Computer Science Course Companion (Chapter 12) Page 3 of 17 © ZigZag Education, 2018
Specification references (2.2)
 Identify, explain and use sequence, selection and iteration in algorithms and programs.
 Follow and make alterations to algorithms and programs that solve problems using:
- Sequence, selection and iteration
- Input, processing and output
 Write algorithms and programs that solve problems using:
- Sequence, selection and iteration
- Input, processing and output
There are three basic constructs that are the foundations of every program that we create; these are sequence,
selection and iteration:

Construct Description
Sequence The order in which the instructions need to occur in an algorithm is called a sequence. If the
instructions are not carried out in the correct sequence, a program may not have the desired
output. Therefore, we need to carefully consider the order in which instructions should occur
when we are designing an algorithm.
Selection When writing a program, it may be necessary to create a way for the
program to follow different paths. This is often dependent on a question
and a condition. The method for creating different paths in a program is
called selection. The path the program takes will depend on the answer
to the question and the condition.
Repetition Sometimes when we write a program we will need to repeat instructions.
The repetition of instructions is called iteration. We can put the
instructions we would like to repeat inside a loop. We can then set the
loop to repeat a set number of times (a counting loop) or we can set the
loop to repeat until a condition is met, or stops being met (a condition loop).

The sequence of instructions in a program is represented by the order in

which the instructions are written. We also need to represent selection
and iteration in a program.

Selection is used to change the path or flow of data in a program. An

if…else statement is the most common selection statement – this allows us
to check whether a condition is true or false and carry out a different instruction depending on whether it is or
not. They basically follow the logic that if x is true then do y, else do z.

For example:

if name == "me"
output "Hello me!"
else
output "Who are you?"
end if

This program will check if the data stored in the variable ‘name’ is equal to ‘me’. If that is true it will output
‘Hello me!’; if it is false it will output ‘Who are you?’. We then end the statement we are making, allowing the
program to recognise that we have finished our selection and to move on to the next instruction in the
sequence.

GCSE Computer Science Course Companion (Chapter 12) Page 4 of 17 © ZigZag Education, 2018
If we have more than one condition that we want to check, we can use the command ‘else if’ in the statement.

For example:

if name == "me"
output "Hello me!"
else if name == "you"
output "Hello you!"
else
output "Who are you?"
end if

Note: Another way to implement selection is by using switch… case statements. These aren’t specifically
mentioned by your exam board, but an example is given below to show how these work, because when
programming, it is more efficient to use switch…case (where possible) than to use a long list of If statements.

set MeatCount = 0
set FishCount = 0
set VegetarianCount = 0
set meal = input ("What mean would you like to eat?")
switch meal:
case "Meat":
set MeatCount = MeatCount + 1
case "Fish":
set FishCount = FishCount + 1
case "Vegetarian":
set VegetarianCount = VegetarianCount + 1
default:
output "We do not recognise your selection"
end switch

This program is designed to give a user three options for their meal choice: a meat, a fish and a vegetarian
option. Whichever option they choose, it will increment a counter for that meal by one to register their choice.
It also contains a default option. It will choose to follow this option if it cannot find an input that matches one
of the other case options.

Repetition (also known as iteration) is used to repeat instructions in a program.

As mentioned on p.3, this is achieved using loops – either counting loops of
condition loops.

For… next is an example of a counting loop, allowing us to repeat an instruction or a sequence of instructions a
specific number of times.

For example:
Discussion point: This program will output the text ‘Hello
for i = 0 to 5 world!’ six times. Why, does this happen, when we have
output "Hello world!" set the number of loops to stop when i reaches 5?
next i

In the above code, we see a count variable, i.

This is essential for the loop to perform correctly.

We should choose a counting loop when we want to repeat the instructions a set number of times. If we do not
know how many times we want to repeat a set of instructions, we will instead be wanting it to repeat until a
condition is met – in these instances we use a condition loop instead.

GCSE Computer Science Course Companion (Chapter 12) Page 5 of 17 © ZigZag Education, 2018
A while… repeat is an example of a condition loop, allowing us to repeat an instruction or a sequence of
instructions until a condition is true or false. This type of loop is controlled by a condition at the start of the
loop. Below is an example of a while…repeat loop (based on the password verification program from p.2).

set match = FALSE

while match == FALSE
set password1 = input("Please enter your password")
set password2 = input("Please re-enter your password")
if password1 == password2
output "Your password has been set"
set match = TRUE
else
output "Your passwords do not match"
set match = TRUE
end if
repeat

This program will output the statement ‘Your passwords do not match’ until the user inputs the correct
password. While… repeat loop are just one type of condition loops; repeat… until and do… while loops are also
commonly used.

Specification references (2.2)

 Explain why the use of self-documenting identifiers and annotation are important in programs
 Give examples of self-documenting identifiers and annotation
Below is an example of code that uses self-documenting
identifiers as well as annotation. There is also indentation.
In Python, indentation is necessary to make selection and
iteration structures work properly. In other languages, such
as Visual Basic (below), indentation is optional. It is still
used, as it clearly identifies where loops and other structures
begin and end.

Variables have meaningful names

that are self-explanatory

Annotation is added to code, to

explain it in plain English

Some lines (or even entire blocks) of code

are indented. In some languages this is
essential in order for the code to run; in
others it isn’t essential but should be done
anyway to make it more readable

GCSE Computer Science Course Companion (Chapter 12) Page 6 of 17 © ZigZag Education, 2018
With a few exceptions, you can give a variable any name you like.
Programming languages vary, but you generally need to follow these rules:

 No spaces
 Letters and numbers can be combined, but variables should start with a letter
 Reserved words (such as loop, if and else) cannot be variable names

Beyond simply working, they need to make sense to anyone who might read your code (such as other
programmers or teachers). Your variable names need to have a clear purpose that can be seen by just looking
at the name of the variable.

Good example Bad example Explanation

Single letters are often used to keep track of how many times a loop
loopCount x
has run, but they are not self-documenting.
Ignoring the fact that ‘input’ is a reserved word in some languages,
levelInput input this is not a meaningful enough name, as the user might input
several things as the program runs.
Nobody wants variable names to fill up the screen, but a longer-than-
player1Score p1s average variable name is less of a problem than a variable name that
has a purpose you can’t remember.

Also known as ‘comments’, annotation spells out, in English, what your code does. Different languages can be
annotated in different ways, but all languages provide some facility for annotation.

Language Annotation
Python #Put a hash sign at the start of the line

Visual Basic 'Put an apostrophe at the start of the line

Anything can be written in the annotation. Using the symbol that identifies comments in your programming
language is how you tell the computer to ignore what you type next. The computer will recognise that you are
marking some text as being ‘not code’ and it will simply skip it.

Specification reference (2.2)

 Identify and explain constructs in object oriented programs
Using object oriented languages, objects are programmed instead of actions. Object-oriented programming
uses the following concepts:
 Objects – each object is a computer representation of a real-world thing. A library program, for
example, might contain millions of ‘book’ objects
 Classes – each class is a template for an object, specifying attributes and methods that belong to each
object. The library program would likely contain only one ‘book’ class, using which many ‘book’ objects
would be created
 Methods – subroutines that belong to a particular class, and that can be run on any object created from
that class. The ‘book’ class, for instance, might have a method called ‘borrow’.
 Attributes - variables that belong to a particular class. Attributes in a ‘book’ class would include the
author, the title and perhaps the number of pages

GCSE Computer Science Course Companion (Chapter 12) Page 7 of 17 © ZigZag Education, 2018
Specification reference (2.2)
 Identify, explain and use subroutines in algorithms and programs.
Examine the following program. It asks for three people’s names and greets them:
set name1 = input("What is your name?")
output "Hello " + name1 + "!"
set name2 = input("What is your name?")
output "Hello " + name2 + "!"
set name3 = input("What is your name?")
output "Hello " + name3 + "!"

This program could be improved, as code is repeated unnecessarily. What if you wanted to change the greeting
message? You would then have to change each greeting, making extra care that they are the same.
Instead we can use subroutines. These are sequences of instructions that we need to use on regular occasions
in our programs. We then just need to refer to the name we give to the subroutine when we want to use the
particular set of instructions.
For instance, we could write a subroutine:

Declare greet
set name = input("What is your name?”)
output "Hello " + name + "!"
End subroutine

Then our code in the example above can be reduced to:

for count = 1 TO 3
call greet
next

Re-using code in this way produces neater, more understandable programs that are less prone to
errors. Not only this, but when code needs to be altered, it only needs to be done in one place.

Specification reference (2.2)

 Identify, explain and use local and global variables in algorithms and programs.
We say that a variable is either local or global. A global variable is one
that is recognised throughout the whole of our program. If we use the
variable name, it will recognise it anywhere in the program and use the
data that is stored in it at any point in our program.

A local variable is one that is created inside of a subroutine and therefore

not recognised by the program outside it.

set x = 1 In the example on the left, the program initialises a global variable, and declares a
subroutine that changes the variable to 2. It calls the subroutine and prints the value
Declare f
of the variable x. One might assume that x is now equal to 2, however the x inside
set x = 2
the subroutine f is a local variable, so it is different from the global variable x. The
end subroutine
value that is printed is therefore 1.
call f
output x It is good practise to treat each variable as local in your code. Without this, checking
your code typically becomes harder, as variables can be in any location. Global
variables can also cause problems when multiple people are working on the same
project, when great care must be taken to not use the same identifiers.

GCSE Computer Science Course Companion (Chapter 12) Page 8 of 17 © ZigZag Education, 2018
Specification reference (2.2)
 Identify, explain and use routines for string handling in algorithms and programs.
Arithmetic operators work on numbers. What would happen if why tried to divide a string by a character?
The most likely thing to happen would be an error – as this operation is not defined on strings and characters.
Other data types have operations unique to themselves. For example, inserting data into an array is an
operation. In particular you should know how to manipulate strings and characters.
Suppose we have the values “Bob” and “Steve” assigned to the variables name1 and name2 respectively:

Command Description Example Output

LEN (length) Returns the number of characters that are in the LEN(name1) 3
string. This will include any spaces.
UPPER Changes all the characters in the string to upper case. UPPER(name2) STEVE
LOWER Changes all the characters in the string to lower case. lower(name1) bob
POSITION Selects a particular character in the string. POSITION(name2, 3) e
SUBSTRING Selects a particular part of a string. It starts at the SUBSTRING(name,2,3) ob
place in the string set by x and selects the next
number of characters set by y.
+ (concatenation) Concatenation joins two strings together. name2 + name1 SteveBob

Note how + is used for addition in numbers, and concatenation in strings. This is why you need to be careful
when using + with different data types – what is the result of a string + number?

In most languages the number is converted to a string, so “ABC” + 4 would equal “ABC4”, but in the
programming language Python for example, you must convert the number to a string or an error will occur.

This is where string conversion operations are useful.

Command Description Example Output

INT Converts a string to an integer. INT(“2016”) 2016
REAL Converts a string to a real. REAL(“3.141”) 3.141
STRING Converts a real/integer to a string. STRING(1.234) “1.234”

There are even operators specific to characters (and not strings), such as character conversion, which converts a
letter into its number representation (see Chapter 3). Let chr1 ← ‘b’.

Then we can manipulate it using the following code:

Command Description Example Output

ASC Conversion from character to ASCII code ASC(chr1) 98
CHR Conversion from ASCII code to character CHR(98) ‘b’

GCSE Computer Science Course Companion (Chapter 12) Page 9 of 17 © ZigZag Education, 2018
Specification reference (2.2)
 Identify, explain and apply computing-related mathematical operations in algorithms and programs.
 Identify, use and explain the logical operators AND, OR, NOT and XOR in algorithms and programs.
It is essential that computer programs are able to manipulate data that we input into our programs. Arithmetic,
relational and Boolean operations help us to do so.

There are many arithmetic operators that we need to understand in order to effectively use them in programs –
with these operators we can manipulate numbers:

Operator Description Example

+ Addition 1+2=3
– Subtraction 2–1=1
/ Division 6/3=2
* Multiplication 6 * 3 = 18
Exponential (^) Repeated multiplication 2^3 = 8 (2 * 2 * 2 = 8)
Remainder (MOD) The remainder left over when a number is divided by another 10 MOD 3 = 1
Integer division (DIV) The number of times a number can be subtracted by another 10 DIV 3 = 3

DIV and MOD are both operators that you would have learnt when first learning division 1
(without going into fractions). One way to think about it is using bins.
3.
Suppose we want to calculate 7 DIV 3 and 7 MOD 3.
 Suppose the bin has a capacity of 7 units, and each item we put in uses up 3 units.
3.
 Therefore we can fit 2 items into the bin, and there is 1 unit of free space remaining.
 So 7 DIV 3 is equal to 2, and 7 MOD 3 is equal to 1.

Relational operators are useful for indefinite iteration – you can check when a value is equal to / less than, etc.
a certain value using a statement that evaluates to true or false.

Operator Description Example

== Is equal to – this can have a true or false outcome 1 == 1 would be True
<> Is not equal to – this can have a true or false outcome 1 <> 1 would be False
< Is less than – this can have a true or false outcome 4 < 5 would be True
> Is greater than – this can have a true or false outcome 4 > 5 would be False
<= Is less than or equal to – this can have a true or false outcome 4 <= 4 would be True
>= Is greater than or equal to – this can have a true or false outcome 4 >= 5 would be False

Boolean operators can be used to join conditional statements together to form ‘complex conditions’.

Example Description
A AND B True if both statement A AND statement B are true
A OR B True if statement A OR statement B (or both) is true
A XOR B True if statement A OR statement B (but not both) is true
NOT A True if statement A is false

GCSE Computer Science Course Companion (Chapter 12) Page 10 of 17 © ZigZag Education, 2018
 Example – Bus tickets
Free travel should be given to those over the age of 75, or if the traveller
already has a ticket. Otherwise they should be charged £4.

if age > 75 OR traveller_has_ticket = true

set ticket_price = 0.00
else
set ticket_price = 4.00
end if

Specification reference (2.2)

 Describe the characteristics of merge sort and bubble sort algorithms.
A sorting algorithm is one that is designed to sort a set of data into order (either increasing or decreasing; we
will always use increasing in the examples). There are various ways in which we can sort a data set into order;
the two methods we need to know are a bubble sort and a merge sort.

A bubble sort is the simplest sorting algorithm to understand. A bubble sort

starts at the beginning of a list and first of all checks the first item against the
second item.
If the first item is greater than the second item, the algorithm knows they are
not in order, so it swaps them. If the first item is less than the second item, it
just leaves them as they are.
It then moves onto the second item and checks this against the third item in
the list. If it is greater than the third item, it swaps them, otherwise it leaves them as they are, and so on. It
will go all the way through the data set and then start again at the beginning to do the same thing again. This
is called passing through the data. It will repeatedly pass through the data until it makes no changes to the
data; it then knows they are in order.
Suppose we want to sort the following list:

10 25 31 15 85 69

We first of all look to see whether 10 is greater than 25. It is not, so they stay as they are.

.10. .25. 31 15 85 69

We then look to see whether 25 is greater than 31. It is not, so they stay as they are.

10 .25. .31. 15 85 69

We then look to see whether 31 is greater than 15. It is, so we swap them.

10 25 .15. .31. 85 69

We then look to see whether 31 is greater than 85. It is not, so they stay as they are.

10 25 15 .31. .85. 69

We then look to see whether 85 is greater than 69. It is, so we swap them.

10 25 15 31 .69. .85.

GCSE Computer Science Course Companion (Chapter 12) Page 11 of 17 © ZigZag Education, 2018
This completes our first pass through the data. We can now begin a second pass.

.10. .25. 15 31 69 85

10 .15. .25. 31 69 85

10 15 .25. .31. 69 85

10 15 25 .31. .69. 85

10 15 25 31 .69. .85.

In that pass the numbers 15 and 25 were swapped. Even though we can see that the list is now in order, the
algorithm does not yet know this. It will make one more pass of the data where it will not need to make any
changes, so it will then recognise the data is sorted.
We can write an algorithm in pseudocode to represent a bubble sort:

array [10,25,15,31,69,85]
length = [Link] – 1
set swapped = true
while swapped == true
set swapCount = 0
for n = 0 to length – 2
if array[n] > array[n+1]
swap(array[n], array[n+1])
set swapCount = swapCount + 1
end if
next n
if swapCount == 0
set swapped = false
end if
end while

A merge sort is an example of a Computer Science technique called ‘divide and conquer’. It can be a more
efficient sorting algorithm as it makes the lists smaller, so they become easier to sort.

A merge sort works by dividing a list in half repeatedly, till it has a set of lists that have one item in them. It
then merges together each list till it has ordered the whole list again. We can use our original list.

10 25 31 15 85 69 75 21 19 6

10 25 31 15 85 69 75 21 19 6

10 25 31 15 85 69 75 21 19 6

10 25 31 15 85 69 75 21 19 6

10 25 15 31 85 69 75 19 21 6

10 25 15 31 85 6 19 21 69 75

6 10 15 19 21 25 31 69 75 85

A merge sort is normally the quickest way of sorting a list. However, it is very difficult to code so you are highly
unlikely to ever need to know how to recognise this in an exam. You mainly need to know the process of how a
merge sort works.

GCSE Computer Science Course Companion (Chapter 12) Page 12 of 17 © ZigZag Education, 2018
Specification reference (2.2)
 Explain and use linear and binary search algorithms.
A searching algorithm is one that is designed to look through a data set and find
a particular item of data. When a data set is very large, running into hundreds
and thousands of entries, manually trying to find a particular item of data can be
time-consuming. A searching algorithm will perform this function for us.

There are two types of searching algorithm that you need to know:
these are linear search and binary search.

A linear search is a simple sequential search of a data set. The algorithm

will start at the beginning of the data set and moves through each data
item one by one. It will do this until it finds the data item it has been set
to look for, or it reaches the end of the data set without finding a matching
data item.
If we had a data set of numbers and we wanted to find a particular number
in the data set we could use a linear search; for example:
We have the following data set of numbers.

10 25 31 15 85 69 75 21 19 6

We want to search the data set to see whether the number 85 appears in it. We start by comparing 85 to the
first number in the data set.
Is 85 = 10?

10 25 31 15 85 69 75 21 19 6

85 is not equal to 10, so the algorithm will move on to the next item.
Is 85 = 25?

10 25 31 15 85 69 75 21 19 6

85 is not equal to 25, so the algorithm will move on to the next item.
Is 85 = 31?

10 25 31 15 85 69 75 21 19 6

85 is not equal to 31, so the algorithm will move on to the next item.
Is 85 = 15?

10 25 31 15 85 69 75 21 19 6

85 is not equal to 15, so the algorithm will move on to the next item.
Is 85 = 85?

10 25 31 15 85 69 75 21 19 6

Yes, it is! The algorithm will stop here as the data item 85 is found.

GCSE Computer Science Course Companion (Chapter 12) Page 13 of 17 © ZigZag Education, 2018
We can write an algorithm in pseudocode to represent a linear search for the data set:

set position = 0
array [10,25,31,15,85,69,75,21,19,6]
set length = [Link]
set number = input("What number would you like to find?")
while position < length AND list[position] != number
set position = position + 1
end while
if position >= length
output "That number is not in the list"
else
output "We have found your number!"
end if

A binary search is another type of searching algorithm. We mostly use a binary searching algorithm when we
have a list of data that is in order. A binary searching algorithm works by dividing a list in half and looking at
the item in the middle. If when the list is split there is an even number of items on each side, we look at the
first item on the right-hand side.
If we order the list of number we used previously, we can use a binary search to find a particular number.
We had the following set of numbers:

10 25 31 15 85 69 75 21 19 6

If we order them, we will have:

6 10 15 19 21 25 31 69 75 85

We can search the data again to see whether the number 85 appears in it. We start by dividing the data set in half:

6 10 15 19 21 25 31 69 75 85

We have an even number of items, so we look at the data in the first position at the right-hand side. We check to
see whether 85 is equal to this number first. 85 is not equal to 25, so we have not found it. We then check whether
85 is greater than 25. It is, so we can discard the list on the left-hand side and only use the one on the right.

25 31 69 75 85

We then divide this list in half:

25 31 69 75 85

This time we do have an odd number and therefore have a central number. We check this first to see whether
we have found 85. 85 is not equal to 69, so we have not found it. We then check whether 85 is greater than
69. It is, so we can discard the list to the left-hand side and only use the one on the right.

75 85

We then divide this list in half:

75 85

GCSE Computer Science Course Companion (Chapter 12) Page 14 of 17 © ZigZag Education, 2018
We have an even number of items, so we look at the data in the first position at the right-hand side. We check
to see whether 85 is equal to this number first. It is! So we have found 85 in the list of data.
In a binary search, the item at the start of the list is called the lower bound, the item at the end of the list is
called the upper bound, and the item in the middle of the list is called the midpoint. The upper bound and
lower bound will move in the list as we keep dividing it in half.
We can write an algorithm in pseudocode to represent a binary search for the data set:

array [6,10,15,19,21,25,31,69,75,85]
set length = [Link]
set number = input("What number would you like to find?")
set lowerBound = 0
set upperBound = length – 1
set match = false
while match == false AND lowerBound != upperBound
set midPoint = round((lowerBound + upperBound)/2)
if array[midPoint] == number
output "We have found your number!"
set match = true
else if array[midPoint] < number
set lowerBound = midPoint + 1
else
set upperBound = midPoint – 1
end if
end while

You need to be able to recognise a searching or sorting algorithm from a set of code. You may be given the
algorithm and have to describe what it does.

Specification references (1.9, 2.2)

 Explain different ways of protecting software systems during design, creation, testing and use.
 Explain how an algorithm or program works and evaluate its fitness for purpose in meeting
requirements.
 Evaluate the efficiency of an algorithm or program using logical reasoning and test data.
During the creation of our program, and also when we have finished, we should be
carrying out regular testing. When we test our program, we are checking that it
does not contain any errors and that it works in the way that we want it to. The
more testing we can carry out on our program, the less likely it is to break in the
future due to a user encountering an error that had not previously been discovered.
When we carry out anything, we must make sure testing is destructive. We must
actively try to break our program to account for misuse. This misuse is not
always done on purpose – it might be the case that someone is using the
program for the first time and doesn’t know how to use it properly.
This will mean not just entering the data that an input should accept, but testing
that it does not accept any other kind of data that we do not want it to accept.
For example, let’s consider the following input:
set age = INT( USERINPUT )

We have created an input that is limited to accepting only integer data. We will want to test whether the input
accepts data that is of the data type integer (normal data), but we will also need to check that the input rejects
real data types or any string data types (erroneous data).

GCSE Computer Science Course Companion (Chapter 12) Page 15 of 17 © ZigZag Education, 2018
Therefore, we may test it with the following data:

Test number Test description Test data Test type Expected outcome
Testing that the input for the age
1 16 Normal Data will be accepted
variable accepts an integer data type
Testing that the input for the age
2 10.2 Erroneous Data will be rejected
variable rejects a number that is real
Testing that the input for the age
3 variable rejects a character that is a A Erroneous Data will be rejected
letter
Testing that the input for the age
4 hello Erroneous Data will be rejected
variable rejects a string of characters
Testing that the input for the age
5 variable rejects a character that is a ! Erroneous Data will be rejected
symbol

This selection of data thoroughly tests our input, making sure that it should only accept
data that is an integer. We have recorded our testing in a testing table.
You will also need to test the logic of your program and test to
see whether the design requirements have been met – this is
where the final type of data, called boundary data, needs to be
tested. This is data that falls on the boundary of what is valid
data and what is not.
For instance, you may have a maximum age of 100, so you would need to check that the program functions
when the age is set to 100. Similarly, it is impossible to be a negative number of years old, so you should check
what happens when you set the age to –1, or 0.
These checks can stop buffer overflows and ensure that people are not granted too many permissions on a
system. Both of these problems give more access to a computer system than is required, meaning that any
malicious user may be able to access private data.

Discussion point: Why do you think it is important to check data on the boundary of what is valid?

GCSE Computer Science Course Companion (Chapter 12) Page 16 of 17 © ZigZag Education, 2018
 i

 An algorithm is a sequence of steps or instructions that are carried out to solve a problem or perform a
task. We can use two methods to plan an algorithm: flowcharts and pseudocode.
 There are multiple ways of writing an algorithm, some being more efficient that others. When writing
algorithms the scenario needs to be considered as this might affect how you proceed.
 A searching algorithm is one that is designed to look through a data set and find a particular item of data.
There are two types of searching algorithm that you need to know: linear search and binary search.
 A linear search is a simple, sequential search of a data set. A binary searching algorithm works by
repeatedly dividing a list in half until it finds the item of data.
 A sorting algorithm is one that is designed to sort a set of data into order. The two methods we need to
know are bubble sort and merge sort.
 A bubble sort starts at the beginning of a list and compares pairs of items, positioning the greater after the
lesser.
 A merge sort works by dividing a list in half repeatedly until it has a set of lists that each contains one
item. It then merges each list until it has ordered the whole list again.

 There are three main programming constructs: sequence, selection and iteration.
 We may need to manipulate the strings of data that we store in a program, extracting sections from them
and joining strings together.
 We can store in a subprogram sections of instructions that we may want to use in a program.
There are two main types of subprogram: a function and a procedure.
 We need to make sure that we thoroughly test the programs that we create, both during the creation of the
program and at the end of the program, using suitable test data.

?
1. Describe what is meant by the term ‘selection’. [2]
2. Describe two ways in which a programmer can make sure that a program they create is robust. [4]
3. A hospital wants a program that records the temperature of each baby that is currently in its maternity unit.
It wants to store the temperature of each baby; it will have 15 babies in the unit at a time.
 If a baby’s temperature is below 36.5 degrees, the program should alert a nurse with a suitable message.
 If a baby’s temperature is above 37.5 degrees, the program should alert a nurse with a suitable message.
Write an algorithm that the hospital could use to enter the temperatures of the babies in the unit, generating an
appropriate output message if appropriate. [6]

4. a) A teacher needs a program that records two test scores for each student in a class of 20. Test 1 has a
maximum of 15 marks, test 2 has a maximum of 20 marks. Each mark entered should be validated
and any invalid marks must be rejected.
Write an algorithm that the teacher could use to store the student name and test scores for each
student in the class. [7]
b) The teacher now wants the program to be able to output the students name and their total score of
both tests. They also want the program to output the classes average test score for each test.
Extend the algorithm created in part (a) to include these two new requirements. [7]

GCSE Computer Science Course Companion (Chapter 12) Page 17 of 17 © ZigZag Education, 2018