Selected Papers on Analysis of Algorithms

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