Algorithms

The following is a skeleton for the content of D1 algorithms, with the content taken from AQA, OCR, OCR MEI and Edexcel's specifications. Not all specifications include all of the following content.

Introduction to Algorithms

What is an algorithm?

An algorithm is a precise set of instructions which, when followed, will solve a problem. They can be presented in various forms, e.g. words, pictures, flow diagrams. Recipes, knitting patterns, instructions to set a VCR or build a desk are all examples of algorithms we may encounter in everyday life.

Why use algorithms?

The main advantage of algorithms is that we can then use computational methods of solving problems. It's rather easy for one to put the numbers 2, 5, 3, 1 and 4 in ascending order, but it would take much, much longer for one to sort a list of 1000 random numbers. Also having an algorithm means that someone else can achieve the same result as you, without having to work out how to do it. Specifically having an algorithm may allow a computer to perform the actions.

Order

Flow Diagrams

You may need to be able to follow or create flow diagrams in order to demonstrate an algorithm. There are three basic shapes used:

Oval, used for start & stop and input & output.
Rectangle, used for calculations and instructions.
Diamond, used for yes/no questions.

Sorting Algorithms

An example

Given a deck of 52 cards to be sorted according to their suit; their position in the current sequence of cards is given a number:

What suit is card 1? It is HEARTS.
What suit is card 2? It is SPADES. We want a deck with spades before hearts. Therefore we exchange the two cards, and go back one step. If we are already at the beginning, then ignore the need to go back one step.
What suit is card 1 now? It is SPADES.
What suit is card 2 now? It is HEARTS. These two cards are in the right order, therefore we do NOT interchange them, but go to the next card in the deck.
What suit is card 3? It is HEARTS. It is the same as the previous card, therefore we carry on to the next card in the deck.

........... AND SO ON, until we get to the card that is one before the last card. We compare, exchange if necessary, and then stop sorting.

Next we separate the HEARTS, or some other suit, as we wish, from the 52-card deck, have now only a deck of 13 cards, and sort this smaller deck of cards according to 2,3, ... J,Q,K,A and do this with the other 3 suits too, one at a time.
After that we are nearly all done, combine the 4 sets of 13 cards each into a big set of 52 cards and stop.

Bubble Sort

For a set of numbers, the first number is compared to the number to the right of it.

13, 2, 4, 3, 82

13>2 so it moves to the right.

2, 13, 4, 3, 82

13>4 so it moves to the right.

2, 4, 13, 3, 82

13>3 so it moves to the right.

2, 4, 3, 13, 82

13<82 so it stays.

At the end of first pass: 2, 4, 3, 13, 82
At the end of second pass: 2, 4, 3, 13, 82
At the end of third pass: 2, 3, 4, 13 82

This set only needed 2 passes, but on a larger data set it can get quite large. The maximum number of passes is equal to the size of the set, provided the set items are unique.

Shuttle Sort

From a set of numbers, one selects the first two numbers and underlines them. These two are the ones that get sorted in the first pass.
In the second pass, the range of numbers to be sorted increases by one, so the first three numbers are compared and sorted into their order.
And so forth until all the numbers are covered in the range and sorted.
1st pass - 23, 2, 4, 8, 9 - 23>2 so 2 is sorted to the left.
2nd pass - 2, 23, 4, 8, 9 - 23>4 so 4 is sorted to the left.
3rd pass - 2, 4, 23, 8, 9 - The numbers are sorted
4th pass - 2, 4, 8, 23, 9 - The numbers are sorted
Final set of numbers = 2, 4, 8, 9, 23 - The numbers are sorted

Quick Sort

Using the midpoint as the pivot, (or whichever value it asks you to use in the question) perform a shuttle sort on each of the sub lists. Continue until all terms but one have been used as a pivot.

Insertion Sort

Shell Sort

Divide the set of numbers in n/2 sublists.
The sublists are shuttle sorted
The data range is recombined and split into half the number of the previous sublists.
The data range are shuttle sorted again.
Repeat until the number of sublists = 2

Packing Algorithms

Full-Bin

The 'full bin' algorithm is one in which combinations of objects which would fill a 'bin' are grouped together to fill as few bins as possible. The remaining objects are then placed in other bins. This is best illustrated by the example below (NB - this is NOT an exam question and does not represent the level of complexity that can be expected on the actual paper).

Q) A computer software company needs to publish its software on floppy disks of capacity 200kB. The files are of size 25kB, 90kB, 30kB, 120kB, 190kB, 10kB, 70kB, 40kB, 100kB, 140kB and 80kB. How many floppy disks are required? Use the 'full-bin' algorithm to arrive at a solution.

A) Start by looking along the list to find values that add up to 200. There is no particular method for this (everyone seems to do it differently), but I find it helps to find combinations that add up to full 10's etc. Fill the 'bins' with these combinations:

Bin | Files

A | 120, 80

B | 190, 10

C | 70, 40, 90

This leaves 25, 30, 100 and 140. It makes sense to get as close as possible to a full bin using the remaining values:

(140 + 25 + 30) = 195 <- so place these values in the next bin, leaving the 100 in the final bin.

Solution:

Bin | Files

A | 120, 80

B | 190, 10

C | 70, 40, 90

D | 140, 25, 30

E | 100

5 disks are required to fit all the files.

First-Fit

Place each object, in turn, in the first available space in which it will fit.

First-Fit Decreasing

Reorder the boxes in decreasing order of size using one of the sorting algorithms, before applying the first-fit algorithm to the reordered list.

A-level Mathematics/OCR/D1/Algorithms