Selected Papers on Analysis of Algorithms

by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 2000), xvi+622pp.

Here is a list of all significant changes that were made between the original printing and the printing of 2008. An asterisk (*) marks technical errors that are not merely typographical:

page ix, bottom line
change 'that that' to 'that'
page 4, line 8 of the displayed program
indent this line one more notch
page 6, line 1
change '(596)' to '(569)'
page 9, line 7 from the bottom
the first left parenthesis should be larger
page 17, line 4
change 'Intermèdiaire' to 'Intermédiaire'
page 18, line 8
change ',16' to ', 16'
page 30, line 6 from the bottom
insert $^\bullet$ after the fourth R
page 53, line 3 from the bottom
change 'manuscript (Tehran: 1972)' to 'Acta Informatica 3 (1973), 37--41.'
page 63, bottom line
change 'follows' to 'follow'
page 66, in formula (12)
change the rightmost occurrence of '$p_i$' to '$p_j$'
page 74, line 20
change 'Mathematiques' to 'Mathématiques'
*page 75, lines 7 and 8 from the bottom
change '$U_{n-1}$' to '$U_{n-2}$'
page 75, last two lines
change '(Preprint, November 1999).' to: [Electronic Journal of Combinatorics 7 (2000), #R44]. The sequence $S_n(2)$ was introduced by A. Cayley in Philosophical Magazine (4) 13 (1857), 245--248.
*page 103, line 16
change '$a_m-1$' to '$a_{m-1}$'
page 108, line 14 from the bottom
change 'approaph' to 'approach'
page 134, line 7
change '$F(a_1\ldots a_{l-1}k$' to '$F(a_1\ldots a_{l-1}k)$'
page 145, line 7 from the bottom
change 'is is' to 'is'
page 147, bottom line
change '1999' to '2000'
page 159, line 14
change '(2.2) and (3.2)' to '(2.2) and (2.3)'
page 176, line 4 from the bottom
change 'with same' to 'with the same'
page 187, line 5 from the bottom
change 'á la' to 'à la'
page 194, line 4
change '(see' to '[see'
page 205, line 3
change ' [Originally' to '[Originally'
*page 230, line 10 from the bottom
change '$1/(4pqz)$' to '$1/(4pq)$'
page 231, line 4
change 'M_p(n)' to 'M_n(p)'
page 240, line 9 from the bottom
change '$x_1+$' to '$x_1$'
*page 240, line 7 from the bottom
change '$x_1+2x_{d-1}$' to '$x_1+x_{d-2}+2x_{d-1}$'
page 243, line 14
change 'and and' to 'and'
page 263, line 6 from the bottom
change '$g_n(t,y)$' to '$g_n(t,y)\,dt$'
*page 269, equation (4.18)
change '$x^{m+n}\over m!$' to '$x^{m+n}\over(m+n)!$'
page 288, line 6
change '$1\over3$).' to '$1\over3$.)'
page 292, line 5 from the bottom
change '$2\over3$ .' to '$2\over3$.'
page 293, line 7 from the bottom
change 'on $n$ elements' to 'of $\{1,2,\ldots,n\}$'
page 294, line 8 from the bottom
change 'permutation on' to 'permutation of'
page 295, lines 13 and 14 from the bottom
change 'on' to 'of' [thrice]
page 296, line 11
change 'permutation on' to 'permutation of'
*page 307, line 1
change 'n\le N^{t+dt}' to 'n\le N'
page 319, line 8
this line should have equation number (6.13)
page 332, lines 6 and 10
change 'log' to 'ln'
page 333, line 11
the equation number '(B.3)' should be flush right
page 336, line 6
change '289]' to '289].'
page 338, line 4
change '1970' to '1968'
*page 338, several corrections to the formulas
line 9, righthand side should be $\ln\ln N+\sum{c_k\over(\ln N)^k}$.
line 10, $a_1=\gamma-1$
line 11, $a_k=(k-1)!\Bigl({\gamma_0\over0!}+\cdots+{\gamma_{k-1}\over(k-1)!} -1$
line -5 should say just 'also'
line -3 should say '$\gamma$' instead of '$3\gamma$'
*page 366, line 4 from the bottom
change '$f_n$' to '$d_n$'
page 372, line 1
change '])' to ']'
page 380, line 6
insert closing quotes after the second comma
*page 380, line 6 from the bottom
change '$o(1)$' to '$o(n^{1/2})$'
page 381, lines 8 and 9
change '$=$' to '$\sim$'
page 382, line 5 from the bottom
the first left parenthesis should be larger
*page 382, line 5 from the bottom
change '(-1)' to '(1)'
page 383, bottom line
change '$=$' to '$\sim$'
page 384, lines 5 and 6 from the bottom
change 'know the asymptotic value' to 'know the value'
page 388, line 4 from the bottom
change '$=$' to '$\sim$'
*page 399, line 10 from the bottom
change '$A(a,1,0)$' to '$A(a,1)$'
*page 402, line 6 from the bottom
change '$C(z)^k$' to '$C(z)^n$
*page 403, line 4
change '$x\ge y$' to '$x\le y$'
*page 410, replacement for lines 15 and 16
else if $x_1>x_2+1=x_3+2$ then max$(x_3,x_j)$
else $g_{j-1}(x_2,\ldots,x_j)$
[Also delete the footnote on this page.]
*page 411, lines 6 and 7
change '$g_{a+1}$' to '$f$' [twice]
page 411, line 6 from the bottom
change 'twice' to 'thrice' [once]
page 414, lines 16 and 17
change 'to appear.]' to '283--300].'
page 414, line 23
change 'a paper in preparation.' to 'in Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics (Kluwer, 2001), 231--242.'
*page 414, replacement for the final paragraph
The author's original formulation of Theorem 4 was incorrect, but a correct definition of the function $g_j(x_1,\ldots,x_j)$ was found in May 2000 by Thomas A. Bailey as he was working with John R. Cowles on Open Problem 4. As of June 2000, ACL2 has verified the corrected version of Theorem 4 when $2\le m\le 7$.
page 466, line 3 from the bottom
change ', to appear, apply' to '47 (2000), 905--911, have applied'
page 469, line 9
change 'p_{nk}z^k' to 'p_{nk}z^n'
page 478, line 15
change ').' to ')'
page 500, last three lines
change 'But the optimum procedure for sorting 13, 14,' to 'Marcin Peczarski [ESA 2002, to appear] extended Wells's method to prove that merge is actually unbeatable when $n=13$. But the optimum procedure for sorting 14,'
page 502, line 2
change 'of of' to 'of'
page 503, line 7 from the bottom
change 'Intermèdiaire' to 'Intermédiaire'
page 504, new copy to follow the references
Addendum Strictly speaking, an addition chain should specify the sets of integers $\{j(i,q) \mid 1\le q\le r(i)\}$ as well as the sequence of vectors $C$, because the latter does not uniquely define the former.
page 519, lines 4, 5, 6, 7, 8
the asterisks should be the typewriter font, as on line 1
page 523, line 18
change 'difficlut' to 'difficult'
page 532, line 9
change 'whose is' to 'whose bandwidth is'
page 532, lines 11 and 12
change ' (Extended abstract),...90--99' to ', Journal of Computer and System Sciences 60 (2000), 510--539'
page 535, line 9 from the bottom
change 'the the' to 'the'
page 543, line 12
change 'is traditionally known as' to 'was in fact defined and named by J. L. Carter in his Ph.D. dissertation, On the Existence of a Projective Plane of Order Ten (Berkeley, California: Mathematics Department, University of California, 1974). It is also known as the problem of'
page 551, line 13
change '$(.11001\ldots{})$' to '$(.11001\ldots{})_2$'
*page 556, line 13 from the bottom
change 'transcendental' to 'irrational'
*page 557, line 3 from the bottom
change '$\mu\ge0$' to '$\mu>m$'
*page 557, line 2 from the bottom
change '$\sum_{m=0}^\mu$' to '$\sum_{m=0}^{\mu-1}$'
*page 581, line 9 from the bottom
change '$F_{j+1}$' to '${1\over2}F_{j+1}$'
*page 582, line 21
change '(5.24)' to '(5.25)'
page 602, line 5
change '1286-1291' to '1286--1291'
*page 603, new paragraph to follow line 8
Conversely, if $F(x)$ is a polynomial distribution with rational coefficients for which $F'(x)$ has no irrational roots, Guy Kindler and Dan Romik have shown that $F(x)$ can be generated by an fsg; this completes the solution of problem (v). [``On distributions computable by random walks on graphs,'' SIAM Journal on Discrete Mathematics 17 (2004), 624--633.]
page 605, first entry in left column
change '37' to '37.'
page 607, Cantor entry in the left column
change 'Philip' to 'Philipp'
page 607, new entry
Carter, John Lawrence, 543.
page 608, right column
change 'Dellac, H.' to 'Dellac, Hippolyte'
page 609, left column
change 'Dirichlet, Peter' to 'Dirichlet, Johann Peter'
page 610, entry for free trees
change '531--532, 533' to '531--533'
page 610, entry for Gauss
change 'Gau8' to 'Gauß' and 'Johann Friedrich' to 'Johann Friderich'
page 612, new entry
Kindler, Guy, 603.
page 613, entry for LISP
add page 116
page 616, new entry
Peczarski, Marcin Piotr, 500.
page 617, new entry
Romik, Dan, 603.
page 618, left column
Rustin, Randall Dennis, 53.
page 620, entry for trees, free
change '531--532, 533' to '531--533'
page 621, entry for Vinogradov
change the Russian spelling from 'Vinogradob' to 'Vinogradov'
page 621, entry for Wrench
change '191--192, 193' to '191--193'

Selected Papers on Analysis of Algorithms home page

Don Knuth's home page

Don Knuth's other books

Valid HTML 4.01 Transitional