Computer Algorithms

An algorithm can be written as a series of steps. Computers only do what they are told, so the algorithm must not omit any important steps, otherwise the problem will not be solved. But adding unnecessary steps is unwise because this will increase the program's run time.

Computers operate with a binary language called machine language - words or strings of 1s and 0s - that is difficult and cumbersome for programmers to use. Although all programs eventually must be translated into machine language, most programmers write programs in languages such as BASIC or C, which contain a set of commands and operations that humans can more readily understand. Programs called compilers or interpreters then translate these instructions into machine language.

Programmers often begin with an outline or a sequence of steps the algorithm is to accomplish. For example, consider the problem of finding the largest number in a list. The steps may be written as follows.

1. Input the list of numbers.
2. Store the first number in a location called Maximum.
3. Store the next number in a location called Next and compare the value of Maximum with that of Next.
4. If Maximum's value equals or exceeds that of Next, discard the number in Next. If not, replace the value of Maximum with Next's value.
5. Repeat steps 3-5 until the end of the list is reached.
6. Output Maximum.

More complicated problems involve a lot more steps. Deep Blue, the IBM computer that beat reigning champion Garry Kasparov in chess in 1997, ran a considerably longer program.

Finding the maximum number in a list is a simple problem with a simple solution, but even simple solutions may take a long time. The TSP is an excellent example. Because it is a practical problem as well as representative of a large class of interesting problems in computer science, it has been much studied. Writing in the February 15, 1991, issue of Science, researchers Donald L. Miller, at E. I. du Pont de Nemours and Company, in Delaware, and Joseph F. Pekny, at Purdue University, in Indiana, observed, "Few mathematical problems have commanded as much attention as the traveling salesman problem."

A brute force approach to solving a TSP would calculate each possible distance. A more thrifty approach is to use heuristics - shortcuts to speed up the computation, such as the author's assumption, as mentioned in the sidebar, that the shortest route would not contain the longest intercity distance. Shin Lin and Brian Kernighan published a heuristic in 1973, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," in Operations Research, that uses a complicated procedure. But these procedures are not guaranteed to find the optimal solution. Instead, the goal is to find a good solution in a reasonable amount of time.

Take a minute and look at the Emtek door hardware and Epilady hair removal on the author's websites.