This book is intended to survey the most important algorithms in use on
computers today and to teach fundamental techniques to the growing number
of people who are interested in becoming serious computer users. It is appropriate
for use as a textbook for a second, third or fourth course in computer
science: after students have acquired some programming skills and familiarity
with computer systems, but before they have specialized courses in advanced
areas of computer science or computer applications. Additionally, the book
may be useful as a reference for those who already have some familiarity with
the material, since it contains a number of computer implementations of useful
algorithms.
The book consists of forty chapters which are grouped into seven major
parts: mathematical algorithms, sorting, searching, string processing, geometric
algorithms, graph algorithms and advanced topics. A major goal in the
development of this book has been to bring together the fundamental methods
from these diverse areas, in order to provide access to the best methods
that we know for solving problems by computer for as many people as possible.
The treatment of sorting, searching and string processing (which may
not be covered in other courses) is somewhat more complete than the treatment
of mathematical algorithms (which may be covered in more depth in
applied mathematics or engineering courses), or geometric and graph algorithms
(which may be covered in more depth in advanced computer science
courses). Some of the chapters involve mtroductory treatment of advanced
material. It is hoped that the descriptions here can provide students with
some understanding of the basic properties of fundamental algorithms such
as the FFT or the simplex method, while at the same time preparing them
to better appreciate the methods when they learn them in advanced courses.
The orientation of the book is towards algorithms that are likely to be
of practical use. The emphasis is on t,eaching students the tools of their
trade to the point that they can confidently implement, run and debug useful
algorithms. Full implementations of the methods discussed (in an actual
programming language) are included in the text, along with descriptions of
the operations of these programs on a consistent set of examples. Though not
emphasized, connections to theoretical computer science and the analysis of
algorithms are not ignored. When appropriate, analytic results are discussed
to illustrate why certain algorithms are preferred. When interesting, the
relationship of the practical algorithms being discussed to purely theoretical
results is described. More information of the orientation and coverage of the
material in the book may be found in the Introduction which follows.
One or two previous courses in computer science are recommended for
students to be able to appreciate the material in this book: one course in
