AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS Second Edition

THIS book is intended to be a thorough overview of the primary techniques
used in the mathematical analysis of algorithms. 􀄻e material
covered draws from classical mathematical topics, including discrete mathematics,
elementary real analysis, and combinatorics, as well as from classical
computer science topics, including algorithms and data structures. 􀄻e focus
is on “average-case” or “probabilistic” analysis, though the basic mathematical
tools required for “worst-case” or “complexity” analysis are covered as well.
We assume that the reader has some familiarity with basic concepts in
both computer science and real analysis. In a nutshell, the reader should be
able to both write programs and prove theorems. Otherwise, the book is
intended to be self-contained.
􀄻e book is meant to be used as a textbook in an upper-level course on
analysis of algorithms. It can also be used in a course in discrete mathematics
for computer scientists, since it covers basic techniques in discrete mathematics
as well as combinatorics and basic properties of important discrete structures
within a familiar context for computer science students. It is traditional
to have somewhat broader coverage in such courses, but many instructors may
􀅀nd the approach here to be a useful way to engage students in a substantial
portion of the material. 􀄻e book also can be used to introduce students in
mathematics and applied mathematics to principles from computer science
related to algorithms and data structures.
Despite the large amount of literature on the mathematical analysis of
algorithms, basic information on methods and models in widespread use has
not been directly accessible to students and researchers in the 􀅀eld. 􀄻is book
aims to address this situation, bringing together a body of material intended
to provide readers with both an appreciation for the challenges of the 􀅀eld and
the background needed to learn the advanced tools being developed to meet
these challenges. Supplemented by papers from the literature, the book can
serve as the basis for an introductory graduate course on the analysis of algorithms,
or as a reference or basis for self-study by researchers in mathematics
or computer science who want access to the literature in this 􀅀eld.