Computation covers any form of information processing. Computation theory deals with whether problems can be solved with a computer and, if so, how easy or difficult they will be to solve.
Some problems are linear in nature: as the size of the input increases the time taken to solve the problem grows proportionally in a linear fashion, e.g. double the input size and the time taken to solve the problem doubles as well.
Some problems are polynomial in nature, that is as the size of the input increases the time taken to solve the problem increases at a rate of at least n2.
Some problems are exponential in nature, that is as the size of the input increases the time taken to solve the problem increase at a rate of at least 2n. An exponential function is one that produces a proportionally larger result each time. 2n, 3n, 4n, etc. produce a bigger result with each change in the size of n.
Illustration: 32 = 9; 23 = 8; 102 = 100; 210 = 1024. 1002=10,000; 2100=something very, very large!
Computer scientists are interested in the computation nature of a problem because this will tell them whether the problem can be solved at all and, if so, how long it will take to solve for a given input and what level of computer resources will be needed. It turns out that some problems are impossible to solve (ever!) while a large number of problems can only be solved by 'brute force' over a very long period of time.
Take a pack of 4 cards arranged in a 2x2 grid. How many different ways are there to arrange the cards? The first of the 4 cards can go in one of 4 positions. The second card can go in one of the remaining 3 positions, the third in one of 2 positions and the fourth in the final position. How many arrangements of cards are there?
How many arrangements are there for 9 cards? For 36 cards?
What if the cards have half a monkey on each side in one of four colours and the two parts of the monkeys must be matched?
What if the cards are parts of a jigsaw where each piece can be placed in four rotations, how many arrangements of the pieces are there?
The Towers of Hanoi is a puzzle that involves three pegs and a series of rings, each one of a different size. The puzzle begins with the rings stacked in order of size on one peg. The aim is to move the rings from the first peg to the third using the second as an intermediate step. Only one ring at a time can be moved and a larger ring must never be placed on top of a smaller one. What is the smallest number of moves for 2 rings? 3 rings? 4 rings? The solution for 2 rings is very easy, for 3 rings a little harder and for 4 rings and above rather more difficult. There is a formula, however. Look at the answers for 2 and 3 rings and see f you can link the solutions to the number of rings. This will give the general formula for 4 rings. When the puzzle was first introduced its author claimed that monks were playing a game with 64 rings and when it was complete the world would end. How long might it be until the prophecy is tested?
How many permutations of 4 digits are there when all 10 denary digits are available? (This is important in PINs on bank cards). What about the number of permutations if you can only use a digit once in the 4-digit PIN?
How many permutations of 6 letters are there from the total of 26? (This is important in passwords). What about 8 letters from 62?
The Travelling Salesman Problem (TSP) is as follows: Given a map of n cities and edges (roads) connecting them, what is the shortest route that takes in all the cities and returns to the starting point? To find the shortest route you must test all the possible routes but how many of these are there? It turns out there are rather a lot... How many possible routes are there around 3 cities? Around 4 cities? 5? 20? 50? 200?
Here is a page where you can experiment with American cities. Here is a page with some models in Java.
Ice cream vans. Imagine a network of 26 nodes and connecting edges between them. This might represent a street map of a town. Here is one such arrangement:
There may be an ice cream company in the town that wants to put a number of vans at points around the town such that every node is less than two edges away from a van (or one and a bit edges to a van). This would mean that any one living in the town would, at worst, have to walk along their own road and one other to reach an ice cream van. How many vans are needed to solve this problem and where should be located? Is there any way of solving this problem other than by brute force? (Trying every possible combination of vans and intersections.)
Clearly 1 van will not cover the intersections and roads in the required way. So try 2, 3, 4...
The most likely solution to the problem is a sub-optimal one: park the vans at nodes that you think will maximise sales and keep trying new arrangements until you think you have it right.
How many combinations of 4 cards are there when drawn at random from a pack of 52?
How many combinations of balls numbered 1-49 are there when 6 are drawn?
How many permutations of 4 digits are there when all 10 denary digits are available but you can only use a digit once in the 4-digit PIN?
How many permutations of 6 letters are there from the total of 26 when you can use each letter just once? What about 8 characters from 62? (Upper case, lower case, 10 digits.)
The last two problems are of the form n choose m and they can be solved with Pascal's Triangle.