An algorithm is a procedure for carrying out a task which, given an initial state, will terminate in a clearly defined end-state. It can be thought of as a recipe, or a step-by-step method, so that in following the steps of the algorithm one is guaranteed to find the solution or the answer. One commentator describes it as:
|“||a finite procedure, written in a fixed symbolic vocabulary, governed by precise instructions, moving in discrete Steps 1, 2, 3, ..., whose execution requires no insight, cleverness, intuition, intelligence, or perspicuity, and that sooner or later comes to an end.||”|
The name is derived from a corruption of Al-Khwārizmī, the Persian astronomer and mathematician who wrote a treatise in Arabic in 825 AD entitled: On Calculation with Hindu Numerals. This was translated into Latin in the 12th century as Algoritmi de numero Indorum. The title translates as "Al-Khwārizmī on the numbers of the Indians", with Algoritmi being the translator's rendition of the original author's name in Arabic. Later writers misunderstood the title, and treated Algoritmi as a Latin plural of the neologism Algoritmus or Algorithmus, and took its meaning to be 'calculation method'. In the Middle Ages there were many variations of this, such as alkorisms, algorisms, algorhythms etc.
There are two main current usages:
- In elementary education, where an 'algorithm' is used for calculation, such as the decomposition algorithm, or the equal addition method of subtraction. Many of these algorithms are, in fact derivations from methods in Al-Khwārizmī's original treatise.
- In computing, where an algorithm is the methodology which underlies a computer program. This tells the computer what specific steps to perform (in what specific order) in order to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards.
All algorithms must adhere to two rules -
- They must work for any given input or network.
- They must have a single start point, and a single finish point.
There is a second type of algorithm - whereas most algorithms provably evaluate the most desirable end-state (for example, it is possible to mathematically prove that Dijkstra's algorithm gives the shortest route from one point to another) - others known as 'heuristic algorithms' cannot provably give the best solution (although they do give a fairly good result). While this may seem inferior, some problems are very difficult or even impossible to map out using normal algorithms, so heuristic ones are superior in these cases.
Examples of Algorithms
Dijkstra's algorithm finds the shortest path through a network, from one point to another.
- Start by labelling the first node (1,0,0). The first number, the ordinal value, denotes the order in which the arcs were labelled, the second, the label value (the distance travelled thus far), while the third, the working value, denotes the possible distance to that point.
- Then, update the working values for nodes separated to the current node(s) by one arc, by adding the weight of the arc to that node to the label value of the node at the other end. This value may decrease during the progression of the algorithm, as new, shorter, routes are found.
- Choose the node with the lowest working value, and promote its working value to the label value, and write in its new ordinal value. For example, if this was the second node labelled, its complete annotation would now read (2, x, x), where 'x' would be the distance between it and the first node.
- Now return to the second step. If there are no more nodes to be added, the algorithm has finished.
The planarity algorithm is used to determine whether a given shape is 2-dimensional or not. It has found particular use in road and circuit board design to avoid cross-overs.
- Identify a Hamiltonian Cycle in the network.
- Redraw the network with the Hamiltonian cycle on the outside.
- Identify any crossings between lines.
- Choose an arc with crossings to stay inside the cycle. Move any arcs with crossings to the outside.
- Repeat from step 3 until there are no more crossings. If this step is completed, it shows that the shape is planar (2-d). If it cannot be completed, the shape is 3-dimensional and not planar.
Critical path analysis
Critical path analysis is used to determine the fastest/most efficient way of completing a series of tasks, which often depend upon each other.
Kruskal's algorithm is used to find the minimum spanning tree in an network that you can see all of.
Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.
The Bellman-Ford algorithm is used to find the shortest path in a graph with negative weighted edges.
The Krim-Jacob algorithm is used to determine if a problem can be solved with abstract time and memory.
The Bin filling algorithm is used to find the most efficient way of combining several differently sized objects into a space(s) with a certain size. An example would be the problem of packing objects into the boot of a car; the bin-filling algorithm is in fact a mathematically formulated version of the rule of thumb 'put the big things in first'; but in can be used for many other problems - loading cars onto ferries, sending messages via routers on the internet, etc. It is a heuristic algorithm, as it does not give a provably maximal solution (the only way to do this, until Vijay Vazirani invented a new form of approximation algorithm, was to arrange the objects in every conceivable order).
- David Berlinski, The Advent of the Algorithm: The Idea that Rules the World (Harcourt Inc.: 2000).