PREFACE v
THE USE
OF
THE BOOK
This: book
is
intended as a first course in the design and analysis
of
algorithms.
The emphasis
is
on ideas and ease
of
un~erstanding
rather than implementa-
tion details or
progra~ming
tricks. Informal, intuitive
~xplanations
are often
used in place
of
long tedious proofs.
The
book
is
self-contained and assumes
no specific background
iri
mathematics
or
programming languages. However,
a certain amount
of
maturity in being able to handle mathematical concepts
is
desirable, as
is
some exposure to a higher-level programming language such as
FORTRAN
\or
ALGOL.
Some knowledge
of
linear
algeb~a
is
needed for a
full understanding
of
Chapters
6;
7, 8, and 12.
This book has been used
in
graduate and undergraduate c'ourses
in
algo-
rithm design. In a one-semester course most
of
Chapters 1-5 and
9-10
were
covered,
aiong with a smattering
of
topics from the remaining chapters. In
introductory courses the emphasis was on material from Chapters
1~5.
but
Se·ctions 1.6, 1.7, 4.13, 5.11, and Theorem 4.5 were generally not covered.
The book can also be used in more advanced courses emphasizing the
th~ory
of
algorithms. Chapters
6-12
could serve as the foundation for such a course.
Numerous exercises have been provided at the end
of
each chapter to
provide an instructor with a wide range
of
homework problems. The exercises
are graded according to difficulty. Exercises with no stars are suitable for
in-
troductory courses, singly starred exercises for more advanced courses, and
doubly starred exercises. for advanced graduate courses. The bibliographic
notes at the end
of
every chapter attempt to point to a published source for
each
of
the .algorithms and results contained
in
the text and the exercises.
ACKNOWLEDGMENTS
The material
in
this book has been derived from class notes for courses taught
by the authors at Cornell,
Princeton, and Stevens Institute ofTechnoiogy. The
authors would like to thank the
many people who have criticaily read various
portions
of
the manuscript and offered many helpful suggestions. In particular
we
would like to thank Kellogg Booth, Stan Brown, Steve Chen, Allen Cypher.
