The complete disruption of the old agrarian order of the tribal communities
Sorting is by no means the only computational problem for which algorithms have
been developed. (You probably suspected as much when you saw the size of this
book.) Practical applications of algorithms are ubiquitous and include the following
examples:
The Human Genome Project has made great progress toward the goals of identifying
all the roughly 30,000 genes in human DNA, determining the sequences
of the roughly 3 billion chemical base pairs that make up human DNA, storing
this information in databases, and developing tools for data analysis. Each
of these steps requires sophisticated algorithms. Although the solutions to the
various problems involved are beyond the scope of this book, many methods to
solve these biological problems use ideas presented here, enabling scientists to
accomplish tasks while using resources efûciently. Dynamic programming, as
in Chapter 14, is an important technique for solving several of these biological
problems, particularly ones that involve determining similarity between DNA
sequences. The savings realized are in time, both human and machine, and in
money, as more information can be extracted by laboratory techniques.
The internet enables people all around the world to quickly access and retrieve
large amounts of information. With the aid of clever algorithms, sites on the
internet are able to manage and manipulate this large volume of data. Examples
of problems that make essential use of algorithms include ûnding good
routes on which the data travels (techniques for solving such problems appear
in Chapter 22), and using a search engine to quickly ûnd pages on which particular
information resides (related techniques are in Chapters 11 and 32).
Electronic commerce enables goods and services to be negotiated and exchanged
electronically, and it depends on the privacy of personal information
such as credit card numbers, passwords, and bank statements. The core
technologies used in electronic commerce include public-key cryptography and
digital signatures (covered in Chapter 31), which are based on numerical algorithms
and number theory.
Manufacturing and other commercial enterprises often need to allocate scarce
resources in the most beneûcial way. An oil company might wish to know
where to place its wells in order to maximize its expected proût. A political
candidate might want to determine where to spend money buying campaign advertising
in order to maximize the chances of winning an election. An airline
might wish to assign crews to üights in the least expensive way possible, making
sure that each üight is covered and that government regulations regarding
crew scheduling are met. An internet service provider might wish to determine
where to place additional resources in order to serve its customers more effectively.
All of these are examples of problems that can be solved by modeling
them as linear programs, which Chapter 29 explores.
Although some of the details of these examples are beyond the scope of this
book, we do give underlying techniques that apply to these problems and problem
areas. We also show how to solve many speciûc problems, including the following:
You have a road map on which the distance between each pair of adjacent intersections
is marked, and you wish to determine the shortest route from one
intersection to another. The number of possible routes can be huge, even if you
disallow routes that cross over themselves. How can you choose which of all
possible routes is the shortest? You can start by modeling the road map (which
is itself a model of the actual roads) as a graph (which we will meet in Part VI
and Appendix B). In this graph, you wish to ûnd the shortest path from one
vertex to another. Chapter 22 shows how to solve this problem efûciently.