If wo try to identify those contributions of computer science which will be
long lasting, surely one of these will be the refinement of the concept called
algorithm. Ever since man invented the idea of a machine which could per
form basic mathematical operations, the study of what can be computed and
how it can be done well was launched. This study, inspired by the computer,
has led to the discovery of many important algorithms and design methods.
The discipline called computer science has embraced the study of algorithms
as its own. It is the purpose of this book to organize what is known about
them in a coherent fashion so that students and practitioners can learn to
devise and analyze new algorithms for themselves.
A book which contains every algorithm ever invented would be exceed
ingly large. Traditionally, algorithms books proceeded by examining only a
small number of problem areas in depth. For each specific problem the most
efficient algorithm for its solution is usually presented and analyzed. This
approach has one major Haw. Though the student sees many fast algorithms
and may master the tools of analysis, she/he remains unconfident about how
to devise good algorithms in the first place.
The missing ingredient is a lack of emphasis on design techniques. A
knowledge of design will certainly help one to create good algorithms, yet
without the tools of analysis there is no way to determine the quality of the
result. This observation that design should be taught on a par with analysis
led us to a more promising line of approach: namely to organize this book
around some fundmental strategies of algorithm design. The number of ba
sic design strategies is reasonably small. Moreover all of the algorithms one
would typically wish to study can easily be fit into these categories; for exam
ple, mergesort and quicksort are perfect examples of the divide-and-conqucr
strategy while KruskaPs minimum spanning tree algorithm and Dijkstra's
single source shortest path algorithm are straight forward examples of the
greedy strategy. An understanding of these strategies is an essential first
step towards acquiring the skills of design.
Though we strongly feel that the emphasis on design as well as analysis
is the appropriate way to organize the study of algorithms, a cautionary
remark is in order. First, we have not included every known design principle.