2.1 Algorithms

Learners should have studied the following:

a) Computational thinking:

b) Standard searching algorithms:

c) Standard sorting algorithms:

d) How to produce algorithms using:

Pseudocode
Using flow diagrams

e) Interpret, correct or complete algorithms.

Introduction

In this unit, we will learn about computational thinking, which is, quite literally, thinking like a computer does and learning how to solve problems by breaking them down into simple and logical stages. Some people are naturally good at solving problems, but everyone can practice and become better at it.

Abstraction

One of the key skills of effective problem solving is abstraction. Basically, abstraction involves ignoring unnecessary details and keeping the essential detail that is needed to correctly solve the problem.

A good example of abstraction can be seen on the road signs in the UK.

Many roads, especially in a large town or city, are very complicated and it can be confusing for motorists who may not be familiar with the roads. If the road signs included too much detail, the motorist couldn't possibly take in all of the information without them getting distracted and possibly causing an accident. By stylising the signs and a consistent use of colour and symbols, the motorist is presented with the essential information that they need.

Some roads are very complicated!

Road signs take away details that the driver doesn't need to see, whilst keeping the essential information.

There are 270 stations shown on this map, and it appears that they have all been carefully and evenly laid out.

In reality, the stations are very close to each other in central London, but much further apart on the outskirts of London.

The London Tube map is another good example of abstraction. The London Underground was the first underground railway and currently has 270 stations and 250 miles of track divided into eleven different "lines" or routes. Harry Beck drew the first map in 1931, and his creation became very popular because it allows all users to find their way through this incredibly complex system. The map is constantly being updated but its iconic graphics are instantly recognisable, and it has been copied in many cities around the world.

Once again, colour is used to help the user and the map has been carefully laid out to make it easier to find your station and journey. The actual layout of the stations is very different - two stations may be close together on the map but are actually a long distance apart and may be deep underground or part of the surface railway.

Decomposition

When we solve problems, both with and without a computer, we need to break down the overall problem into smaller, simpler ones which can be solved more easily. Decomposition means breaking down of large problems into smaller problems.

Smaller problems are easier to solve.
They can be created independent of the other problems.
They can be tested independently.
The smaller solutions can then be combined to produce the full solution.
There is not always one right answer. A problem could be decomposed in several valid ways.

We all do this as part of our everyday life. When faced with an everyday problem, such as "get ready to go out", we would decompose the problem down into smaller ones:

Are we dressed appropriately?
Do we need money?
Do we need food, or do we need to eat first?
Have you told everyone who needs to know where we are going?
Have you got your phone and keys?
Have you been to the loo!?

When people solve a Rubik's cube, they break the problem down into smaller problems - solve the first face, solve the middle sections, etc.

Algorithmic Thinking

An algorithm is a set of rules that must be followed that will carry out a task. The rules must usually be followed in the correct order, and may contain items which will only be carried out under certain circumstances.

For your GCSE Computing, you need to know about several "standard" algorithms. The first two are used to search a list of items for one that meets certain criteria.

Searching

Computers can hold a lot of information, but that information is only useful if we can find it easily. There are many ways that a computer can search for information, and for your GCSE you need to know about two of the most popular methods. Watch the Searching Algorithms Video (opposite) which explains about searching.

Searching Algorithms Video

Searching.mp4

Linear Search

The first search algorithm that we need to know about is called a linear search. This is the most common way that humans would search for something, we start at the beginning and check each item until we have either found what we are looking for, or reached the end.

The list of items does not need to be in order. Below, you can see a pseudocode algorithm for a linear search, along with a version written in Python.

Pseudocode for a linear search

Python code for the same linear search

Binary Search

Obviously, there are faster and more efficient ways of searching than just starting at the beginning and checking every item until you find it (as in the linear search above)

If the list of items to be found are in order, then we could start by checking the item right in the middle of the list. You may be lucky, and find what you are looking for straight away, but it is unlikely. If the item that you check is bigger than what you are looking for, then you can continue searching using only the cards which are smaller. This gives you a list of items that are half as big, so you can continue - checking the middle item, removing half the items etc. until you have found what you are looking for.

This search is called a binary search because we split the list in two each time. It is usually much faster than a linear search (see below)

Pseudocode for a binary search

Python code for the same binary search. three variables are used to remember the positions of the midpoint, a point on the left and a point on the right.

When we use a linear search, we will probably have to check a large number of items before we find what we are looking for (on average, if we search 1000 items, it will take 500 searches)

A binary search removes half the list every time one check is carried out, which means that we have to check far fewer items, so a binary search is far quicker (unless the item you are searching for is at the beginning of the list of items). Using a binary search on 1000 items will take a maximum of 10 searches.

Sorting

Bubble Sort

As well as searching for an item in a list, it is very common for us to be able to sort a list of items into a particular order. One of the simplest ways to do this is the bubble sort.

To perform a bubble sort on a list of items, a number of comparisons are made. This involves comparing the value of one item with another, and taking an appropriate action. With a bubble sort, the first and second item are checked, and swapped if the first item is greater than the second. Next, the second and third item are checked, and swapped if the second is greater than the first. In this way, a "large" item will "bubble" up the list of items. The process is continued right to the end of the list, and then it is done again until the full list has been gone through and no items have had to be swapped (i.e., it is in order)

Bubble Sort Video

You will find lots of videos on Youtube about the different sorting algorithms, but I thought this one from Cambridge University Press was easy to understand and made good sense.

Bubble Sort.mp4

Merge Sort

With a merge sort, the list of items is broken down into smaller lists, with just two items in each. The small, two item lists are arranged into the correct order. It is very easy to merge two of these lists together so that all the items are in the correct order. This will be repeated until all of the two item lists have been merged into four item lists. The four item lists can then be merged into eight item ones etc.

The process of merging two lists is easier, as both the lists are in order. The smallest item in both lists is compared and the smallest one inserted into the new list. This is repeated until all the items are inserted.

Insertion Sort

This is the final sorting algorithm that we need to understand for GCSE Computing.

To carry out an insertion sort, a completely new list is made. The original set of data is then added to it, one item at a time. As it is added, it is placed in the correctly sorted position. This is a very quick way of sorting data.

There is a great interactive demonstration of some different sorting algorithms at the website:

https://www.advanced-ict.info/interactive/algorithms.html

Interpret, Correct or Complete Algorithms

As we have seen, an algorithm is simply a way of solving a problem.

Algorithms can take many forms:

They may be a simple written list which could be numbered or just done as a bullet list
They may be a flowchart with arrows to indicate "program flow"
They may be pseudocode, which is a cross between written English and a programming language
They may be a fully working program

We need to be able to understand what a particular algorithm does and see how it will handle a particular situation.

Flowcharts

Flowcharts have been used for many years to document or describe how systems work. They use a standard set of symbols or shapes and each specific symbol has a set meaning. Each symbol contains text which explains its function. They can be coloured but are normally left as just a plain black and white symbol and text.

Arrows connect each shape which indicates how the "flow" of the program moves from one shape to another. There should be only one possibility of the program flow at any one time. A diamond shaped decision box has two possible routes of flow, and the question in the shape should be one that has two possible answers "Yes" and "No"

This is the "terminator" shape that should be used at the very start and end of a flowchart.

All flowcharts must have a "Start" terminator (Labelled as Start) and most systems will also have a "Stop" terminator.

This shape is used when a program requires an input or an output.

An example of an input would be when a program asks the user to enter their name.

An example of an output would be when a program prints out an answer.

This is the process shape which is used when a program does something that does not involve a decision, an input or an output.

The process should be described briefly, and complex processes should be broken down into several smaller steps.

This is the decision shape, which is used whenever a program uses a statement that has a choice of possible routes. The box should be labelled with a brief statement that summarises the two possible choices. (Decisions should always have only two choices)

A decision shape is unusual because will have two arrows from it, which should be labelled as "Yes" or "No"

This shape is used when a subroutine has been used. This is a frequently used piece of code that may contain lots of separate tasks. The main flowchart will refer to the subroutine using this shape.

Arrows should be drawn to connect each shape. the direction of the arrow represents the "flow" of the program. Arrows should be drawn horizontally or vertically and angled or non straight lines should be avoided.

Algorithm Examples

We can also use pseudocode, or even full code to describe an algorithms.

Look at this program (its pseudocode, because Python wouldnt recognise the capitalised words)

What would you do if you followed this algorithm? (try it!)

What would your teacher do?

Here are some keywords that you should understand when discussing algorithms:

Algorithm – the series of steps to solve a problem or perform an action.
Flowchart – a diagram that shows the inputs, outputs and processes in an algorithms.
Process – an action that takes place.
Pseudocode – simplified programming code that is not language specific, used to design algorithms.

Flowchart Example

This is a typical problem that you may have to solve when writing a program, and you may get something similar in the unit 2 exam.

Imagine that you are the computer, and follow the steps one at a time.

This slide show uses a trace table which is a great way of keeping track of the values of any variables as your program runs.

Step through the slides one at a time, using the ">" button.

Try to answer the question at the end.

followanalgorithm.pptx

Report abuse