Algorithms
Algorithms provide the method of solving a problem. Algorithms lie at the heart
of computer science as much of the subject consists of creating logical
solutions to problems in computer format. Some people have likened algorithms to
recipes in cookery, they provide the steps you must take to solve a problem. Can
you think of an algorithm for testing whether a number is prime?
i.
Searching
'Battleships'.
Search list of members of a class. Count number of items searched for each
search.
Use the method developed earlier for finding mystery numbers to search a list.
ii.
Sorting
Sort using network on ground. Split into groups of about 8. Write a single
letter on a sheet of paper. Stand in a line with the letters in random order.
Walk forward 2-3 paces and converge into pairs. Compare letters and have the
lowest on the left. Walk forward 2-3 paces and diverge. Repeat the previous
procedure until the letters are sorted. If there is an odd number of letters the
right hand person should do a comparison with the adjacent person after the
other comparisons have taken place.
Bubble sort. Put 8 cards in random order. Devise a strategy to sort the cards
into ascending order by systematically comparing pairs of cards. Note how many
comparisons are made to sort the cards.
Mergesort.
iii. Routing and Deadlock in Networks
The Internet (and most other networks) work by splitting data into packets. Each
packet contains just a small part of the data along with the computer addresses
of the sender and the destination. The packets are sent across the network, they
can each take different routes to the destination computer where they are
assembled into their correct order so their contents can be read.
We saw earlier how most nodes in the Internet are linked to many other nodes.
When a packet reaches a node a piece of equipment called a router examines the
packet, chooses a suitable route and sends it on to the next node. A packet can
pass through up to 255 nodes (a number keeps count of each step), after which it
is lost. The router has to decide what is the best route for a packet to take in
order to reach its destination, which may be many steps away.
Practical Work
We can simulate a simple routing process with balls or fruit. It's a bit like
'pass the parcel'. Sit in a circle with a unique label attached to your shirt or
at your feet. You will have two balls or oranges labelled with your identifier -
one person has only one so the balls can be passed around. At the start you can
hold any ball/fruit but your own. As the game progresses you can pass either of
the balls/fruit you hold to the one empty hand in the circle. The aim is to
acquire your own two balls/fruit and the game finishes when everyone has their
own.
Deadlock is the situation where data cannot move through a network because two
or more processes want the same item. Deadlock occurs in the simulation when
someone tries to hold on to their own balls/fruit before everyone else has
theirs. The simulation can only be completed if you cooperate.
An alternative exercise is to simulate computers and routers. Three quarters of
a class act as computers sending and receiving messages in packets while the
other quarter act as routers that send the message packets to their
destinations. The computer pupils write a message across separate sheets of
paper with their own address and that of the recipient in the 'header' of the
packets. They take each 'packet' in turn to a 'router', the router examines the
header and sends it on to either another router nearby or the destination
computer.
iv. Finite State Automata
A finite state automaton is a simple machine that moves through states as time
elapses. One example might be a light bulb that has either two states (on/off)
or more than two (off, dim, medium, bright, etc.) A state table holds the rules
for changes in the state of the automaton, for example a bulb in the off state
can react to a message to turn on.
Imagine a series of light bulbs in a garden. A special bulb will only light up when
the correct sequence of bulbs switching on and off has been completed. For
example you might start by switching on bulb 1. Switching off bulb 1 does
nothing but you can switch on any other bulb. You switch on bulb 2 and then 3,
at which point bulbs 1 and 2 switch off. You switch on bulb 5 (the special bulb)
but nothing happens so you try bulb 4, which turns on bulbs 4 and 1. You now try
bulb 2, which switches off bulbs 1 and 4 and switches on bulb 2. You switch on
bulb 5, which now lights up and bulb 2 switches off.
This can be represented in a state table:
|
Event: |
Bulb 1 |
Bulb 2 |
Bulb 3 |
Bulb 4 |
Bulb 5 |
| State 1 |
On: S2 |
Off |
Off |
Off |
Off |
| State 2 |
On |
On: S3 |
Off |
Off |
Off |
| State 3 |
On |
On |
On: S4 |
Off |
Off |
| State 4 |
Off |
Off |
On: S5 |
Off |
Off |
| State 5 |
Off |
Off |
On |
On: S6 |
Off |
| State 6 |
On |
On: 7 |
Off |
On |
Off |
| State 7 |
Off |
On |
Off |
Off |
On: S8 |
| State 8 |
Off |
Off |
Off |
Off |
On |
In state 1 only bulb 1 can receive an instruction to turn on. In state 2 only
bulb 2 can receive the on instruction. In state 3 only bulb 3 can switch on, and
so on. The only way to get bulb 5 to turn on is to get to state 7 where bulb 2
is on by itself and where turning on bulb 5 finally produces the desired effect.
This might also represent the steps required to manufacture some item - the
final part cannot be added until the correct sequence of steps is completed.
This is the way the route to treasure might work. The instructions don't say 'go
straight to point X', that would be too easy, instead you have to visit a series
of places and choose the correct route from each of those. This might involve a
series of islands. You start at one island and then follow a series of steps
that lead you to the single step that will take you to the treasure - like the
correct steps in lighting bulb 5.
And so you proceed from your first island to the next. At each island you have a
choice of 2 destinations.
v. Cellular Automata: The Game of Life
Cellular automata are cells in a grid that behave like finite state automata -
they have a finite number of states (e.g.
black/white) that can change through time. Each cell has its own behaviour that may be influenced by the
other cells around it. Time advances in discrete steps and with each tick the
cellular automata change state according to the rules of a particular model.
One version of cellular automata was devised by mathematician John Conway in
1970 and is known as 'The Game of Life' because of the way it appears to portray
simple creatures being born and dying. You may know the board game (check
here) but Conway's
'game' is different.
The rules appear simple but took some
time to refine to the point where they produced the most interesting effects.
With each step in time the following rules are followed by each automaton:
- Any live cell with fewer than two live neighbours dies,
as if by loneliness.
- Any live cell with more than three live neighbours dies,
as if by overcrowding.
- Any live cell with two or three live neighbours lives,
unchanged, to the next generation.
- Any dead cell with exactly three live neighbours comes
to life.
It's tempting to compare the rules of the 'game' ('model' is
probably a better word) and and the patterns it produces with
real life, the way organisms might react in certain situations
of crowding or loneliness.
Practical Work
Take a sheet of graph paper and fill in some squares in the middle - three in a
row will be enough to begin with. Add a label
'1' to the bottom of the sheet. On a second sheet of graph paper plot the state
of the squares after one step in time. Add a label '2' to this second sheet.
Repeat this on 3 further sheets.
Doing this by hand is time-consuming. This
link allows you to experiment
on a computer model.
You may be tempted just to draw random patterns across the grid and set it going
super-fast. That's OK to begin with but it won't help you understand the model
and what it can do. Use the Clear option and draw some simple shapes and see how
they develop. Better still, see if you can predict the next step by looking at
the rules of the model. A 2x2 square is one possible starting point, followed by
a 3x3 square and a 4x4. Then try a 3x3 square with an empty middle square or a
5x5 outline square.
The Life Lexicon shows
how seriously some people have taken this model. One of the uses of cellular
automata is in computer games, for example SimCity.
vi. Compression
Here
Advanced algorithms
Back