Algorithms

Computer Science; Operating Systems; Software Engineering

An algorithm is set of precise, computable instructions that, when executed in the correct order, will provide a solution to a certain problem. Algorithms are widely used in mathematics and engineering, and understanding the design of algorithms is fundamental to computer science.

The term “algorithm” is derived from the name al-Khwarizmi. Muhammad ibn Musa al-Khwarizmi was a ninth-century Persian mathematician who is credited with introducing the decimal system to the West. He has been celebrated around the world as a pioneer of mathematics and conceptual problem solving.

“Algorithm” has no precise definition. Broadly, it refers to a finite set of instructions, arranged in a specific order and described in a specific language, for solving a problem. In other words, an algorithm is like a plan or a map that tells a person or a machine what steps to take to complete a given task.

In computer science, an algorithm is a series of instructions that tells a computer to perform a certain function, such as sorting, calculating, or finding data. Each step in the instructions causes the computer to transition from one state to another until it reaches the desired end state.

Any procedure that takes a certain set of inputs (a data list, numbers, information, etc.) and reaches a desired goal (finding a specific datum, sorting the list, etc.) is an algorithm. However, not all algorithms are equal. Algorithms can be evaluated for “elegance,” which measures the simplicity of the coding. An elegant algorithm is one that takes a minimum number of steps to complete. Algorithms can also be evaluated in terms of “goodness,” which measures the speed with which an algorithm reaches completion.

Algorithms can be described in a number of ways. Flowcharts are often used to visualize and map the steps of an algorithm. The DRAKON computer language, developed in the 1980s, allows users to program algorithms into a computer by creating a flowchart that shows the steps of each algorithm. Such a flowchart is sometimes called a DRAKON chart.

Various types of algorithms take different approaches to solving problems. An iterative algorithm is a simple form of algorithm that repeats the same exact steps in the same way until the desired result is obtained. A recursive algorithm attempts to solve a problem by completing smaller instances of the same problem. One example of a recursive algorithm is called a “divide and conquer” algorithm. This type of algorithm addresses a complex problem by solving less complex examples of the same problem and then combining the results to estimate the correct solution.

Algorithms can also be serialized, meaning that the algorithm tells the computer to execute one instruction at a time in a specific order. Other types of algorithms may specify that certain instructions should be executed simultaneously. Distributed algorithms are an example of this type. Different parts of the algorithm are executed in multiple computers or nodes at once and then combined.

An algorithm may have a single, predetermined output, or its output may vary based on factors other than the input. Deterministic algorithms use exact, specific calculations at every step to reach an answer to a problem. A computer running a deterministic algorithm will always proceed through the same sequence of states. Nondeterministic algorithms incorporate random data or “guessing” at some stage of the process. This allows such algorithms to be used as predictive or modeling tools, investigating problems for which specific data is lacking. In computational biology, for instance, evolutionary algorithms can be used to predict how populations will change over time, given estimations of population levels, breeding rates, and other environmental pressures.

One of the most famous applications of algorithms is the creation of “search” programs used to find information on the Internet. The Google search engine can search through vast amounts of data and rank millions of search results in a specific order for different users. Sorting large lists of data was one of the earliest problems that computer scientists attempted to solve using algorithms. In the 1960s, the quicksort algorithm was the most successful sorting algorithm. Using a random element from the list as a “pivot,” quicksort tells the computer to pick other elements from the list and compare them to the pivot. If the element is less than the pivot, it is placed above it; if it is greater, it is placed below. The process is repeated until each pivot is in its proper place and the data is sorted into a list. Computer scientists are still attempting to find search and sorting algorithms that are more “elegant” or “good” in terms of completing the function quickly and with the least demand on resources.

Searching and sorting are the most famous examples of algorithms. However, these are just two of the thousands of algorithm applications that computer scientists have developed. The study of algorithm design has become a thriving subfield within computer science.

—Micah L. Issitt