Edexcel International D1 Algorithms

Section 1: Working with algorithms

Notes and Examples

These notes contain subsections on

 Algorithms
 Flow charts
 Programs for a graphical calculator
 Binary search algorithm

Algorithms
An algorithm is simply a set of precise instructions. Although in this chapter (and
throughout Decision Maths) you will be working through algorithms by hand, in real
life algorithms are usually programmed into computers.

Flow charts
It’s useful to be aware of the box convention used for drawing flowcharts.

A flowchart may
have circular
boxes to start and
end the process it
describes.

Diamond shaped
Rectangular boxes boxes are used for
contain instructions to questions/decisions.
be carried out on the The route followed
variables in the problem from such boxes
depends on the
outcome.

Boxes with curved

corners are used for
inputs and outputs.

Example 1 below uses a flow chart to communicate an algorithm.

Example 1
Draw a flowchart to divide one number by another using repeated subtraction. The output
should be the quotient and the remainder.

1 of 4 07/10/19 © MEI
[Link]
 Edexcel Int D1 Algorithms 1 Notes and Examples

Solution

Start

Read x, y
N=0

No x=x–y
x < y? N=N+1

Yes N is being used to count

the number of subtractions
you have done.
Output N, x

When x < y you cannot

subtract any more, and the
End value of x is the remainder.

Programming a graphical calculator

Programming a graphical calculator to carry out simple algorithms like the ones in
this chapter is quite easy. The programming language used varies from one make of
calculator to another.

It is well worth trying some programming, as this will help your understanding of
algorithms and flowcharts.

The following two pages contain ‘pseudo code’ (which means that it uses the type of
commands and structure used in most programming languages – the actual
commands used will vary according to the software used) for two algorithms: finding
the roots of a quadratic and Euclid’s method for finding the highest common factor of
two integers. However, you might like to try writing the programs for yourself without
looking at these. Start with the one for finding the roots of a quadratic as this is the
easier.

Quadratic Equation Formula

Input A
Input B
Input C
D = B² - 4AC
If D  0

2 of 4 07/10/19 © MEI
[Link]
 Edexcel Int D1 Algorithms 1 Notes and Examples

Display ( B  D ) / (2 A)
Display ( B  D ) / (2 A)
Else
Display “No real roots”
End

Examples

If A = 1, B = 3 and C = -2, then the answers displayed are 0.5615528128 and

–3.561552813.

If A = 1, B = 1 and C = 1, then the message displayed is NO REAL ROOTS.

Euclid’s Method

Input X
Input Y
While X  Y
If X>Y
X=X–Y
Else
Y=Y–X
Display X,Y
Display "HCF =", X

Example

If X = 21 and Y = 91, then the result displayed is: HCF = 7

Binary search algorithm

Efficient searching methods are essential in many computerised systems which may
include vast databases. As for sorting, you can only really experiment with the
algorithms by hand with small lists, when you can spot the item you are looking for
straightaway!

The binary search algorithm is one of the most efficient searching algorithms. The
method for searching for a particular item in an ordered list of length n is as follows:

1. Find the item at the midpoint of the list. If n is odd, this is the item with position
2 (n  1)
1
, and if n is even, this is the item with position 12 (n  2) .
2. Compare the midpoint item with the item you are searching for. If the midpoint
item is the one you are searching for, you have found it and the search is
over. Otherwise, use the comparison to decide which half of the list you
should now search.

3 of 4 07/10/19 © MEI
[Link]
 Edexcel Int D1 Algorithms 1 Notes and Examples

3. Repeat steps 1 and 2 on the new list. Continue until either you have found the
item, or you have reached a list of just one item which is not the one you are
searching for, in which case the item is not in the list.

Clearly this method only works if the list is ordered in some way, so that you can
decide which half of the list to select. Usually, lists are ordered alphabetically or
numerically.

The example below may seem trivial – we already know where the letter J is in the
alphabet! However, the example illustrates how the method works, and it could be
used in the same way by a computer to find a particular word in a dictionary
containing thousands of words.

Example 2
Use the binary search method to locate the letter J in the alphabet.
State the number of comparisons required.

Solution
There are 26 letters in the alphabet.
The midpoint is taken as 12 (26  2)  14 . The 14th letter in the alphabet is N.
Compare J with N: J comes before N so now look at the list A – M (13 letters).

The midpoint is taken as 12 (13  1)  7 . The 7th letter in the list A – M is G.

A B C D E F G H I J K L M
Compare J with G: J comes after G so now look at the list H – N (7 letters)

The midpoint is taken as 12 (7  1)  4 . The 4th letter in the list H – N is K.

H I J K L M
Compare J with K: J comes before K so now look at the list H – J (3 letters).

The midpoint is taken as 12 (3  1)  2 . The 2nd letter in the list H – J is I.

H I J
Compare J with I: J comes after I so now look at the list J (1 letter)

There is only one letter in the list so the midpoint is J itself.

Compare J with J: The search is complete and J has been found.

The search required 5 comparisons.

In Example 2 above, J was eventually located when the list had a length of 1. The
search could have been much shorter, e.g. if the search was for the letter N it would
be complete after just one comparison.

The binary search method can also be used to show that an item is not in a list: if
you get to a list of 1, and this is not the item you are looking for, then it is not in the
list.

4 of 4 07/10/19 © MEI
[Link]