An Introduction to the Analysis of Algorithms

Robert Sedgewick, Philippe Flajolet

Pearson Education, Feb 22, 2013 - Computers - 604 pages

Despite growing interest in the mathematical analysis of algorithms, basic information on methods and models has rarely been directly accessible to practitioners, researchers, or students. This book organizes and presents that knowledge, fully introducing today's primary techniques for mathematically analyzing algorithms.

Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematical and computer science material, integrating discrete mathematics, elementary real analysis, combinatorics, algorithms, and data structures. They focus on "average-case" or "probabilistic" analysis, while also covering tools for "worst case" or "complexity" analysis. Improvements in this edition include:

• Upgraded figures and code
• Newer style for presenting much of the text's math
• An all-new chapter on trees

This book's thorough, self-contained coverage will help readers appreciate the field's challenges, prepare them for advanced results covered in Donald Knuth's books, and provide the background they need to keep abreast of new research. Coverage includes: recurrences, generating functions, asymptotics, trees, strings, maps, sorting, tree search, string search, and hashing algorithms. Ideal for junior- or senior-level courses on mathematical analysis of algorithms, this book will also be useful in courses on discrete mathematics for computer scientists, and in introducing mathematics students to computer science principles related to algorithms and data structures.

About the author

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University, where was founding chair of the computer science department and has been a member of the faculty since 1985. He is a Director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He is the coauthor of the landmark introductory book, Algorithms, Fourth Edition. Professor Sedgewick earned his Ph.D from Stanford University under Donald E. Knuth.

The late Philippe Flajolet was a Senior Research Director at INRIA, Rocquencourt, where he created and led the ALGO research group. He is celebrated for having opened new lines of research in the analysis of algorithms; having systematized and developed powerful new methods in the field of analytic combinatorics; having solved numerous difficult, open problems; and having lectured on the analysis of algorithms all over the world. Dr. Flajolet was a member of the French Academy of Sciences.

Bibliographic information

• Title: An Introduction to the Analysis of Algorithms
• Authors: Robert Sedgewick, Philippe Flajolet
• Edition: 2, illustrated
• Publisher: Pearson Education, 2013
• ISBN: 032190575X, 9780321905758
• Length: 604 pages
• Subjects: Computers / Programming / Algorithms; Computers / Software Development & Engineering / Systems Analysis & Design