Selected Papers on Design of Algorithms (Volume 191)

by Donald Ervin Knuth

Donald Knuth’s influence in computer science ranges from the invention of methods for translating and defining programming languages to the creation of the TEX and METAFONT systems for desktop publishing. His award-winning textbooks have become classics that are often given credit for shaping the field; his scientific papers are widely referenced and stand as milestones of development over a wide variety of topics. The present volume, which is the seventh in a series of his collected papers, is devoted to his work on the design of new algorithms. It covers methods for numerous discrete problems such as sorting, searching, data compression, optimization, theorem-proving, and cryptography, as well as methods for controlling errors in numerical computations and for Brownian motion. Nearly thirty of Knuth’s classic papers on the subject are collected in this book, brought up to date with extensive revisions and notes on subsequent developments. Many of these algorithms have seen wide use—for example, Knuth’s algorithm for optimum search trees, the Faller-Gallagher-Knuth algorithm for adaptive Huffman coding, the Knuth-Morris-Pratt algorithm for pattern matching, the Dijkstra-Knuth algorithm for optimum expressions, and the Knuth-Bendix algorithm for deducing the consequences of axioms. Others are pedagogically important, helping students to learn how to design new algorithms for new tasks. One or two are significant historically, as they show how things were done in computing’s early days. All are found here, together with more than forty newly created illustrations.

Genres: Computer Science, Mathematics

453 pages, Paperback

First published April 15, 2010

About the author

Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.

Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.

In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.

A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.

Reviews

[Yeshu'aah · Rating 5 out of 5]

I originally picked up this book primarily due to Chapter 9, which covers what is known as the Knuth-Morris-Pratt (KMP) Algorithm, with additional interest in reading other chapters. I later read Chapter 3, which covers a Quicksort implementation for a special case. I'm currently reading the last chapter, which is more of a historical look into how data was stored (also Knuth's first published computer science paper), as well as the first chapter (also historical) and Chapter 12. Some of the chapters, such as what I see so far in Chapter 12, require a good discrete math background to fully appreciate. If you've read and understood a good portion of Vol. 1 of his TAOCP series, I think you'd have minimal difficulties with this compilation based on what I'm seeing (Full disclosure: I received a Knuth Reward Check for TAOCP.).