An Introduction to the Analysis of Algorithms (2nd Edition)
Robert Sedgewick, Philippe Flajolet
Language: English
Pages: 593
ISBN: B00B3TB7IQ
Format: PDF / Kindle (mobi) / ePub
"[Sedgewick and Flajolet] are not only worldwide leaders of the field, they also are masters of exposition. I am sure that every serious computer scientist will find this book rewarding in many ways."
—From the Foreword by Donald E. Knuth
Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field.
Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematics and computer science, integrating discrete mathematics, elementary real analysis, combinatorics, algorithms, and data structures. They emphasize the mathematics needed to support scientific studies that can serve as the basis for predicting algorithm performance and for comparing different algorithms on the basis of performance.
Techniques covered in the first half of the book include recurrences, generating functions, asymptotics, and analytic combinatorics. Structures studied in the second half of the book include permutations, trees, strings, tries, and mappings. Numerous examples are included throughout to illustrate applications to the analysis of algorithms that are playing a critical role in the evolution of our modern computational infrastructure.
Improvements and additions in this new edition include
* Upgraded figures and code
* An all-new chapter introducing analytic combinatorics
* Simplified derivations via analytic combinatorics throughout
The book’s thorough, self-contained coverage will help readers appreciate the field’s challenges, prepare them for advanced results—covered in their monograph Analytic Combinatorics and in Donald Knuth’s The Art of Computer Programming books—and provide the background they need to keep abreast of new research.
Wavelet Transforms and Their Applications (2nd Edition)
Real Analysis: Modern Techniques and Their Applications (2nd Edition)
A Course in Number Theory and Cryptography (2nd Edition) (Graduate Texts in Mathematics, Volume 114)
Distributed Graph Algorithms for Computer Networks (Computer Communications and Networks)
. , at−1 ) of terms of the form nj β n , where β is a root of the “characteristic polynomial” q (z ) ≡ z t − x1 z t−1 − x2 z t−2 − . . . − xt and j is such that 0 ≤ j < ν if β has multiplicity ν. Proof. It is natural to look for solutions of the form an any such solution must satisfy βn = x1 β n−1 + x2β n−2 + . . . + xtβ n−t = β n. Substituting, for n ≥ t C or, equivalently, T § . β n−t q (β ) = 0. at is, β n is a solution to the recurrence for any root β of the characteristic
functions lgN and ⌊lgN ⌋ are plotted in Figure 2.3, along with the fractional part {lgN } ≡ lgN − ⌊lgN ⌋. Exercise 2.54 What is the number of comparisons used during an unsuccessful search with binary search in a table of size N in the best case? Exercise 2.55 Consider a “ternary search” algorithm, where the le is divided into thirds, two comparisons are used to determine where the key could be, and the algorithm is applied recursively. Characterize the number of comparisons used by that
deduce the rst few terms in the sequence by setting coefficients of z equal in = ( B0 + B1 z + B2 z2 + )( B3 z3 + . . . 0≤k the de nition given in Chapter 1 for use in our discussion on computational complexity. A variety of similar notations and de nitions have been proposed. A reader interested in pursuing implications may wish to read the discussion in [6] or [12]. Exercise 4.1 Show that ( ) N/(N + 1) = O 1 , 2N = o(N !), and √ e ∼ 1. N Exercise 4.2 Show that (1) N =1+O N +1 N and 1 N ∼1− . N +1 N Exercise 4.3 Show that N α = o(N β ) if α < β. Exercise 4.4 Show that, for r xed, ( ) ( ) N Nr = + O N r−1 r r! immediately from the generating functions given in the previous chapter. e rst four expansions serve as the basis for many of the asymptotic calculations that we do (actually, the rst three suffice, since the geometric expansion is a special case of the binomial expansion). For a typical example of the use of Table 4.2, consider the problem of nding an asymptotic expansion for N − as N → ∞. We do so by pulling out the leading term, writing ln( 2) ( ) ( ) ln(N − 2) = lnN + ln 1 − N2 = lnN − N2 +
