Algorithm

File:Flowchart.png

Flowcharts are often used to graphically represent algorithms.

In mathematics and computing, an algorithm is a finite sequence of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.

Informally, the concept of an algorithm is often illustrated by the example of a recipe, albeit more complex; and they often contain steps that repeat (iterate) or require decisions (such as logic or comparison). In most higher level programs, algorithms act in complex patterns, each using smaller and smaller sub-methods which are built up to the program as a whole. In most languages, they are synonymous with functions or methods.

Most algorithms can be directly implemented by computer programs; any other algorithms can at least in theory be simulated by computer programs.

History

The word algorithm comes from the Latin name of the 9th century Persian mathematician Abu Abdullah Muhammad ibn Musa al-Khwarizmi. The word algorism originally referred only to the rules of performing arithmetic using Hindu-Arabic numerals but evolved via European Latin translation of al-Khwarizmi's name, ‘’algoritmi’’, into algorithm by the 18th century. The word evolved to include all definite procedures for solving problems or performing tasks.

The concept of an algorithm originated as a means of recording procedures for solving mathematical problems such as finding the common divisor of two numbers or multiplying two numbers. The concept was formalized in 1936 through Alan Turing's Turing machines and Alonzo Church's lambda calculus, which in turn formed the foundation of computer science. The first case of an algorithm written for a computer was Ada Lovelace's notes on the analytical engine written in 1842, for which she is considered by many to be the world's first programmer. However, since Charles Babbage never completed his analytical engine, the algorithm was never implemented on it.

The lack of mathematical rigor in the "well-defined procedure" definition of algorithms posed some difficulties for mathematicians and logicians of the 19th and early 20th centuries. This problem was largely solved with the description of the Turing machine, an abstract model of a computer formulated by Alan Turing, and the demonstration that every method yet found for describing "well-defined procedures" advanced by other mathematicians could be emulated on a Turing machine (a statement known as the Church-Turing thesis). Nowadays, a formal criterion for an algorithm is that it is a procedure that can be implemented on a completely specified Turing machine or one of the equivalent formalisms (emphasis of form over content or meaning).

<NOTE: THIS SECTION IS A STUB. YOU CAN HELP BY ADDING TO IT.>

Formalization of algorithms

Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform, and in what specific order, to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations which can be performed by a Turing-complete system.

Typically, when an algorithm is associated with processing information, data is read from an input source or device, written to an output sink or device, and/or stored for further processing. Such data is stored in a data structure (a tool for efficiently and cheaply storing data in a computer), and a predefined set of operations may be performed on it as per the demands of the algorithm.

For any such computational process, an algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise. In other words, it must be able to account for any possible discrepancy, error, or alternative situation occurring during its computation and to deal with it. An example of such would be an invalid input (i.e. a letter where a number is requested).

Algorithms generally execute in sequential order, from top to bottom, left to right; although certain control structures, such as loops, can alter the order in a particular segment of the program. A program is basically an algorithm that has a number of smaller algorithms within it, and each of those algorithms may have yet more within them. This design is called Top-down Design, where each level of abstraction (from the main algorithm to the sub-algorithms and so on) increases in specificity and detail. To illustrate, the main algorithm may not execute much other than the sub-algorithms, but each sub-algorithm completes a specific task, the sum of which result in an output, or solution to the computation.

So far, this discussion of the formalization of an algorithm has assumed the premises of imperative programming (formalism that describes a task in discrete, 'mechanical' terms). Unique to this conception of formalized algorithms is the assignment operation, setting the value of a variable. It derives from the intuition of 'memory' as a scratchpad.

See functional programming and logic programming for alternate conceptions of what constitutes an algorithm.

The academically accepted definition of an algorithm stipulates a finite timeframe of operation. Some insist that the definition include procedures that could run forever without stopping, arguing that some entity may be required to carry out such permanent tasks. In such a case, the success of the algorithm then needs to be redefined to allow for unbounded output sequences (not time constrained). For example, an algorithm that verifies if there are more zeros than ones in an infinite random binary sequence must run forever to be effective. If it is implemented correctly, the algorithm's output will be useful: for as long as it examines the sequence, the algorithm will give a positive response while the number of examined zeros outnumber the ones, and a negative response otherwise. Success for this algorithm could then be defined as eventually outputting only positive responses if there are actually more zeros than ones in the sequence, and in any other case outputting any mixture of positive and negative responses.

Summarizing the above discussion about what an algorithm should consist of:

• Zero or more Inputs
• One or more Outputs
• Finiteness or computability
• Definitiveness or Preciseness

Expressing algorithms

Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while avoiding implementation details. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.

Implementation

Most algorithms are intended to be implemented as computer programs. However, algorithms are also implemented by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect relocating food), in electric circuits, or in a mechanical device.

Examples

One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm, which can be stated in English as:

1. Let us assume the first item is largest.
2. Look at each of the remaining items in the list and make the following adjustment.

   a. If it is larger than the largest item we gathered so far, make a note of it.

3. The latest noted item is the largest in the list when the process is complete.

Here is a more formal coding of the algorithm in pseudocode:

Algorithm LargestNumber

  Input: A non-empty list of numbers L.
  Output: The largest number in the list L.

  largest ← L0
  for each item in the list L≥1, do
    if the item > largest, then
      largest ← the item
  return largest

• "←" is a loose shorthand for "changes to". For instance, with "largest ← the item", it means that the largest number found so far changes to this item.
• "return" terminates the algorithm and outputs the value listed behind it.

Here is a much simpler algorithm described somewhat formally but still in English instead of pseudocode. It determines if a given number n is even or odd:

1. BEGIN
2. Read the value of n.
3. Divide n by 2 and store the remainder in rem.
4. If rem is 0, go to step 7.
5. Print "n is an odd number".
6. Go to step 8.
7. Print "n is an even number".
8. END

For a more complex example, see Euclid's algorithm, which is one of the oldest algorithms.

Algorithm analysis

As it happens, most people who implement algorithms want to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember two values: the largest number found so far, and its current position in the input list. Therefore it is said to have a space requirement of O(1). (Note that the size of the inputs is not counted as space used by the algorithm.)

Different algorithms may complete the same task with a different set of instructions in less or more time, space, or effort than others. For example, given two different recipes for making a casserole, one is a frozen package and simply requires one to warm it up in the microwave, but the other spells out how to make a casserole from scratch and uses conventional oven. Both recipes end up with roughly the same dish, but each one has a different time and space requirement.

The analysis and study of algorithms is one discipline of computer science, and is often practiced abstractly (without the use of a specific programming language or other implementation). In this sense, it resembles other mathematical disciplines in that the analysis focuses on the underlying principles of the algorithm, and not on any particular implementation. The pseudocode is simplest and abstract enough for such analysis.

Classes

There are various ways to classify algorithms, each with its own merits.

Classification by implementation

One way to classify algorithms is by implementation means.

• Recursion or iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition is met, a method common to functional programming. Iterative algorithms use repetitive constrol structures, like loops, to solve the given problems. A programmer has to determine which method is best to use for a particular problem.

• Serial or parallel: Algorithms that are executed sequentially (one at a time) are known to be ‘’serial’’. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time. Parallel algorithms divide the problem into more symmetrical or asymmetrical sub-problems and pass them to many processors and put the results back together at the end. Problems that have no parallel algorithms are called ‘’inherently serial problems’’.

• Deterministic or random: Deterministic algorithms solve problems with exact decisions at every step of the algorithm. Randomized algorithms as their name suggests explore the search space randomly until an acceptable solution is found.

• Exact or approximate: While many algorithms reach an exact solution, approximation algorithms seek an approximation which is close to the true solution. Approximation may use either a deterministic or a random strategy. Such algorithms have practical value for many hard problems, usually dealing with physical situations.

Classification by design paradigm

Another way of classifying algorithms is by their design methodology or paradigm. There are a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:

• Divide and conquer. A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively), until the instances are small enough to solve easily. An example of such is Binary Search; given a sorted list of characters and a target character, it will check the midpoint character in the list and tests to see if it is the target character, and if not, whether the target is above or below the midpoint. Then, it uses the midpoint character as one of the bounds and then checks the new midpoint character of the one half of the list it is now searching. It repeats this procedure until the target is found or it cannot continue.

• Dynamic programming. This algorithm is used when a problem requires the same task or calculation to be done repeatedly throughout the program. Removing the redundancy can optimize such a program, which is done by performing the repeated operations just once and storing the result for later use.

• The greedy method. A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the sub-problems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment. Difference between dynamic programming and greedy method is, it extends the solution with the best possible decision (not all feasible decisions) at an algorithmic stage based on the current local optimum and the best decision (not all possible decisions) made in previous stage. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method.

• Linear programming. When solving a problem using linear programming, the program is put into a number of linear inequalities and then an attempt is made to maximize (or minimize) the inputs. Many problems (such as the maximum flow for directed graphs) can be stated in a linear programming way, and then be solved by a 'generic' algorithm such as the simplex algorithm. A complex variant of linear programming is called integer programming, where the solution space is restricted to all integers.

• Reduction: It is another powerful technique in solving many problems by transforming one problem into another problem. For example, one selection algorithm for finding the median in an unsorted list is first translating this problem into sorting problem and finding the middle element in sorted list. The goal of reduction algorithms is finding the simplest transformation such that the complexity of the reduction algorithm does not dominate the complexity of the reduced algorithm. This technique is also called transform and conquer.

• Search and enumeration. Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes the search algorithms and backtracking.

• The probabilistic and heuristic paradigm. Algorithms belonging to this class fit the definition of an algorithm more loosely.

1. Probabilistic algorithms are those that make some choices randomly (or pseudo-randomly); for some problems, it can in fact be proven that the fastest solutions must involve some randomness.
2. Genetic algorithms attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations yielding successive generations of "solutions". Thus, they emulate reproduction and "survival of the fittest". In genetic programming, this approach is extended to algorithms, by regarding the algorithm itself as a "solution" to a problem.
3. Heuristic algorithms, whose general purpose is not to find an optimal solution, but an approximate solution where the time or resources to find a perfect solution are not practical. An example of this would be local search, taboo search, or simulated annealing algorithms, a class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount.

Classification by field of study

Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms, string algorithms, computational geometric algorithms, combinatorial algorithms, machine learning, cryptography, data compression algorithms and parsing techniques.

Some of these fields overlap with each other and advancing in algorithms for one field causes advancement in many fields and sometimes completely unrelated fields. For example, dynamic programming is originally invented for optimisation in resource consumption in industries, but it is used in solving broad range of problems in many fields.

Classification by complexity

Some algorithms complete in linear time, and some complete in exponential amount of time, and some never complete. One problem may have multiple algorithms, and some problems may have no algorithms. Some problems have no known efficient algorithms. There are also mappings from some problems to other problems. So computer scientists found it is suitable to classify the problems rather than algorithms into equivalence classes based on the complexity.

See also

• Algorism
• Algorithmic music
• Algorithmic trading
• Data structure
• Important algorithm-related publications
• List of algorithm general topics
• List of terms relating to algorithms and data structures

References

ISBN links support NWE through referral fees

• Knuth, Donald E. (1973). The Art of Computer Programming, Volume 1/Fundamental Algorithms, Second Edition, Addison-Wesley.  In pages 1-9 Knuth gives the history and his definition of "algorithm".
• Post, Emil (1936). Finite Combinatory Processes, Formulation I. The Journal of Symbolic Logic 1: pp.103-105. Reprinted in The Undecidable, p. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called Church-Turing thesis.
• Rosser, J.B. (1939). An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem. Journal of Symbolic Logic 4. Reprinted in The Undecidable, p. 223ff. Herein is Rosser's famous definition of "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (p. 225-226, The Undecidable)
• Church, Alonzo (1936). An Unsolvable Problem of Elementary Number Theory. The American Journal Of Mathematics 58: 345—363. Reprinted in The Undecidable, p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (The Undecidable) where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.
• Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propostions, Unsolvable Problems and Computable Functions. New York: Raven Press.  Davis gives commentary before each article. Papers of Gödel, Church, Turing, Rosser, Kleene, and Post are included.
• Paul E. Black, algorithm at the NIST Dictionary of Algorithms and Data Structures.

External links

• Eric W. Weisstein. Algorithm. MathWorld
• Algorithms in Everyday Mathematics
• Algorithms at the Open Directory Project

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

• Algorithm  ^history

The history of this article since it was imported to New World Encyclopedia:

• History of "Algorithm"

Note: Some restrictions may apply to use of individual images which are separately licensed.