Algorithm

In mathematics and computing, an algorithm is a finite sequence of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. Informally, the concept of an algorithm is often illustrated by the example of a recipe, albeit more complex. Algorithms often contain steps that repeat (iterate) or require decisions, such as by using logic or comparisons.

Algorithms constitute a foundational concept in computer science. In most higher-level computer programs, algorithms act in complex patterns, each using smaller and smaller sub-methods, which are built up to the program as a whole. In other words, a computer program may be regarded as an algorithm that has nested sets of smaller algorithms within it. Most algorithms can be directly implemented by computer programs; any other algorithms can at least in theory be simulated by computer programs.

History

As early as 1600 B.C.E., the Babylonians developed algorithms for factorization and finding square roots of numbers. The Euclidean algorithm, given in Euclid's Elements around 300 B.C.E., was useful for determining the greatest common divisor of two integers, among other things. The latter algorithm was probably not discovered by Euclid and may have been known by the Greeks up to 200 years earlier.

Between CE 813 and 833, Persian mathematician Al-Khawarizmi (Abu Ja'afar Abdullah Muhammad Ibn Mūsā al-Khawārizmī) described a procedure for solving linear equations and quadratic equations. The word "algorithm," used for such a procedure, comes from his name.

Initially, the term "algorism" was used to refer to the rules of performing arithmetic computations with Hindu-Arabic numerals. Later, based on European Latin translations of al-Khwarizmi's name, the word evolved into "algoritmi" and then "algorithm" by the eighteenth century. The meaning of the word was also broadened to include all definite mathematical procedures for solving problems or performing tasks.

The lack of mathematical rigor in the "well-defined procedure" definition of algorithms posed some difficulties for mathematicians and logicians of the nineteenth and early twentieth centuries. Their understanding of algorithms, however, was greatly improved in 1936, with Alan Turing's description of the "Turing machine" (an abstract model of a computer), and the assertion that all possible calculations can be emulated on a Turing machine—a statement known as the "Church-Turing thesis," which has so far not been contradicted. Currently, a formal criterion for an algorithm is that it is a procedure that can be implemented on a completely specified Turing machine or equivalent formalism. In this manner, the concept of an algorithm has become a foundation for the development of computer science.

The first case of an algorithm written for a computer occurs in Ada Lovelace's notes on Charles Babbage's analytical engine, written in 1842. For that, she is considered by many to be the world's first programmer. Babbage, however, never completed his analytical engine, and the algorithm was never implemented on it.

Formalization of algorithms

Algorithms are essential to the way computers process information. A computer program is basically an algorithm that tells the computer what specific steps to perform, and in what order, to carry out a specified task. The task could be something like calculating employees’ paychecks or printing students’ report cards. In formal terms, an algorithm can be considered to be any sequence of operations that can be performed by a "Turing-complete" system—that is, a programming language that has a computational power equivalent to a universal Turing machine.

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 stored for further processing. Such data is stored in a data structure (a tool for efficiently storing data in a computer), and a predefined set of operations may be performed on it based on the demands of the algorithm.

For any such computational process, an algorithm must be rigorously defined—that is, specified in a way that applies to all possible circumstances. In other words, it must be able to deal with any possible discrepancy, error, or alternative situation occurring during the computation. For example, it needs to be able to deal with an invalid input, such as a letter instead of a number.

Algorithms generally execute their operations in sequential order: From top to bottom, and left to right. Occasionally, however, certain control structures (such as loops) can alter the order in which a particular segment of the program is conducted.

A computer program may be regarded as an algorithm that has a set of smaller algorithms within it, and each of these may contain additional subsets of algorithms. 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, each sub-algorithm is designed to complete a specific task, and the main algorithm brings the results of these tasks together to generate a solution (or output) for the computational problem.

This type of formalization of an algorithm is based on the premises of "imperative programming"—a formalism that describes a task in discrete, "mechanical" terms. Unique to this concept of formalized algorithms is the "assignment operation," setting the value of a variable. It derives from the intuition of "memory" as a scratch pad. (Alternate concepts of an algorithm can be found in "functional programming" and "logic programming.")

Knuth's characterization

Donald Knuth made a list of five properties that are still widely accepted as requirements for an algorithm:^[1]

1. Finiteness: "An algorithm must always terminate after a finite number of steps."
2. Definiteness: "Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case."
3. Input: "…quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects."
4. Output: "…quantities which have a specified relation to the inputs."
5. Effectiveness: "…all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil."

An example of such an algorithm would be the Euclidean algorithm for determining the greatest common divisor of two natural numbers.

This description of an algorithm is intuitively clear but lacks formal rigor. Some terms—such as "precisely defined," "rigorously and unambiguously specified," or "sufficiently basic,"—are not exactly clear.

Thus the academically accepted definition of an algorithm stipulates a finite time frame of operation. Some, however, insist that the definition should include procedures that may run forever without stopping, arguing that some entity may be required to carry out such tasks. In such a case, the success of the algorithm needs to be redefined, to allow for output sequences that are unconstrained by time. 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 implemented correctly, the algorithm's output will be useful. For as long as it examines the sequence, the algorithm gives a positive response when the number of examined zeros outnumber the ones, and a negative response otherwise. Success for this algorithm could then be defined as eventually producing only positive responses if the sequence has more zeros than ones, and producing mixtures of positive and negative responses in other cases.

Expressing algorithms

Algorithms can be expressed in many types of notation, such as natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and they 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 they are often used as a way to define or document algorithms.

Implementation

Most algorithms are intended to be implemented as computer programs. Many algorithms, however, are implemented by other means, such as a biological neural network—the human brain implementing arithmetic or an insect relocating food—or an electric circuit, or a mechanical device.

Examples

One of the simplest algorithms is to pick out the largest number from 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 follows:

1. Assume the first item is the largest.
2. Look at each of the remaining items in the list, and if a particular item is larger than the largest item found so far, make a note of it.
3. The last noted item is the largest in the list when the process is complete.

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

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

  if L.size = 0 return null
         largest ← L[0]
         for each item in L, do
           if item > largest, then
             largest ← 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.

Below is a much simpler algorithm presented somewhat formally but still in English instead of pseudocode. It determines whether 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

A more complex example is 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 above algorithm 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 needs to remember only 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) In this example the sizes of the numbers themselves could be unbounded and one could therefore argue that the space requirement is O(log n). In practice, however, the numbers considered would be bounded and hence the space taken up by each number is fixed. (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, consider two different recipes for making a casserole: One is a frozen package and simply needs to be warmed up in the microwave; but the other spells out how to make a casserole from scratch and involves using a conventional oven. Both recipes end up with roughly the same dish, but each has a different time and space requirement.

The analysis and study of algorithms is a field within 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, 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 control 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:

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

• A Dynamic programming 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.

• 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. The 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 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 the theory of biological evolution, in which cycles of "random mutations" are thought to yield successive generations of "solutions." This process is likened to the concept of "survival of the fittest." In genetic programming, the algorithm is regarded 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 optimization in resource consumption in industries, but it is used in solving a broad range of problems in many fields.

Classification by complexity

Some algorithms complete in linear time, some complete in an 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 their complexity.

Notes

References

ISBN links support NWE through referral fees

• Church, Alonzo. "An Unsolvable Problem of Elementary Number Theory" The American Journal Of Mathematics 58 (1936): 345-363.
• Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions New York:Raven Press, 1965.
• Knuth, Donald E. The Art of Computer Programming, Volume 1/Fundamental Algorithms (2nd ed.) Addison-Wesley, 1973. ISBN 0201038099
• Post, Emil. "Finite Combinatory Processes, Formulation I" The Journal of Symbolic Logic 1 (1936): 103-105.
• Rosser, J.B. "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem" Journal of Symbolic Logic 4 (1939).

External links

All links retrieved May 16, 2021.

• Algorithms Everyday Mathematics