Computer Science

This book is a thorough overview of the primary techniques and models used in the mathematical analysis of algorithms. The first half of the book draws upon classical mathematical material from discrete mathematics, elementary real analysis, and combinatorics; the second half discusses properties of discrete structures and covers the analysis of a variety of classical sorting, searching, and string processing algorithms.

1. Analysis of Algorithms.

2. Recurrence Relations.

3. Generating Functions.

4. Asymptotic Approximations.

5. Trees.

6. Permutations.

7. Strings and Tries.

8. Words and Maps.

Algorithms [PTG: AW PROFESSIONAL] (Computer Science)

 

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University. He is a Director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He earned his Ph.D from Stanford University under Donald E. Knuth.

About Philippe Flajolet

Philippe Flajolet is a Senior Research Director at INRIA, has taught at Ecole Polytechnique and Princeton University, and has held visiting positions at Stanford University, the University of Chile, and the Technical University of Vienna. He is a corresponding member of the French Academy of Sciences.

020140009XAB06262002

"People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.... The appearance of this long-awaited book is therefore most welcome. Its authors are not only worldwide leaders of the field, they also are masters of exposition." --D. E. Knuth

This book provides a thorough introduction to the primary techniques used in the mathematical analysis of algorithms. The authors draw from classical mathematical material, including discrete mathematics, elementary real analysis, and combinatorics, as well as from classical computer science material, including algorithms and data structures. They focus on "average-case" or "probabilistic" analysis, although they also cover the basic mathematical tools required for "worst-case" or "complexity" analysis. Topics include recurrences, generating functions, asymptotics, trees, strings, maps, and an analysis of sorting, tree search, string search, and hashing algorithms.

Despite the large interest in the mathematical analysis of algorithms, basic information on methods and models in widespread use has not been directly accessible for work or study in the field. The authors here address this need, combining a body of material that gives the reader both an appreciation for the challenges of the field and the requisite background for keeping abreast of the new research being done to meet these challenges.

Highlights:

• Thorough, self-contained coverage for students and professionals in computer science and mathematics
• Focus on mathematical techniques of analysis
• Basic preparation for the advanced results covered in Knuth's books and the research literature
• Classical approaches and results in the analysis of algorithms

020140009XB04062001

View a Sample Chapter PDF:

  

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, contact your Pearson Higher Education representative for pricing and ordering information.

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.