Glossary of Computer Science and Engineering Part 6 - ALGORITHM | HackTHatCORE

ALGORITHM

When people think of computers, they usually think of silicon chips and circuit boards. Moving from relays to vacuum tubes to transistors to integrated circuits has vastly increased the power and speed of computers, but the essential idea behind the work computers do remains the algorithm. An algorithm is a reliable, definable procedure for solving a problem. The idea of the algorithm goes back to the beginnings of mathematics and elementary school students are usually taught a variety of algorithms. For example, the procedure for long division by successive division, subtraction, and attaching the next digit is an algorithm. Since a bona fide algorithm is guaranteed to work given the specified type of data and the rote following of a series of steps, the algorithmic approach is naturally suited to mechanical computation.

Algorithms in Computer Science

Just as a cook learns both general techniques such as how to sauté or how to reduce a sauce and a repertoire of specific recipes, a student of computer science learns both general problem-solving principles and the details of common algorithms. These include a variety of algorithms for organizing data (see sorting and searching ), for numeric problems (such as generating random numbers or finding primes), and for the manipulation of data structures (see list processing and queue ). A working programmer faced with a new task first tries to think of familiar algorithms that might be applicable to the current problem, perhaps with some adaptation. For example, since a variety of well-tested and well-understood sorting algorithms have been developed, a programmer is likely to apply an existing algorithm to a sorting problem rather than attempt to come up with something entirely new. Indeed, for most widely used programming languages there are packages of modules or procedures that implement commonly needed data structures and algorithms (see library , program ). If a problem requires the development of a new algorithm, the designer will first attempt to determine whether the problem can, at least in theory, be solved (see computability and complexity ). Some kinds of problems have been shown to have no guaranteed answer. If a new algorithm seems feasible, principles found to be effective in the past will be employed, such as breaking complex problems down into component parts or building up from the simplest case to generate a solution (see recursion ). For example, the merge-sort algorithm divides the data to be sorted into successively smaller portions until they are sorted, and then merges the sorted portions back together. Another important aspect of algorithm design is choosing an appropriate way to organize the data (see data structures ). For example, a sorting algorithm that uses a branching (tree) structure would probably use a data structure that implements the nodes of a tree and the operations for adding, deleting, or moving them (see class ). Once the new algorithm has been outlined (see pseudo - code ), it is often desirable to demonstrate that it will work for any suitable data. Mathematical techniques such as the finding and proving of loop invariants (where a true assertion remains true after the loop terminates) can be used to demonstrate the correctness of the implementation of the algorithm.

Practical Considerations

It is not enough that an algorithm be reliable and correct, it must also be accurate and efficient enough for its intended use. A numerical algorithm that accumulates too much error through rounding or truncation of intermediate results may not be accurate enough for a scientific application. An algorithm that works by successive approximation or convergence on an answer may require too many iterations even for today’s fast computers, or may consume too much of other computing resources such as memory. On the other hand, as computers become more and more pow- erful and processors are combined to create more powerful supercomputers (see supercomputer and concurrent programming ), algorithms that were previously considered impracticable might be reconsidered. Code profiling (analysis of which program statements are being executed the most frequently) and techniques for creating more efficient code can help in some cases. It is also necessary to keep in mind special cases where an otherwise efficient algorithm becomes much less efficient (for example, a tree sort may work well for random data but will become badly unbalanced and slow when dealing with data that is already sorted or mostly sorted). Sometimes an exact solution cannot be mathematically guaranteed or would take too much time and resources to calculate, but an approximate solution is acceptable. A so called “greedy algorithm” can proceed in stages, testing at each stage whether the solution is “good enough.” Another approach is to use an algorithm that can produce a reasonable if not optimal solution. For example, if a group of tasks must be apportioned among several people (or computers) so that all tasks are completed in the shortest possible time, the time needed to find an exact solution rises exponentially with the number of workers and tasks. But an algorithm that first sorts the tasks by decreasing length and then distributes them among the workers by “dealing” them one at a time like cards at a bridge table will, as demonstrated by Ron Graham, give an allocation guaranteed to be within 4/3 of the optimal result—quite suitable for most applications. (A procedure that can produce a practical, though not perfect solution is actually not an algorithm but a heuristic.) An interesting approach to optimizing the solution to a problem is allowing a number of separate programs to “compete,” with those showing the best performance surviving and exchanging pieces of code (“genetic material”) with other successful programs (see genetic algorithms ). This of course mimics evolution by natural selection in the biological world.

References:

• Berlinksi, David. The Advent of the Algorithm: The Idea That Rules the World. New York: Harcourt, 2000.
• Cormen, T. H., C. E. Leiserson, R. L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, Mass.: MIT Press, 2001.
• Knuth, Donald E. The Art of Computer Programming. Vol. 1: Funda- mental Algorithms. 3rd ed. Reading, Mass.: Addison-Wesley, 1997. Vol. 2: Seminumerical Algorithms. 3rd ed. Reading, Mass.: Addison-Wesley, 1997. Vol. 3: Searching and Sorting. 2nd ed. Reading, Mass.: Addison-Wesley, 1998.