Errata

Report errata.

If you discover an error or typo, please fill out this errata submission form. Your feedback is much appreciated.

Errata.

p. 21. Second line of Theorem 1.3 should read "$N$ partitioning stages"
p. 22. Last four constraints on $N$ are off by 1: $N>0$, $N>1$, $N>1$, $N>1$ should be $N>1$, $N>2$, $N>2$, $N>2$, respectively.
p. 23. Exercise 1.13."j:=r+1" -> "j:=hi+1"
p. 23. Exercise 1.14. Add "with $A_0=0. This is the number of times quicksort is called with hi$\ge$lo. How often does equality hold, on average?"
p. 25. Exercise 1.17. Line of code should be "if hi-lo<=M then insertionsort(lo,hi) else"
p. 65. Repertoire example is bad; needs to be replaced.
p. 81. $\alpha a(x/\beta^2)$ -> $\alpha^2 a(x/\beta^2)$ on line -6.
p. 84. Switch < and > conditions on $\gamma$, in the displayed equations at the top and at the bottom.
p. 94. Partial sum entry. $a_1$, $a_1+a_2$ -> $a_0$, $a_0+a_1$
p. 100. Index divide entry. $n\ge 1$ -> $n\ge 0$
p. 103. 3.4 -> 3.1 on line -4.
p. 107. mod $z^4$ -> mod $z^3$ on line 7.
p. 130. ${1\over 6}$ -> ${1\over 3}$ on line -6.
p. 135. $P(1,z)$ -> $P(z,1)$ on lines -1 and -6.
p. 136. $P(1,z)$ -> $P(z,1)$ on line -5.
p. 137. $P(1,z)$ -> $P(z,1)$ (twice).
p. 171. First plus should be a minus on both lines 4 and 5.
p. 188. ${1\over N}$ -> ${k-1\over N}$ at the ends of lines 9 and 10.
p. 192. "(N-k)!" -> "(N+k)!" on line 3.
p. 206. Second line for P(N). $1\le k \le N$ -> $0\le k < N$ and $1\le j < k$ -> $0\le j < k$.
p. 207. Exercise 4.71. $k\ge 0$ -> $0\le k\le N$
p. 239. $D_N=$ -> $D_N/N!=$ on line 11.
p. 245. "T(1,z)" -> "T(z,1)" on line -8.
p. 247. $g'(\beta)$ -> $g'(1/\beta)$ on line -4.
p. 247. "the root $1/\beta$ of $g(z)$ of largest modulus" -> "of smallest modulus" on line -6.
p. 250. In the Corollary, replace $\rho^n$ by $\rho^{-n}$
p. 250. Proof of the Corollary should read "Change variables from $z$ to $z/\rho$ in Theorem 5.5"
p. 260. "$2$" -> "$2z$" in the denominator in the middle box in Figure 6.2
p. 274. "+2" -> "-2" on line 19.
p. 354. "rises" row in Table 7.3 should be 1, 6, 36, 240, 1800, and 15,120.
p. 360. "right to left" -> "left to right" on line 4.
p. 423. $S_P$ -> $B_P$ (twice) on line 11.

Typos.

p. 31. Figure 1.3 label needs to move down and to the left.
p. 42. "and exact" -> "an exact" on line 5.
p. 49. Ref. [14] -> [13] and [23]->[22] on line 9.
p. 50. Ref. [18] -> [17] and [24]->[23] on line 8.
p. 60. Ref. [14] -> [13] on line -10.
p. 66. Ref. [20] -> [19] on line 5; [18] -> [17] and [24] -> [23] on line -3; 1.4 -> 1.3 on line -10.
p. 79. Ref. [19] -> [18] on line 13; [9] -> [8] on line 17;
p. 181. "3.86 and 3.87" -> "3.73 and 3.74" on line 2.
p. 185. "M" -> "m" on line 4.
p. 231. "5.5" -> "5.6" on line -5.
p. 234. "5.6" -> "5.7" on line -7.
p. 235. "5.7" -> "5.8" on line -1.
p. 313. "tp" -> "to" on line 5.
p. 382. "5.7" -> "6.7" on line 9.
p. 382. "6.15" -> "7.15" on line 10.
p. 543. Several errors in Theorems for Chapter 3.

Thanks are due to the following people, who have sent errata notices: Micha Hofri, Alex Daifotis, Bruce Wolk, csoroz,

Errata in the first edition (no longer being updated)

The list below supplements this list from July 2006. For brevity, spelling and grammatical errors are supressed.

p. 50. Equation on line -9 should read $a_n = 2a_{n-1}+a_{n-2}-2a_{n-3}$.
p. 59. In line 1 "-2"-> "+2" and in line 2 "2" -> "-2".
p. 64. Ref. to Program 2.1 should be 2.2; also need different implementation or description about 3-way compare.
p. 66. $D_1$ is $2$, not 0.
p. 76. Switch $\alpha$ and $\beta$ in the statement of Theorem 2.6.
p. 89. $zA(z)$ is the EGF for $0, a_0, 2a_1, 3a_2,\ldots$.
p. 96. Partial fraction decomposition in next-to-last line should be $1+z$, not $1-z$.
p. 141. In exercise 3.38, $n!$ in sum should be k!
p. 161. In line -6, ref to 3.10 should be 3.11.
p. 167. In last column of table header, $+$ should be $-$.
p. 194. In line 13, $2^{5000}$ should be $2^{10000}$.
p. 205. In line 4, need minus sign in exponent.
p. 271. First triangulation appears twice more. Missing cases are the rotation of that one and three rays emanating from left vertex.
p. 283. In Program 6.3, "insert" is missing its first parameter, "Node x"
p. 289. $n$ should be $N$ (twice) in last displayed formula, and $1/N$ should precede $[u^{n-1}]$.