Algorithm

From Conservapedia

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:^[1]

“

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.

Computational Complexity[edit]

One aspect of algorithms implemented in computer programs is that of computational complexity, which denotes how efficient (fast) they are. Asymptotic Notation is the formal means of describing the running time of an algorithm and the size of its inputs.^[2] The most commonly used notation is called "Big O", which is used to give an upper bound on the computational complexity of the routine. Some examples:

O(1) indicates constant running time.
O(n) indicates running time that is linear with the size of the inputs.
O(log n) indicates running time that is logarithmic.
O(n^x) indicates polynomial running time. For instance, O(n²) indicates that the algorithm is quadratic - that the running time increases as the square of the size of the input.

Categories of Algorithms[edit]

Algorithms can be categorized several ways.

Pathfinding[edit]

Pathfinding algorithms are commonly used. For instance, route finding apps on cell phones use pathfinding to determine the quickest route between two points. A-Star and Dijkstra's algorithm are examples of pathfinding algorithms.

Greedy Algorithms[edit]

Algorithms which find local optimizations instead of global optimizations are referred to as greedy. Although they may not return an optimal result, they tend to execute much faster than non-greedy algorithms.

Sorting[edit]

Sorting algorithms are used to order data.

Searching[edit]

Search algorithms find data matching a certain criteria, using some form of pattern matching, within a larger set of data.

Pattern Matching[edit]

Pattern matching algorithms are used to match different data. Regular Expressions are a way of describing a pattern and are commonly used for pattern matching algorithms.

Evolutionary algorithm[edit]

An Evolutionary algorithm is a type of stochastic numerical analysis.

Numerical[edit]

Numerical algorithms deal directly with numbers. They can be arithmetical (such as performing division), or seminumerical (such as generating random values). Note: Donald Knuth believed this was a more proper term for all numerical algorithms^[3]

Examples of Algorithms[edit]

Dijkstra's algorithm[edit]

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.

Planarity algorithm[edit]

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[edit]

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[edit]

Kruskal's algorithm is used to find the minimum spanning tree in an network that you can see all of.

Prim's algorithm[edit]

Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.

Bellman-Ford algorithm[edit]

The Bellman-Ford algorithm is used to find the shortest path in a graph with negative weighted edges.

Krim-Jacob algorithm[edit]

The Krim-Jacob algorithm is used to determine if a problem can be solved with abstract time and memory.

Bin-filling algorithm[edit]

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).

References[edit]

↑ David Berlinski, The Advent of the Algorithm: The Idea that Rules the World (Harcourt Inc.: 2000).
↑ John V. Guttag, Introduction to Computation and Programming Using Python (MIT Press:2016)
↑ Donald Knuth, The Art of Computer Programming: Seminumerical Algorithms (Addison Wesley:1969)