Let’s get right back down to basics and look at what an algorithm is. There are several different types, and it can all get a little bit confusing sometimes. It can be very complicated and it can also be simple. If you intend to make complicated ones, then you’ll need to delve into the depths of computer science, linguistics, maths or whatever is it you’re doing. Otherwise, let’s press on. We’re going to KISS…
First of all a very short history:
The concept of the algorithm was formalized in 1936 with Alan Turing’s Turing machines and Alonzo Church’s lambda calculus. This formed the foundation of computer science.
There are many definitions but there I will give you my own explanation. (Feel free to comment and complement it if you would like to):
It is basicaly a method. A set of well defined instructions which allow for something to happen. There is an initial state (a starting point), then the instructions are processed which produces a set of sequential and different states, then finally there is a result and the terminating state. Something is called an algorithm when it follows this formula. It needs to have a terminating state – otherwise there is no output.
One of my heroes, Marvin Minsky said:
“If the length of the process is not known in advance, then “trying” it may not be decisive, because if the process does go on forever — then at no time will we ever be sure of the answer “
There is a nice Microsoft paper called “Algorithms: A quest for absoloute definitions” if you want more.
Why do we need them?
Well because humans are basically rubbish compared to computers at following complex instructions at speed. In fact some idividuals find it hard to carry out even simple instructions, right?
Some different types:
Dynamic Programming Algorithms: remembers old results and uses these to speed up the discovery of new results.
Greedy algorithms: these try to find a solution but also the ideal solution.
Brute force: These start at a random point and iterate through all of the possibilities until it finds the solution.
Randomized: they use any random number at any state.
Branch & bound: they form a tree of subproblems to the actual given problem and each branch is followed until the problem is solved.
Simple recursive: these test for solutions and recur until one is found.
Backtracking: It tries to find the solution straight away and if it doesn’t it backtracks to find the next best one.
Divide and conquer: these backtrack as well as dividing the problem into subproblems (like the Branch & Bound one)
The deterministic algorithm: It makes transitions from one state to the next, seqentially.
The probabilistic algorithm: It works following random states.
There are many many others and you can look at Sun’s excellent tutorial.
Creating an algorithm:
First you need to have a problem to solve, and be very clear about what you intend to do with the output. The reason I say this is that sometimes it’s possible to get sidetracked and solve problems that really aren’t that useful. Usually this happens when an algorithm maker is tired and drowning in complex problems!
Second, because algorithms are invisible, and that you can’t touch them like you would engines in machanics for example, we need an abstract way of visualising the algorithm. This is so that we can see and manipulate it effectively. Diagrams are used, like flow charts and software like Visio is a big favourite too.
Writing “pseudocode” is also useful, it’s a human expression of the computational method. If we write them all out in natural language, then it’s not so easy to understand and in my experience you end up with a lot of waffle too. Using pseudocode and diagrams ensures that you are conscise and precise. The flowchart used is a “state diagram” which represents each state of the system. You might be familiar with UML, this is also a state diagram.
Here is a basic algorithm called “Make cereal”:
–>if no bowl: abort
–>if no cereal: abort
->Pour cereal in bowl
–>if no milk: abort
->Pour into bowl
Thirdly, you need to put the algorithm into machine code which works best for you and the machine and get it right. Some code will be better for a specific problem, for example Perl is better at natural language processing than Java. Next, you need to run the program and this will show you where the holes in the algorithm are or where your design fails.
Why should you care?
In the SEO circles, everyone constantly talks about “algorithms” but not everyone knows what they actually are, so this very short explanation should help clear up any basic misunderstandings.