Algorithms and Environmental Engineering - Mathematics and Statistics for the Environment - page 93

Algorithms exist for many purposes and are expressed in many different ways. Examples of algo-
rithms include recipes in cook books, servicing instructions in the manual of a computer, knitting
patterns, digital instructions for a welding robot indicating where each weld should be made, or
cyber-speak for any system used in cyberspace.
Algorithms can be used in sorting operations—for example, to reorder a list into some defined
sequence. It is possible to express an algorithm as instructions given to a human who has a similar
requirement to reorder some list—for example, to sort a list of tax records into a sequence deter-
mined by the date of birth on the record. These instructions could employ the insertion sort algo-
rithm , the bubble sort algorithm , or one of many other available algorithms. Thus, an algorithm, as
a general technique for expressing the process of completing a defined task, is independent of the
precise manner in which it is expressed.
Sorting is by no means the only application for which algorithms have been developed. Practical
applications of algorithms include the following examples:
• Internet routing (e.g., single-source shortest paths)
• Search engine (e.g., string matching)
• Public-key cryptography and digital signatures (e.g., number-theoretic algorithms)
• Allocating scarce resources in the most beneicial way (e.g., linear programming)
Algorithms are at the core of most technologies used in contemporary computers:
• Hardware design uses algorithms.
• The design of any GUI relies on algorithms.
• Routing in networks relies heavily on algorithms.
• Compilers, interpreters, and assemblers make extensive use of algorithms.
A few classic algorithms are commonly used to illustrate the function, purpose, and applicability
of algorithms. One of these classics is known as the Byzantine Generals (Black, 2012). Briefly, this
algorithm is about the problem of reaching a consensus among distributed units if some of them
give misleading answers. The problem is couched in terms of generals deciding on a common plan
of attack. Some traitorous generals may lie about whether they will support a particular plan and
what other generals told them. What decision-making algorithm should the generals use to reach a
consensus through only an exchange of messages? What percentage of liars can the algorithm toler-
ate and still correctly determine a consensus?
Another classic algorithm that is used to illustrate how an algorithm can be applied to real-
world situations (because of its general usefulness and because it is easy to explain to just about
anyone) is the Traveling Salesman problem. The Traveling Salesman problem is the most notori-
ous NP-complete problem; that is, no polynomial-time algorithm has yet been discovered for an
NP-complete problem, nor has anyone yet been able to prove that no polynomial-time algorithm
can exist for any one of them. For the Traveling Salesman problem, imagine that a traveling sales-
man has to visit each of a given set of cities by car, but he can only stop in each city one time. In
Figure 4.1A, find the shortest possible route that visits each city once and returns to the origin city
(Figure 4.1B).
We have pointed out some of the functions that algorithms can perform, but the question arises:
“Can every problem be solved algorithmically?” The simple and complex answer is no . For exam-
ple, for some problems no generalized algorithmic solution can possibly exist (they are unsolvable).
Also, some problems— NP-complete problems —have no known efficient solutions; that is, it is
unknown if efficient algorithms exist for these problems. If an efficient algorithm exists for any one
of them, then efficient algorithms exist for all of them (e.g., Traveling Salesman problem). Finally,
problems exist that we simply do not know how to solve algorithmically. From this discussion, it
should be apparent that computer science is not simply about word processing and spreadsheets.