Mathematics for the Analysis of Algorithms (Progress in Computer Science and Applied Logic (PCS)) [Hardcover]

Daniel H. Greene (Author), Donald E. Knuth (Author)

Book Description

ISBN-10: 0817635157 | ISBN-13: 978-0817635152 | Publication Date: September 1, 1990 | Edition: 3rd

This monograph collects some fundamental mathematical techniques that are required for the analysis of algorithms. It builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult notions. The authors cover recurrence relations, operator methods, and asymptotic analysis in a format that is concise enough for easy reference yet detailed enough for those with little background with the material.

Editorial Reviews

Review

“Mathematics for the Analysis of Algorithms covers a variety of topics in a relatively small amount of pages. Despite its briefness, most of the topics are clearly and fully explained using detailed examples for better understanding. As such, the book is suitable for use as study material, as well as a good reference guide…The reviewer recommends this book to anyone interested in advanced theory of algorithms and the mathematics behind it, either as an exposition to the topic or as reference material in future work.”   —SIGACT NEWS "This book collects some fundamental mathematical techniques which are required for the analysis of algorithms... This book arose from handouts for an advanced course on the analysis of algorithms at Standard University, and the appendices list lectures, homework assignments and problems for the midterm and the final exams with their solutions. In summary, this book is a very valuable collection of mathematical techniques for the analysis of algorithms and accompanies, as well as complements, the second author's series The Art of Computer Programming."   —Mathematical Reviews "The book covers the important mathematical tools used in computer science, especially in the exact analysis of algorithms. A wide range of topics are covered, from the binomial theorem to the saddle point method and Laplace's techniques for asymptotic analysis...The book is very well written. The style and the mathematical exposition make the book pleasant to read...It covers many of the major paradigms used in the analysis of algorithms in its one hundred plus pages."   —SIAM Review "The book presents a welcome selection and careful exposition of material that can be (and is) covered in a single course...In this reviewer's opinion, this would be an interesting text to use with a group of advanced students well-grounded in undergraduate mathematics and computer science, and would produce a valuable course for the participating students."   — Computing Reviews "The reader has probably heard of the expression 'good things come in small packages.' The validity of that maxim is no more in evidence than in the work under review, which is nothing less than a mathematical wellspring among the otherwise parched world of theoretical algorithm analysis. In only 76 pages (not counting the bibliography and amazing appendices), the authors cover four important topics in algorithm analysis, all from a rudimentary, but highly original, point of view: Binomial Identities, Recurrence Relations, Operator Methods, and Asymptotic Analysis. Each of these topics is critical to understanding the modern analysis of algorithms, primarily from the speed of execution perspective... In summary, the book under review should not be underestimated in its powerful use of mathematics for the analysis of algorithms arising from computer science considerations."   —Timothy Hall, Process Quality Improvement Consulting "The analysis of algorthms is possible on mathematical and on computer scientific ways. This [book] is a mathematical look at this topic. It is based on an advanced course in computer science at Stanford University... The Appendices contain further difficult problems for applying the methods of this outstanding, full-of-thoughts book."   —P.L. Erdos (Periodica Mathematica Hungarica)

From the Back Cover

A quantitative study of the efficiency of computer methods requires an in-depth understanding of both mathematics and computer science. This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult notions. The authors cover recurrence relations, operator methods, and asymptotic analysis in a format that is terse enough for easy reference yet detailed enough for those with little background. Approximately half the book is devoted to original problems and solutions from examinations given at Stanford.   "...a very valuable collection of mathematical techniques for the analysis of algorithms..."   — Mathematical Reviews "The book covers the important mathematical tools used in computer science, especially in the exact analysis of algorithms. A wide range of topics are covered, from the binomial theorem to the saddle point method and Laplace’s techniques for asymptotic analysis...The book is very well written. The style and the mathematical exposition make the book pleasant to read...It covers many of the major paradigms used in the analysis of algorithms in its one hundred plus pages."   — SIAM Review "The book presents a welcome selection and careful exposition of material that can be (and is) covered in a single course...In this reviewer’s opinion, this would be an interesting text to use with a group of advanced students well-grounded in undergraduate mathematics and computer science, and would produce a valuable course for the participating students."   — Computing Reviews

Product Details

• Hardcover: 132 pages
• Publisher: Birkhäuser Boston; 3rd edition (September 1, 1990)
• Language: English
• ISBN-10: 0817635157
• ISBN-13: 978-0817635152
• Product Dimensions: 9.2 x 6 x 0.6 inches
• Shipping Weight: 11.2 ounces
• Average Customer Review: 2.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #895,878 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

17 of 21 people found the following review helpful:

1.0 out of 5 stars The Kindle Edition is defective and should NOT be bought by anyone, August 1, 2009

By 

bluestats (Los Altos, CA) - See all my reviews

This review is from: Mathematics for the Analysis of Algorithms (Progress in Computer Science and Applied Logic (PCS)) (Kindle Edition)

I downloaded the Kindle Edition sample of this book. The text has been mangled in conversion to Topaz format in such a way as to be effectively unusable - words in sentences are dropped out, variables in formulas are missing, etc. I've noticed this with other Topaz versions of technical text. See, for example, locations 71-75 (dropped words), 75-79 (dropped variable in what appears to be a combinatorial function), locations 111-114 (who know what power x was taken to?).

I can't believe

a) Amazon continues to sell defective products like this - their QA of Kindle Editions appears to be non-existent
b) that Donald Knuth knows about this (given his work on mathematical publishing, I think he would have a cow over this disaster)

Full disclosure, I work for Adobe, so I have some skin in the game. That said Amazon really should be ashamed of themselves for this and Jeff Bezos should send another letter out. Charging $29.99 for a useless book seems tantamount to banker-like behavior. I see lots of typographical errors in Kindle Edition fiction - I'm reading "The Help" on a Kindle, and fortunately the writing is good enough to to allow these to be overlooked - but in technical literature, this sort of thing could lead to really bad mistakes. I overstate the case, but what if a civil engineer built a bridge using a formula in a Kindle Edition and the bridge later fell down?

7 of 8 people found the following review helpful:

4.0 out of 5 stars Flex your mind, December 18, 2004

By 

W Boudville (Terra, Sol 3) - See all my reviews
(VINE VOICE)    (TOP 1000 REVIEWER)    (HALL OF FAME REVIEWER)    (REAL NAME)   

This review is from: Mathematics for the Analysis of Algorithms (Progress in Computer Science and Applied Logic (PCS)) (Hardcover)

This book is a gem of problem sets AND solutions, in the field of algorithms. The problems were from actual examinations given at Stanford in various computer science classes. About half the book is good descriptive text about the ideas that the problems probe. Certainly, well written, as befits Knuth's contribution.

But I would suggest to you that the best use of the book is in tackling those problems. In the spirit of Knuth's classic Art of Computer Programming series, where he gives extensive questions and answers.

I realise my suggestion may have appeal to only some of you. But I'm addressing my remarks to the smartest amongst you glancing at this. Test and improve your understanding of algorithms.