Don Knuth has asked for help with Volume 4B of The Art of Computer Programming saying:
Volume 4B of The Art of Computer Programming will begin with a special section called ‘Mathematical Preliminaries Redux’, which extends the ‘Mathematical Prelimaries’ of Section 1.2 in Volume 1 to things that I didn’t know about in the 1960s. Most of this new material deals with probabilities and expectations of random events; there’s also an introduction to the theory of martingales.
You can have a sneak preview by looking at the current draft of pre-fascicle 5a (39 pages), last updated 31 August 2013. As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions. I’m particularly interested in receiving feedback about the exercises (of which there are 99) and their answers (of which there are 99).
There’s stuff in here that isn’t in Wikipedia yet!
I worked particularly hard while preparing some of those exercises, attempting to improve on expositions that I found in the literature; and in several noteworthy cases, nobody has yet pointed out any errors. It would be nice to believe that I actually got the details right in my first attempt; but that seems unlikely, because I had hundreds of chances to make mistakes. So I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out as yet.
I still cling to a belief that these details are extremely instructive, and I’m uncomfortable with the prospect of printing a hardcopy edition with so many exercises unvetted. Thus I would like to enter here a plea for some readers to tell me explicitly, “Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,” where N is one of the following exercises in prefascicle 5a:
- 24 (median of the cumulative binomial distribution)
- 28 (Hoeffding’s theory of generalized cumulative binomial distributions)
- 29 (the nearly forgotten inequality of Samuels)
- 59 (the four functions theorem)
- 61 (the FKG inequality)
- 99 (Motwani and Raghavan’s generalized bound on random loop termination time)
Remember that you don’t have to work the exercise first; you’re allowed and even encouraged to peek at the answer. Please send success reports to the usual address for bug reports (taocp@cs.stanford.edu), if you have time to provide this extra help. Thanks in advance!
Given Knuth’s contribution to the field of computer programming, if you have the time and ability, helping proof the exercises would be a small repayment for his efforts.
BTW, standards editors should take heed of Knuth’s statement in the preface to this pre-fascicle:
This material has not yet been proofread as thoroughly as the manuscripts of Volumes 1, 2, 3, and 4A were at the time of their first printings. And those carefully-checked volumes, alas, were subsequently found to contain thousands of mistakes. (The Art of Computer Programming, Volume 4 Pre-Fascicle 5, Mathematical Preliminaries Redux, page iii)
Mistakes, even in great writing (See TAOCP’s ranking along side Principia Mathematica, Theory of Games and Economic Behavior, Fractals: Form, Chance and Dimension, Cybernetics, QED, Quantum Mechanics, The Meaning of Relativity, Nature of the Chemical Bond, Search for Structure, Conservation of Orbital Symmetry, The Collected papers of Albert Einstein. Vol. 2 : The Swiss years : writings, 1900-1909 in 100 or so Books that shaped a Century of Science by Philip, Phylis Morrison) happen.
Discovery of a mistake should lead to acknowledgement of the mistake and the earliest correction possible.
Discovery of a mistake should not be met with: “everyone knows what we meant to say,” “other ‘standards’ do it that way,” or any of the other excuses for not fixing mistakes.
Mistakes are excusable as human error, failure to correct mistakes when identified, is not.
*With apologies to the Beatles, the first line of “Help!” was just too appropriate to pass up!