Mathematics for the Analysis of Algorithms, Third Edition

by Daniel H. Greene and Donald E. Knuth (Boston: Birkhäuser, 1990), viii+132pp.
ISBN 0-8176-3515-7
ISBN 3-7643-3515-7
(Progress in Computer Science and Applied Logic, Volume 1.)

Russian translation of the second edition by B. B. Pokhodzei, edited by Yuri V. Matijasevich, Matematicheskie metody analiza algoritmov (Moscow: Mir, 1987), 120pp.
Japanese translation, in preparation (Kindai Kagaku Sha).

Based on class notes from a graduate course at Stanford. 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, in a format that is terse enough for easy reference yet detailed enough for those with little background. Approximately half of the book is devoted to original problems and solutions from examinations given at Stanford.

Table of Contents:

Available from the publisher, Birkhäuser Boston .

... an enjoyable read. 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. -- M. Miksa, ACM SIGACT News (June 2011)

Errata

For a list of corrections to known errors in this book, last updated 12 March 2010, you may download either the errata file in plain TeX format (1767 bytes) or the errata file in DVI format (2364 bytes) or the errata file in compressed PostScript format (18239 bytes); the latter files were generated by the TeX file.

With these corrections, the authors hope that the book is now error-free. But (sigh) it probably isn't. Therefore Knuth will gratefully deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to

Prof. D. Knuth
Computer Science Department
Gates Building 4B
Stanford University
Stanford, CA 94305-9045 USA.

He may not be able to read your message until many months have gone by, because he's working intensively on The Art of Computer Programming. However, he promises to reply in due time.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Supplementary material

We originally wanted the third edition to include the midterm and final exam given by A. C. Yao when he taught this course at Stanford in 1984. But when it came time to submit camera-ready copy in 1990 this plan had slipped our minds. The additional material, 24 pages' worth, is now available for downloading, either as a supplementary file in plain TeX format (18K bytes) or as a supplementary file in DVI format (35K bytes).

Dan Greene's home page

Don Knuth's home page

Don Knuth's other books

Analysis of Algorithms Home Page

Valid HTML 4.01 Transitional