Summer Reading Sale
 
 

Recently Viewed clear list


Original Essays | June 20, 2014

Lauren Owen: IMG The Other Vampire



It's a wild and thundery night. Inside a ramshackle old manor house, a beautiful young girl lies asleep in bed. At the window, a figure watches... Continue »

spacer
Qualifying orders ship free.
$67.25
New Trade Paper
Ships in 1 to 3 days
Add to Wishlist
available for shipping or prepaid pickup only
Available for In-store Pickup
in 7 to 12 days
Qty Store Section
2 Remote Warehouse Software Engineering- Programming and Languages

This title in other editions

An Introduction to the Analysis of Algorithms

by

An Introduction to the Analysis of Algorithms Cover

 

Synopses & Reviews

Publisher Comments:

"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

Book News Annotation:

An introduction to the primary techniques used in the mathematical analysis of algorithms, intended as a textbook in an upper-level course on mathematical analysis of algorithms or for a course in discrete mathematics for computer scientists. Material is drawn from discrete mathematics, elementary real analysis, and combinatorics, as well as algorithms and data structures.
Annotation c. Book News, Inc., Portland, OR (booknews.com)

Synopsis:

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 combinatories, 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.

Synopsis:

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

About the Author

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

Table of Contents

1. Analysis of Algorithms.

Why Analyze an Algorithm?

Computational Complexity.

Analysis of Algorithms.

Average-Case Analysis.

Example: Analysis of Quicksort.

Asymptotic Approximations.

Distributions.

Probabilistic Algorithms.

2. Recurrence Relations.

Basic Properties.

First-Order Recurrences.

Nonlinear First-Order Recurrences.

Higher-Order Recurrences.

Methods for Solving Recurrences.

Binary Divide-and-Conquer Recurrences and Binary Numbers.

General Divide-and-Conquer Recurrences.

3. Generating Functions.

Ordinary Generating Functions.

Exponential Generating Functions.

Generating Function Solution of Recurrences.

Expanding Generating Functions.

Transformations with Generating Functions.

Functional Equations on Generating Functions.

Solving the Quicksort Median-of-Three.

Recurrence with OGFs.

Counting with Generating Functions.

The Symbolic Method.

Lagrange Inversion.

Probability Generating Functions.

Bivariate Generating Functions.

Special Functions.

4. Asymptotic Approximations.

Notation for Asymptotic Approximations.

Asymptotic Expansions.

Manipulating Asymptotic Expansions.

Asymptotic Approximations of Finite Sums.

Euler-Maclaurin Summation.

Bivariate Asymptotics.

Laplace Method.

“Normal” Examples from the Analysis of Algorithms.

“Poisson” Examples from the Analysis of Algorithms.

Generating Function Asymptotics.

5. Trees.

Binary Trees.

Trees and Forests.

Properties of Trees.

Tree Algorithms.

Binary Search Trees.

Average Path Length in Catalan Trees.

Path Length in Binary Search Trees.

Additive Parameters of Random Trees.

Height.

Summary of Average-Case Results on Properties of Trees.

Representations of Trees and Binary Trees.

Unordered Trees.

Labelled Trees.

Other Types of Trees.

6. Permutations.

Basic Properties of Permutations.

Algorithms on Permutations.

Representations of Permutations.

Enumeration Problems.

Analyzing Properties of Permutations with CGFs.

Inversions and Insertion Sorts.

Left-to-Right Minima and Selection Sort.

Cycles and In Situ Permutation.

Extremal Parameters.

7. Strings and Tries.

String Searching.

Combinatorial Properties of Bitstrings.

Regular Expressions.

Finite-State Automata and Knuth-Morris-Pratt Algorithm.

Context-Free Grammars.

Tries.

Trie Algorithms.

Combinatorial Properties of Tries.

Larger alphabets.

8. Words and Maps.

Hashing with Separate Chaining.

Basic Properties of Words.

Birthday Paradox and Coupon Collector Problem.

Occupancy Restrictions and Extremal Parameters.

Occupancy Distributions.

Open Addressing Hashing.

Maps.

Integer Factorization and Maps. 020140009XT04062001

Product Details

ISBN:
9780201400090
Editor:
Gordon, Peter
With:
Flajolet, Philippe
Editor:
Gordon, Peter
Author:
Sedgewick, Robert
Author:
Flajolet, Philippe
Publisher:
Addison-Wesley Professional
Location:
Reading, Mass. :
Subject:
Computer Science
Subject:
Programming Languages - General
Subject:
Programming - General
Subject:
Algebra - General
Subject:
Algorithms
Subject:
Computer algorithms
Subject:
Software Engineering - Programming and Languages
Copyright:
Edition Description:
Trade paper
Series Volume:
103-428
Publication Date:
November 1995
Binding:
TRADE PAPER
Grade Level:
Professional and scholarly
Language:
English
Illustrations:
Yes
Pages:
512
Dimensions:
9 x 6 x 1.4 in 658 gr

Other books you might like

  1. The Design and Analysis of Computer... Used Hardcover $54.00

Related Subjects

Computers and Internet » Computers Reference » General
Computers and Internet » Personal Computers » General
Computers and Internet » Software Engineering » Algorithms
Computers and Internet » Software Engineering » Programming and Languages
Science and Mathematics » Mathematics » Advanced

An Introduction to the Analysis of Algorithms New Trade Paper
0 stars - 0 reviews
$67.25 In Stock
Product details 512 pages Addison-Wesley Professional - English 9780201400090 Reviews:
"Synopsis" by , 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 combinatories, 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.
"Synopsis" by , 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
spacer
spacer
  • back to top
Follow us on...




Powell's City of Books is an independent bookstore in Portland, Oregon, that fills a whole city block with more than a million new, used, and out of print books. Shop those shelves — plus literally millions more books, DVDs, and gifts — here at Powells.com.