Monday, April 18, 2011

What is an Algorithm?

In its most general sense, an algorithm is any set of detailed instructions which results in a predictable end-state from a known beginning. Algorithms are only as good as the instructions given, however, and the result will be incorrect if the algorithm is not properly defined.

A common example of an algorithm would be instructions for assembling a model airplane. Given the starting set of a number of marked pieces, one can follow the instructions given to result in a predictable end-state: the completed airplane. Misprints in the instructions, or a failure to properly follow a step will result in a faulty end product.

A computer program is another pervasive example of an algorithm. Every computer program is simply a series of instructions (of varying degrees of complexity) in a specific order, designed to perform a specific task. Most conceptions of the human brain define all behavior — from the acquisition of food to falling in love — as the result of a complex algorithm.

While there is no universally accepted breakdown for the various types of algorithms, there are common classes that algorithms are frequently agreed to belong to. Among these are:

Dynamic Programming Algorithms: This class remembers older results and attempts to use this to speed the process of finding new results. 

Brute Force Algorithms: The brute force approach starts at some random point and iterates through every possibility until it finds the solution. 

Branch and Bound Algorithms: Branch and bound algorithms form a tree of sub problems to the primary problem, following each branch until it is either solved or lumped in with another branch.

Simple Recursive Algorithms: This type of algorithm goes for a direct solution immediately, then backtracks to find a simpler solution.

Backtracking Algorithms: Backtracking algorithms test for a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.

Divide and Conquer Algorithms: A divide and conquer algorithm is similar to a branch and bound algorithm, except it uses the backtracking method of recurring in tandem with dividing a problem into sub problems.

In addition to these general classes, algorithms may also be divided into two primary groups: serial algorithms, which are designed for serial execution, wherein each operation is enacted in a linear order; and parallel algorithms, used with computers running parallel processors (as well as existing in the natural world in the case of, for example, genetic mutation over a species), wherein a number of operations are run in parallel.

No comments:

Post a Comment