Algorithm

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 you are guaranteed to find the solution or the answer. The name is derived from a corruption of Al-Khwārizmī, the Persian astronomer and mathematician, wrote a treatise in Arabic in 825 AD, entitled: On Calculation with Hindu Numerals. This was translated into Latin in 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 as 'calculation method'. In the Middle Ages there were many variants on this, such as alkorisms, algorisms, algorhythms etc.

There are two main current usages:

1. 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.
2. 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.

Examples of Algorithms

Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path through a network, from one point to another.

1. 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.
2. 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.
3. 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.
4. Now return to the second step. If there are no more nodes to be added, the algorithm has finished.

Planarity algorithm

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.

1. Identify a Hamiltonian Cycle in the network.
2. Redraw the network with the Hamiltonian cycle on the outside.
3. Identify any crossings between lines.
4. Choose an arc with crossings to stay inside the cycle. Move any arcs with crossings to the outside.
5. 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.

See also

computability