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?
The well-known algorithm for finding the GCD of 2 numbers is attributed to Euclid around 300 BC but was almost certainly known before then. Given two numbers such as 90 and 24 what is their greatest common divisor? Can you figure out a way to find it?
You may be able to do it in your head from knowledge of multiplication tables or by trial and error. However, these methods would not work for larger numbers. What we need is a method that will produce the answer reliably for any pair of numbers. (Some pairs may have no gcd other than 1, a result which is not seen as particularly useful or interesting.)
The solution requires nothing more than simple arithmetic. There are two well-known solutions, one you may find for yourselves, the other more subtle and less obvious but equally simple when you find it.
A tree is a graph that does not have any loops or cross-links, the branches do not run across each other.
Put names of class members into a binary tree. Write names on cards, pick a card for the 'root' and then grow the tree with random selections. Compare the number of levels in trees across the class. Can you move systematically through the tree and derive a list in alphabetical order?
Write the parts of a simple expression on cards e.g. 2 + 2. Place this in a tree formation with the + at the root and the 2s either side. Write down the expressions derived from traversing the tree in these ways:
LNR: go left as far as possible, write down the last item found; write down the value in the root of the sub-tree; check the right branch, if no left sub-branches then write down value or continue (if item is operator it will have left and right children, if it is an operand it will have no children)
NLR: write down value in root, check left and write down item found - if operator continue left, if operand check right;
LRN: go left as far as possible, write down last item found; check right including any sub-trees, if no sub-trees write down item; return to node and write down value;
(where N = node or root)
Now write the following expression on cards and place it in a tree with the + at the root and the * in the right branch: 2 + 2 * 2
Traverse the tree in LRN fashion and work out the arithmetic result.
Rearrange the tree with * in the root and + in the right branch and repeat the above traversal. What result do you get?
Expressions can have the operator before or after the operands as well as in between. What advantage does postfix have over infix?
These trees are different to the binary trees we saw earlier, though they still do not have loops or branches that run across each other. The problem here is to devise a network or tree that spans all the nodes in an area using the shortest possible route and therefore the least amount of materials.
This problem might be applied to, for example, a road network such as motorways, a rail network, a series of connecting flights or a utility such as gas or electricity moving from house to house.
Work in pairs. You should have a sheet of graph paper, a pencil and a ruler each. On one sheet of paper plot some points at various intervals across the graph paper as if they were towns on a map or houses in a neighbourhood with no links between them. Make a copy of the points on the second sheet. Each member of the pair should start at a different point and then look for a way to build the shortest route to link all places.
Compare the length of the routes you have created. Do you think you could do better? How? Make two more copies and complete a second tree using the 'greedy algorithm'.
What are the advantages and disadvantages of a minimal spanning tree? What if the links were roads, how useful would they be?
Can you see any practical uses for this technique in the world of computer networking? What general principle would you consider when connecting computers together with, say, optical fibre? How does the minimal spanning tree approach compare with the way the Internet is linked together? (Take a look at this.) UK USA
This puzzle involves three pegs and any number of rings, each of a different size. To begin with the rings are stacked in sequence, largest on the bottom, on peg A. The aim of the puzzle is to move the rings from peg A to peg C using peg B with the single rule that a larger ring should never be placed over a smaller one.
Start with two rings and work out a method that will move them across the pegs in the required way. What is the minimum number of moves? Now try three rings and finally four. Is there a formula that expresses the number of moves that a given number of rings will require? Can you see a pattern in the moves?
