D1: Algorithms

An algorithm is a set of instructions that can be followed and will always produce the same result, regardless of who, or what, is following them. This means that if two human beings are following the same instructions, they should get the same result (provided they do not make mistakes, of course). Because algorithms do not require intelligence or human senses, they can be followed more efficiently by machines than people. We will see that a human being is very capable of putting a small number of words into alphabetical order quickly, but if the list gets too big a machine is much more efficient. But how do computers do this? After all, a computer is merely a (complex) electrical circuit with microchips and stuff; a PC cannot really think like a person can.

Flow Charts

Algorithms can be written down in a number of ways. For instance a recipe for baking a loaf of bread will usually be a set of instructions in a list.

Another way to write algorithms is to use a flow chart. Here the instructions will usually be a little bit more complicated than a list and will involve making decisions based on results of calculations.

In this module you do not need to understand the different shapes that are used in flow charts. You do need to be able to follow them and write down the results as you go.

Flow charts are a bit like a poor-man's computer program. There will be different variables whose values change as we go through the chart. There will be times where we look at a particular calculation and make a decision based on the result.

Any one who has ever written even the most simple computer program (in any language) will be familiar with the "let" key word. Actually, most modern languages do not need you to even write the word "let". What it is used for is to give a new value to a variable.

For example: Let n = 5 + 2 instructs the computer to give the variable "n" the value "7". Let n = a + b makes the variable "n" equal to the sum of the variables "a" and "b". This seems straightforward enough but what if I want to make our variable "n" go up by four?

It's actaully easy, but looks like mathematical nonsense: Let n = n + 4 is the instruction we use. Or simply n = n + 4 if we can't be bothered with the "let" keyword. This is not an equation to solve (it's impossible to find a number that equals itself add 4) but rather it's an instruction to let the new value of "n" equal the current value add 4.

Now we will have a look at an exam question involving flow charts. Hopefully you'll see that it's all pretty simple, provided that you work methodically.

Sorting Algorithms

One of the most useful algorithms that we can get a computer to do for us is to sort long lists into order. A computer can only deal with Yes/No, True/False type questions and so can't order 3 numbers at once, they can only "see" 2 numbers at a time. How would a computer order numbers (or words alphabetically)?

We will look at 2 different ways of doing this. One is easy and quick for quite short lists, the other is faster for longer lists.

Bubble Sort

The simplest method to order numbers is to use Bubble Sort.

Place some shuffled cards with numbers on, face down in front of you. Remember that a computer can only compare 2 at once and make a decision based on the result of a True/False type question. Turn the first 2 cards over. Are they in the right order? If they aren't then swap them round, otherwise do nothing. Now turn them back over (a computer cannnot remember what the cards were once the decision to swap round or not is made).

Now move on to the second and third cards in your list (the second is one that you have just used but you haven't seen the third card yet). Repeat the decision making process for these cards ie swap them if they are in the wrong order otherwise do nothing. Turn them over and move on through all of the cards until you reach the end.

What has this achieved? If you can't answer this question then start again and think about what is happenning. The answer is in the box below.

Can you see why this is called Bubble Sort? Think of the cards as "bubbles" in a fizzy drink; they rise to the surface in some order and leave the drink.

Now we know that the last card is in the right place, all we need do is remove it from the list (like a bubble leaving a fizzy drink) and repeat the whole process for the remaining cards. Each time we go throught he list we get the last card in its right place. This is called a "pass".

In an exam you must show the examiner that you understand the process by showing the order of numbers after each comparison until the last number is in the right place. This is the first pass. For the other "passes" you needn't show all the comparisons, just write the order after each pass.

This is a part of an exam question from Jan 2003.

25 22 30 18 29 21 27 21

The list of numbers above is to be sorted into descending order.

  1. Perform the first pass of a bubble sort, giving the state of the list after each exchange.
  2. Perform further passes, giving the state of the list after each pass, until the algorithm terminates.

I have given a solution to this in the video.

Quick Sort

The main problem with Bubble Sort is that it takes ages. A modern PC can do 2 billion calculations per second, but these are binary calculations. Just converting a number to a load of ones and zeros takes quite a few individual steps. If you had a list of 2000 students in a school we would need 2 million comparisons to sort them with Bubble Sort. The fact is: Bubble Sort is very slow.

It doesn't take a genius to predict that Quick Sort is probably faster than Bubble Sort for long lists of data.

Take some playing cards and arrange them in this order: 3 5 1 7 2 9 8 4 6. We are going to use Quick Sort to arrange them in ascending (smallest to greatest) order.

  1. Find the card in the middle (not the median, just the one in the middle of the list). It is the 2.
  2. Now go through the cards from left to right. If the card is smaller than 2, put it on the left of 2. If it's bigger than 2, put it on the right.

Think about what this achieves when you have finished. The answer is in the box below.

With 2 in its correct place we can now work on the numbers on the left to sort them. You should find that there is only one number (1) so it is already sorted. To sort the numbers on the right (3 5 7 9 8 4 6), choose the number in the middle (in this case it is the 9) and go through the list putting the numbers on the left of 9 if they're smaller and on the right of 9 if they're bigger.

Nine is an unlucky number to be in the middle because it is bigger than all the others (but only an intelligent human being can tell this - a PC can only compare 2 numbers at once). We end up with all the numbers on the left of 9, but at least 9 is now in the right place.

Our unsorted list is now 3 5 7 8 4 6. Find the central number. Here is a problem as there are two numbers in the middle. For this course we always choose the second number if there are two in the middle - that is 8 in this example. Keep repeating the process until all numbers are in the right place.

Have a look at this clip to see how it all works

Searching Algorithms

Another useful type of algorithm is a searching algorithm. Here a computer searches through a huge database, looking for a certain record.

The worst way to do this would be to look at each record until we found the one we're looking for. Obviously this is very slow and hopelessly inefficient.

A much better way to search for the record is to use Binary Search...

Binary Search

Binary Search is the only searching algorithm needed for D1. It is very fast at locating a record amongst millions of entries but first the data must be sorted using a sorting algorithm. Once the data is in order, we're ready to perform a binary search.

The process is simple: each time we pass through the algorithm we half the size of the list. How? Look at the record in the middle of the list and compare it to what we're looking for. Too big? We know that all records that are even bigger can be discarded. Too small? All smaller records can be discarded.

Here is a clip demonstrating the algorithm in practice.

The boy follows the algorithm quite well but goes wrong at some point. Can you tell where?

How do you write all this down? Here's a worked exam question from 2007.

Bin Packing Algorithms

Another very common type of process is packing different sized boxes into larger containers called bins. This is used when a computer allocates locations in memory to a program but could just as easiy be used to pack boxes into shipping containers. We will look a two very similar algorithms: First Fit and First Fit, Decreasing.

First Fit

Basically you go through the list of boxes and put them in the first available bin that has enough space for the box. If there is not enough space then we need to start a new bin. See First Fit, Decreasing for how to do this.

First Fit, Decreasing

The problem with First Fit is that you can be left with big boxes at the end and lots of small spaces, so you end up having to get a new bin to fit them in. This makes the algorithm less than perfect. It is much better to start with the big boxes because then you'll be left with small boxes to fit in the gaps at the end. Often we will need to use a sorting algorithm to get the boxes in order (largest first). Here's an exam question from 2003.

25 22 30 18 29 21 27 21

The list of numbers above is to be sorted into descending order.

  1. (i) Perform the first pass of a bubble sort, giving the state of the list after each exchange.

    (ii) Perform further passes, giving the state of the list after each pass, until the algorithm terminates.

  2. The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.

    (i) Show the result of applying the first fit decreasing bin packing algorithm to this situation.

    (ii) Determine whether your solution to (b) (i) has used the minimum number of 50 cm rods.

Notice that part (a) is just bubble sort. I have made a clip of the solution ...