Chapter Table of Contents:

0. Algorithms, Programs, and CS
1. CS and its Relation to Math
2. Math and CS: Coping with Finiteness
3. Algorithms
4. Algorithms in Modern Math and CS
5. Algorithms Themes
6.-9. Theory and Practice I..IV
10. Are Toy Problems Useful?
11. Ancient Babylonian Algorithms
12. Von Neumann's First Computer Program (sorting)
13. The IBM 650: An Appreciation from the Field
14. George Forsythe and the Development of Computer Science
15. Artistic Programming

Audence:
1) Computer Science faculty and graduate students.
2) Mathematicians.
3) other scientists who want to understand their computer science colleagues.

Knuth is best known for his huge corpus
The Art of Computer Programming [TAOCP] (at this time vols. I-III)
This text (Selected Papers) really isn't for beginning programmers
(TAOCP is better for this even if more dense).
"Selected" is not a How-to book.
It's the Philosophy of the PhD on the computing field.

Math:
Yes. Selected Papers has a fair amount of algebra.
The level of math required to understand and appreciate the book:
for several of the papers, the reader needs an understanding of combinatorics:
'n!' as factorial (not exclamination point), running sums,
matrix algebra, and a bit of calculus. Other papers have practically no math (the last 3 and the opening chapter[0]).
Heavy emphasis appears on the concept of the iterative nature of Algorithms
(in contrast to other sciences which seek closed form solutions).
Can you read it w/o the math? Sure, but you would be losing major points (read it with a knowledgeable friend).

The Reading:
I really liked the paper on Toy problems. I needed this earlier in my career. Many computer scientists who like fun but get criticism will like this essay. It alone is worth the price of the book.

The easy reading introductory parts of various papers are readable withminimum math and have valuable insights (like Knuth's informal observation that 2% of the general populice feels comfortable thinking algorithmically).

The early chapters on algorithms show the importance of experimental randomization methods.

The astute review reader will notice 4 chapters (really
4 speeches) on the ideas of Theory and Practice. A lot of this material is redundant, but it conforms to the ideas of stepwise refinement and it shows some of the development of DEK's thinking. Note: he describes; he does not offer solutions.

Knuth has an obscure challenge during DEK's address to IFIP (T&P IV), slide 33. I worked toward this without knowing it.

I'll be honest with the review reader: I know the author, and
he asked me to promote this book. And it's a book well worth promoting.

The book is a pleasure to those interested in the field.
Chap 4: I sat in the audience for this presentation.
Every library should have a copy for inspection if not enough to have on every computer scientist's book shelf (next to TAOCP, and other books by Don)., and it can be a good gift book to scientists.

If this book is your first Donald Knuth's Book, the way you think about Computer Science will change. The author gives us the opportunity to think about Computer Science and Algorithms like a brillant scientist.

If you are a student you must read this book... and if you are not, I hope you already have it !

Knuth's most famous work, the "Art of Computer Programming" series, is justly famed. Bill Gates said something like "If you can read it all the way through, write me and I'll hire you". But most people can't make it through -- they're put off by the use of assembly language, or by the amount of mathematics. I have to agree that the use of assembly throughout is overkill, and I always wished there was some way to get the essence and excitement of "Art of Computer Programming" without the full tedium. Now there is.

"Selected Papers in Computer Science" succeeds beautifully in showing what its like to be a computer scientist, and how that is related to but different from being a mathematician. At the heart of the book are four essays on "Theory and Practice". Actually, it should be "Practice and Theory", because the only sensible way to progress in any field is to get some practical experience first, and then acquire the theory necessary to understand what you did, and to allow you to do more. Knuth covers this very well for computer science. I am in the habit of dog-earing pages in a book that offer an especially important insight. Looking back at my copy of "Selected Papers", I see that about 40 pages are so marked; an amazingly high ratio for a book of 270 pages. Try a test: read 10 pages from the book at random, if you don't find at least one important insight, then probably this book (and perhaps computer science in general) is not for you. If you do, you can be assured that the full book will give you many more.

This book won't teach you TeX or Metafont. It might not even teach you all that much about particular algorithms (although Chapter 3 is one of the most detailed explanations of TeX's linebreaking algorithms published anywhere). Instead, this book offers a look behind the scenes.

Instead of beholding TeX and Metafont in their almost final versions, as published in _TeX: The Program_ and _Metafont: The Program_, respectively, you see them grow from the first design studies (when Knuth thought of TeX as a program for two grad students to write over a summer) to where they are today. You see how the collaboration between Knuth and Zapf on the Euler fonts worked, and you get another glance at many facets of Knuth's mind (And a beautiful mind it is indeed, even though it is entirely sane).

If you have any deeper interest in TeX and Metafont, this book is well worth the money.

EXCELLENT book.... I cannot rate this one high enough.... at firstI thought it might have been expensive but it is NOT... the price is well WORTH it for what you get, Knuth is a master!

This is a highly stimulating collection of essays about TeX, typography, the delectable art of programming, the joy of a beautifully constructed letter A, the world, the universe and everything. Knuth's style is, as always, eminently readable and possessed of a fluidity unmatched in technical writing this century. Definitely recommended.

This boxed set is described in Knuth's own website ...

Here's the publisher's description:

"Donald E. Knuth's five volumes on Computers & Typesetting comprise the definitive user guides and thoroughly documented program code for the TeX and METAFONT systems. This open-source software is widely used around the world by scientists, mathematicians, and others to produce high-quality, aesthetically pleasing text, especially where technical content is included.
TeX and METAFONT have now reached a state of maturity that few pieces of software have ever been able to achieve. The start of the Millennium is a perfect time to offer users and libraries the opportunity to fill their reference shelves with an up-to-date and comprehensive collection of Knuth's work, as well as to encourage a broad audience of software developers to learn from the complete, robust, and portable systems built by a master programmer.

This Millennium Boxed Set---five elegantly printed books that describe their own method of creation---celebrates Knuth's monumental coupling of programming and typography. Originally published in 1986, each volume has changed so much in subsequent printings that nearly every page has been touched in some way. Improvements to the books have followed developments in digital printing technology; they also reflect corrections submitted over the years by thousands of volunteers. The volumes in this box are the latest and most accurate versions yet published.
If you have earlier printings of Knuth's books, or holes in your collection, the Millennium Boxed Set makes updating easy. If you have none of the books, you now can conveniently get them all at once. Whether your work requires that you generate superbly formatted text, or that you hone the skills needed for writing your own successful programs, you will find these volumes to be an immediately valuable resource, as well as a treasure for future generations."

Many readers are no doubt thinking, ``Why does Knuth replace MIX by another machine instead of just sticking to a high-level programming language? Hardly anybody uses assemblers these days.''

Such people are entitled to their opinions, and they need not bother reading the machine-language parts of my books. But the reasons for machine language that I gave in the preface to Volume 1, written in the early 1960s, remain valid today:

One of the principal goals of my books is to show how high-level constructions are actually implemented in machines, not simply to show how they are applied. I explain coroutine linkage, tree structures, random number generation, high-precision arithmetic, radix conversion, packing of data, combinatorial searching, recursion, etc., from the ground up.

The programs needed in my books are generally so short that their main points can be grasped easily.

People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird.

Machine language is necessary in any case, as output of many of the software programs I describe.

Expressing basic methods like algorithms for sorting and searching in machine language makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes.

Moreover, if I did use a high-level language, what language should it be? In the 1960s I would probably have chosen Algol W; in the 1970s, I would then have had to rewrite my books using Pascal; in the 1980s, I would surely have changed everything to C; in the 1990s, I would have had to switch to C++ and then probably to Java. In the 2000s, yet another language will no doubt be de rigueur. I cannot afford the time to rewrite my books as languages go in and out of fashion; languages aren't the point of my books, the point is rather what you can do in your favorite language. My books focus on timeless truths.

Therefore I will continue to use English as the high-level language in TAOCP, and I will continue to use a low-level language to indicate how machines actually compute. Readers who only want to see algorithms that are already packaged in a plug-in way, using a trendy language, should buy other people's books.

As Knuth himself says, it is impossible for any one person to keep up with all the research in computer science, but these 3 volumes do a remarkably good job of distilling the most important results and explaining them with mathematical rigor.

Each volume contains 2 chapters. Ch. 1, Basic Concepts: mathematical foundations and a description of MIX, a hypothetical machine (now available in software emulations). Ch. 2, Information Structures: lists, trees, memory allocation, garbage collection. Ch. 3, Random Numbers: how to produce series of "random" numbers and test their statistical properties. Ch. 4, Arithmetic: algorithms for integer and floating-point arithmetic. Ch. 5, Sorting: both in memory and on disks or tapes. Ch. 6, Searching: sequential, binary, hashing.

Despite the detailed coverage of the topics, which often involves esoteric mathematical notation, the author's lively style makes the algorithms and the main theoretical results relatively easy to grasp. If all you care about is getting a program to run, buy another book; but if you really want to understand how and why software works, there's nothing quite like this.

I started graduate school in the biological sciences in the late 90s. Biomedical research changed a great deal while I was getting my degree. The increased importance of computers in cutting edge research prompted me to teach myself computer science. I started with fundamentally well written books like Sedgewick's series on algorithms and K&R's C programming language and progressed to more difficult material like stroustrup's C++ programming language or CLR's intro to algorithms. However, the first time I truly felt a deep understanding of computer programming was when I read Knuth's chapter on sorting. The clarity with which he described quicksort, precisely analyzed its running time, and illustrated its behavior in a table put everything into place. Before Knuth, I was frustrated and disheartened. I didn't think it would ever make sense to me. TAOCP is what kept me at the keyboard.
A couple of years later, I've come back to these books and they continue to inspire.

To a reader interested in the analysis of algorithms, this book doubtlessly contains a number of very thorough analyses, with some interesting correspondence about the origin of complexity O()-notation and the term "NP-hard" thrown in.

As a reader more interested in Knuth's work in general, I must admit that, despite having advanced degrees in CS and a quite decent math education, I found myself unable to follow the heavy mathematics employed, and ultimately, the problems analyzed were not interesting enough to me to make me spend the effort to follow it. One of the chapters was titled "A Trivial Algorithm Whose Analysis Isn't", and this probably sums up why I'm not entirely enthusiastic about this book and about the field of algorithm analysis in general.

Knuth wouldn't be Knuth if he didn't throw some lighter material in as well, and chapter 2, "The Dangers of Computer Science Theory", was quite amusing.

Befor Donald Ervin Knuth, there was no such thing as the Analysis of Algorithms. He is a visionary in this field, and these selected papers are a testomony to his greatness in this field.

Professor Knuth collects a charming and valuable set of papers into one terrific place. Don't miss his satirical "anti- Science" article "The Dangers of Computer Science", Chapter two, first presented in 1971.

The wisdom of spending money on this might be questionable as the book could, at least in theory, be replicated from the .mf sources for Computer Modern (and be more up-to-date in the process), but the time and effort that would be expended is more than the cost of the book. For anyone who's still interested in creating fonts with Metafont, this volume is essential as a model as the most extensive use of the program.

There's a common misconception that Webs are analagous to technologies like Javadoc. The latter is effectively a fancy prettyprinter. The former is that, and more. A well-written web actually presents a program in a way that makes sense to the reader while providing a means to make that program also make sense to the computer. The idea being that you would be able to write code that looks like: for(i=0; i@; } so that you can defer exactly what processing an array element entails until a point where it makes sense. Since these redirections are handled by a preprocessor, there's no cost at run-time for doing that like there would be if the code were written with a function call.

Writing computer programs is easy, writing programs that are useful is hard and writing programs that are very useful as well as correct sometimes seems impossible. Knuth takes this truism even further and offers up the radical notion that the very best programs are so profound that people will one day read them as one would a piece of classic literature. If the idea of curling up by the fire with a copy of The World's Greatest Programs and spending the night in a state of rapture seems absurd, you think as I did. However, after reading this book, my mind now concedes the possibility does exist. After all, most of the great works of literature describe actions, conditions and solutions (algorithms) to problems of human-human and sometimes human-god interactions. Science fiction writers and readers have known for a long time that computers are very interesting objects. Buildings, paintings or other works of art are often admired not only for their subjective beauty, but also for the talent that it took to create them. Programming ability can be admired just as easily.
However, an extremely large technical barrier exists, in that programming languages are literal, terse and lack flair. Knuth works to eliminate this problem by combining the programming and documentation languages into a structure called a WEB. He also adopts the reverse paradigm that a program should be an explanation to humans of what the computer is doing. The result does wonders for readability and introduces a bit of flair. Certainly, this is a good first step towards Knuth's ideal.
The development of TEX is chronicled in great detail. It is personally comforting to read about some of the errors made in its development. Learning that the great ones make errors provides emotional security to all who hack for fun and/or profit. Some classic programming problems are used to demonstrate exactly what literate programming is meant to be. Jon Bentley, author of the 'Programming Pearls' section of "Communications of the ACM", contributes two chapters that were co-authored with Donald Knuth. These pearls demonstrate the applications of literate programming to common coding problems. All are presented in a clear, easy-to-understand style.
A bit of clever humor is also used. A WEB program is constructed from two distinct components. The Weave part explains what the program is doing, and the Tangle component produces the program. Of course, this suggests the line from Sir Walter Scott's poem Marmion, "O what a tangled web we weave, when first we practice to deceive."
I do not know whether to consider this book the product of a dreamer or a visionary. The truth, like most of the work of pioneers, is no doubt somewhere in between. My opinion is that it is more vision than dream. And is that not a common theme among the greatest works of art and literature?

Published in Mathematics and Computer Education, reprinted with permission.

Excellent analysis of control structures in the classic article "Structured Programming with goto Statements." Invents the literate programming style of program documentation. Convincingly demonstrates the literate programming style with six example programs. Includes an independent program criticism and an error log. Highly recommended.

Most of the book is about his other book, 3:16. Only near the end do we get to read what Knuth thinks about God, and here, you will be very disappointed. He trots out a few mundane ideas, like that finite numbers, while not infinite, can still be very big, and therefore adequate for describing the universe and God. Another (unoriginal) idea is that perhaps the universe is one big program similar to Conway's Game of Life (cellular automata - also now discovered/invented by Wolfram), with some randomness thrown in for free will. Finally, there is a panel discussion with a few others (Guy Steele, Manuela Veloso, Harry Lewis, Mitch Kapor). What an incoherent mess! At first, I felt sorry for these people, as they are dealing with a difficult topic, and it is hard to be coherent in real time. They all basically try to use computer science metaphors to describe religious concepts, and do a fairly poor job. That's understandable. But they are also quite annoying, as they are all a pretty self-centered bunch, constantly quoting themselves or work they've done (that doesn't advance the topic at all), and ultimately, you get the feeling they each think they ARE God, with all the "great ideas" and programs and robots they've created and imparted with their wisdom.

If you are a computer scientist, you will be disappointed. If you are a theologian, please don't think Knuth (and the others in this book) are representative of other computer scientists as far as this topic goes.

... Definitely a waste of $....

Knuth, known for his work in computer science, uses this book to talk about how religion and science don't necessarily have to go against each other. Although an easy read, it does drag at points whenever he talks about his work on the 3:16 project. Good for a weekend leisure book.

This is not a book that will revolutionize your spiritual life, but if you'd like to spend some time in the company of a very intelligent Christian, you'll enjoy this book.
I think it fair to say that Knuth is the greatest living computer scientist. He is also one of a number of prominent scientists (including Owen Gingerich and John Polkinghorne) who are willing to make their Christianity known. This tends to refute the popular perception that all scientists, or all intellectuals, are atheists. In my experience (and Knuth's experience, as evident from the audience questions in the book), a lot of atheists get their atheism blindly on authority, and whether or not you agree with him, contact with an intelligent Christian such as Knuth can be a very refreshing change!