Errata

Report errata.

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

Errata list for the Lecture slides

Lecture 1, slide 29. $\infty$ -> $N$ on line -2
Lecture 1, slide 33. Should be $${a (10 N) \ln (10 N)\over a N\ln N} = 10\Bigl(1 + {\ln 10\over\ln N}\Bigr) = 10\Bigl( 1 + {1\over\log_{10}N}\Bigr)$$ and therefore 4 x 12 = 48 seconds for N = 1M and 48 x (70/6) x (80/7) x (90/8) = 20 hours for N = 1B.
Lecture 2, slide 15. Should be $2(H_{n+1}-1)$ just to the left of the telescope.
Lecture 2, slide 29. Need $a_0$ in telescoped result, so solution should be $B_N = \lg N + 1$.
Lecture 2, slides 31, 32, 33, 35, and 38. Initial condition for Mergesort recurrence should be $C_1 = 0$.
Lecture 2, slide 42. < and > should be switched in the Master Theorem.
Lecture 3, slide 13. Four "-" signs missing under "Do some math"
Lecture 3, slide 20. Polynomial should be $z^t-x_1z^{t-1}-+x_2z^{t-2}-\ldots-x_tz^{0}.$
Lecture 3, slide 34. Missing summation sign before the binomial coefficient on line 3 (sum on $k$ from 0 to $n$).
Lecture 4, slide 6. decreasing series -> decreasing sequence.
Lecture 4, slides 7-8. $g(0)=0$ -> $g(0)\ne0$.
Lecture 4, slide 36. negligible -> negligable.
Lecture 5, slide 17. Add "3" to the Fibonacci sequence at the bottom
Lecture 5, slide 46. $\rho^n$ -> $\rho^{-n}$.
Lecture 6, slides 36 and 37. Term corresponding to the empty tree should be 0 (no "1 + " in lines -1 and -4 on slide 36 and line 2 on slide 37).
Lecture 6, slide 27. $2k-2\choose k$ -> $2k-2\choose k-1$.
Lecture 8, slides 8 and 18. $\beta_k$ is the dominant root of $1-2z+z^k$ -> $1/\beta_k$ is the smallest root of $1-2z+z^k$ .

Errata list for the book

6. "below" -> "below (by a strictly positive number)" in line -3
8. "mergesort(0, N-1)" -> "mergesort(a, 0, N-1)" in last line of text
9. Switch floors and ceilings in proof of Theorem 1.1
10. "operations used" -> "operations used by" on line 11
11. "can be divided by 2 before reaching an number less than" -> "needs to be divided by 2 in order to reach a number equal to or less than" on line -15
21. Second line of Theorem 1.3 should read "$N$ partitioning stages"
21. Adjust LHS of Theorem 1.3 equations to reflect following two changes
22. Only $N$ compares when partitioning element is smallest, so change average parititioning cost to $N+1-1/N$ in equation (3)
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
23. Exercise 1.13."j:=r+1" -> "j:=hi+1"
23. Exercise 1.14. Add "with $A_0=0. This is the number of times quicksort is called with hi$\ge$lo."
24. $-.601 N$ -> $+ .601 N$ on line 11
25. "less than M" -> "less than or equal to M" on line 8
25. "2 or less" -> "$k>0$" in Exercise 1.16
25. Exercise 1.17. Line of code should be "if hi-lo+1<=M then insertionsort(lo,hi) else"
25. "M = 0" -> "M = 1" in Exercise 1.19
51. "-1" -> "-3/2" on line 2.
51. Change initial condition in Exercise 2.17 to $A_1 = 1$.
51. [25] -> [24] in exercise 2.17.
52. Remove extra closing paren in line -8
56. Last sentence in proof of Theorem 2.2 is unsupported.
65. Repertoire example is bad; needs to be replaced.
66. 1.4 -> 1.3 on line -10
66. Initial conditions do not match Theorem 1.3.
67. "increasing" -> "increasing for $n>2$" on line after first displayed equation.
81. $\alpha a(x/\beta^2)$ -> $\alpha^2 a(x/\beta^2)$ on line -6.
81. $\alpha a(x/\beta^3)$ -> $\alpha^3 a(x/\beta^3)$ on line -5.
84. Switch < and > conditions on $\gamma$, in the displayed equations at the top and at the bottom.
94. Partial sum entry. $a_1$, $a_1+a_2$ -> $a_0$, $a_0+a_1$
100. Index divide entry. $n\ge 1$ -> $n\ge 0$
101. Index multiply entry. $3a$ -> $3a_2$
103. 3.4 -> 3.1 on line -4.
107. mod $z^4$ -> mod $z^3$ on line 7.
108. $n>4$ -> $n>3$ in exercise 3.18.
115. $B(-z)=e^zA(z)$ -> $A(z)=e^zB(-z)$ on line -8.
115. $A(-z)=e^zB(z)$ -> $B(z)=e^zA(-z)$ on line -7.
116. $k^n\over n!$ -> $k^n\over k!$ in exercise 3.38.
117. Reference on line -9 should be to 3.8, not 3.3.
123. five or fewer nodes -> five or fewer external nodes on line -12.
126. external -> internal on line 7.
127. RHS on last line is missing $\sum_k$.
130. ${1\over 6}$ -> ${1\over 3}$ on line -6.
133. $A(z,u)$ -> $P(z,u)$ on line 7.
135. $P(1,z)$ -> $P(z,1)$ on lines -1 and -6.
136. $P(1,z)$ -> $P(z,1)$ on line -5.
137. $P(1,z)$ -> $P(z,1)$ (twice).
139. ${1\over(1-z)^2}\ln{1\over 1-z}$ -> ${2\over(1-z)^2}\ln{1\over 1-z}$ on line 12.
139. ${8\over(1-z)^3}\ln^2{1\over 1-z}$ -> ${8\over(1-z)^4}\ln^2{1\over 1-z}$ on line 14.
139. ${-6\over(1-z)^2}$ -> ${8\over(1-z)^2}$ on line 15.
159. $n>4$ -> $n>3$ in exercise 4.15.
164. Last three digits in center column in Table 4.3 should be 624, 669 (no change), 149, 828, 456, 691, 177, 025, 302, and 704.
164. In Table 4.3, absolute error for $N=10$ should be 9.70.
166. In the third row in Table 4.5, the last four digits in the second column should be 4554 and the last four digits in the third column should be 4582.
166. "error" -> "absolute error" in Table 4.5.
166. In Table 4.5, the entries in the last column should be $10^{-6}$ (no change), $10^{-9}$, $10^{-12}$, and $10^{-15}$.
168. Table entry for binomial coefficients (second line) should be
$${N\choose k}={2^N\over\sqrt{\pi N/2}}\Bigl(1+O({1\over N})\Bigr)\quad\hbox{for }k={N\over2}+O(1)$$.
171. First plus should be a minus on both lines 4 and 5.
182. Last term should be $O(1/N^3)$ in Exercise 4.54.
188. ${1\over N}$ -> ${k-1\over N}$ at the ends of lines 9 and 10.
192. "(N-k)!" -> "(N+k)!" on line 3.
206. Second line for P(N). $1\le k \le N$ -> $0\le k < N$ and $1\le j < k$ -> $0\le j < k$.
207. Exercise 4.71. $k\ge 0$ -> $0\le k < N$
227. $1\le N\le 4$ -> $1\le N\le 5$ in figure caption.
244. Third line from the bottom should read $u^1 +u^1 + u^2 + u^1 + u^1 + u^2 + u^2 + u^2 + u^2 + u^1 + u^1 + u^2 + u^1 + u^1$
239. $D_N=$ -> $D_N/N!=$ on line 11.
247. $g'(\beta)$ -> $g'(1/\beta)$ on line -4.
247. "the root $1/\beta$ of $g(z)$ of largest modulus" -> "of smallest modulus" on line -6.
250. In the Corollary, replace $\rho^n$ by $\rho^{-n}$
248. Denominator for Catalan GF in the middle of the page should be $2z$.
250. Proof of the Corollary should read "Change variables from $z$ to $z/\rho$ in Theorem 5.5"
251. Specify $T^{\Box}(z)$ (external nodes) on line 10.
252. $1/\sqrt{\pi N/2}$ -> $\sim 1/\sqrt{\pi N/2}$ in Exercise 5.23.
254. $\phi^N$ -> $\phi^{N+2}$ in the third row.
260. "$2$" -> "$2z$" in the denominator in the middle box in Figure 6.2
271. Figure does not illustrate correspondences, just enumerates all possibilities.
274. "+2" -> "-2" on line 19
299. "3.11" -> "3.8" on line -1
300. "3.10" -> "5.4" on line -7 (see page 245)
283. "private Node insert(Key key)" -> "private Node insert(Node x, Key key)" in Program 6.3.
335. First sentence should read "The corollary to Theorem 5.5 (page 250) provides an immediate proof that $ [z^n]M(z) \sim 3^n /\sqrt{4\pi n^3/3}$."
335. 4.12 -> 5.5 on line 15.
341. $U(z)^2$ -> $U(z^2)$ in GF equation for unordered trees.
352. Entry for index 9 in table after line 2 should be 14 and not 8.
352. Entry for index 1 in table after line 2 should be 18 and not 9.
352. 188 -> 203 just before Exercise 7.5.
353. longest cycle for 2134 and 1432 in Table 7.2 should be 2 and not 3.
353. Cycles entry in Table 7.2 for 2134 should be 3.
353. Inverse entry in Table 7.2 for 4213 should be 3241.
353. Subseqs entry in Table 7.2 for 1243 should be 12, for 1324 should be 12, for 2143 should be 9, for 3124 should be 10, and for 4132 should be 7.
353. Inversion table entry in Table 7.2 for 2413 should be 0021, for 3124 should be 0110, for 3142 should be 0102, for 3241 should be 0103, and for 4213 should be 0121.
354. "rises" row in Table 7.3 should be 1, 6, 36, 240, 1800, and 15,120.
359. "decreasing" -> "increasing" and "smallest" -> "largest" in Exercise 7.7
359. $q_i$ -> $q_i+1$ on line 14
359. eighth->ninth and sixth->seventh in the example below the table
360. "right to left" -> "left to right" on line 4.
365. add another factor of 2 before the 3 at the end in the denominator on line 2.
367. $\times$ -> $\star$ on line -1.
368. $P_{>0}(z)$ -> $P_{>1}(z)$ on line 8.
368. $\times$ -> $\star$ on line -9.
369. "greater than" -> "greater than or equal to" on line -3.
369. Include the empty involution on the right hand side on line -1.
372. Include the empty permutation in the equation in the middle of the page.
378. add condition "and $A_{Nk}=0$" on line 8.
378. $z^n u^k$ -> $z^N u^k/N!$ on line 10.
378. The partial derivative on the left is not defined at $u=1$, so replace by the limit as $u\to 1$ and apply l'Hôpital's rule twice to get $$[z^N] {z\over(1-z)^2} - {z^2\over 2(1-z)^2},$$ which yields $(N+1)/2$ for $N\ge 1$ and correctly gives 0 for N=0
379. "Dividing by $N!$" -> "Multiplying by $z^N/N!$" on line -7
379. $(1-z)$ -> $(1-z)^2$ on line -6.
382. $N+1$ -> $N-2$ in both cases on line 4.
382. In line 4 of the proof, the claim that a fall is either a valley or a double fall does not apply to the (possible) fall at the end of the permutation.
386. "standard deviation" -> "variance" on line 5.
404. The variance $1/k$ in Theorem 7.13 only applies for $N\ge 2k$
406. Bubble sort description in lines 12-16 does not match Program 7.6
417. Program 8.1 does not implement the sentinel method described on lines 1-4
418. Table 8.1 does not incorporate the additional 1
423. $S_P$ -> $B_P$ (twice) on line 11.
423. "null or consisting" -> "a string" on line 7
423. $S_P$ -> $B_P$ (twice) on line 11
423. $1+z^P$ -> $1-z^P$ on line 12
425. $M$->$P$ on line 11
426. $2^M$ -> $2^P$
439. $i-1$ -> $i$ on line 12
439. delete “, but the ith character does not match” on line 13.
459. "Theorem 4.9" -> "the Corollary of Theorem 4.10" on line -1
467. Omit reference [28] on line -11 (not a book)
475. "insert()" -> "insert(key)" in Program 9.1
485. "3-word 2 1" -> "2-word 2 1" on line -10
487. the "it is more likely that" interpretation is not valid, as this is the expected value, not thresholding at 0.5 as per the median
491. Displayed formula in Ex. 9.8 should be $$\sum_{0\le j < M}{M-1\choose j}(-1)^j\bigl(1-{j+1\over M}\bigr)^{N-1}$$.
497. $k=1$ -> $k=0$ on line -6
504. $[z^N] 1/M^2$ -> $[z^N] 2/M^2$ on line 7
508. summation in proof should be $0\le k< N$ since these indices are implicit in deriving the successful search result in Thm 9.7
508. $(N+1)/2M$ -> $(N-1)/2M$ on line 3 and in proof
510. "hash function does not return zero" -> "hash table does not store zeroes" on line 5
511. "successful and unsuccessful" -> "unsuccessful and successful" in Theorem 9.7
512. "25" -> "24" on line -2.
512. Delete the last sentence of the paragraph on lines -14 to -12 (repeats the last paragraph of proof of Theorem 9.7)
513. "key takes j+1 steps" -> "key can take more than j steps" on line 10
514. $N-k-i$ -> $N-k-1$ on line -6.
515. Remove "This is to be expected..." sentence starting on line 5 since the inline equation is only correct with "[1]" -> "[0]"
515. Replace $i$ by $(i+1)$ after the summation sign on lines 9 and 14 <--!
516. Corollary is missing the extra factor ½ in Thm 9.8 -->
516. $e^M$ -> $e^z$ on line -13
517. entries for exact and asymptotic costs for separate chaining in the table do not match results of Theoremm 9.6
528. Asymptotic result for cycles of trees in Table 9.11 does not match formula at top of p. 529: should be $N^N \sqrt{\pi/2N}$ (to match claim on p.529, line 6)
529. coefficient of $1/N^N$ missing on line -6, and the summation condition should be $
531. Replace $C(z)$ by $Y(z)=ln 1/(1-C(z)) $ on lines 4-5
534. Update of b in while loop missing parentheses in Program 9.4

Typos.

31. Figure 1.3 label needs to move down and to the left.
42. "and exact" -> "an exact" on line 5.
43. Ref. "[14], [15], [16]" -> "[13], [14], [15]" on line -8.
49. Ref. [14] -> [13] and [23]->[22] on line 9.
50. Ref. [18] -> [17] and [24]->[23] on line 8.
60. Ref. [14] -> [13] on line -10.
66. Ref. [20] -> [19] on line 5; [18] -> [17] and [24] -> [23] on line -3; 1.4 -> 1.3 on line -10.
79. Ref. [19] -> [18] on line 13; [9] -> [8] on line 17;
181. "3.86 and 3.87" -> "3.73 and 3.74" on line 2.
185. "M" -> "m" on line 4.
219. "an general" -> "a general" on line 7.
224. "defined" -> "define" on line 5.
224. "5.3" -> "5.5" on line -6.
224. "5.4" -> "5.6" on line -5.
228. Bad opening quote on superleaf in Ex. 5.4
231. "5.5" -> "5.6" on line -5.
234. "5.6" -> "5.7" on line -7.
235. "5.7" -> "5.8" on line -1.
244. Missing * superscripts for $P$ and $P_u$ in first three equations.
245. "3.6" -> "3.5" on line -5.
246. "consider consider" -> "consider" on line -3.
248. "weaker" -> "a weaker" on line 17.
252. "ease with" -> "ease with which" on line 8.
267. "." -> "," on line 9.
267. "to to list" -> "to listing" on line 11.
289. "3.11" -> "3.8" on line -6.
289. "3.11" -> "3.8" on line -2.
292. "3.11" -> "3.8" on line -2.
294. "1.2" -> "1.3" on line -14.
294. "3.12" -> "3.9" on line -13.
296. $2H_N - 3 - 2H_N/N$ -> $2H_N - 4 + 2H_N/N$ on line 15.
296. "6.3" -> "6.4" on line 15.
299. "OGF" -> "is the OGF" on line 7.
299. Missing subscript Bs on line 12.
299. "3.11" -> "3.8" on line -1.
300. "3.10" -> "5.4" on line -7.
303. "3.11" -> "3.8" on line -13.
313. "tp" -> "to" on line 5.
378. Proof of Thm 7.5 missing an end-of-proof marker
378. "3.6" -> "3.5" on line -12
382. "5.7" -> "6.7" on line 9.
382. "6.15" -> "7.15" on line 10.
397. 7.12 -> 7.11 on line -13
402. “in p. from” -> “in p, from” on line -10
404. 3.6 -> 3.8 on line -4
421. 3.11 -> 3.8 on line 9
421. "3.9" -> "3.10" on line 6
424. "4.18" -> "4.17" on line -2
431. "8.3" -> "8.2" on lines -9 and -14
461. "8.7" -> "8.8" on line 6
470. "[28]" -> "[26]" on line 16
484. "given" -> "given in" on line 16
490. "3.10" -> "3.7" on line -7
490. "3.7"-> "3.6" on line -3
492. "3.7" -> "3.6" on line 13
501. "4.6" -> "4.9" on line 9
504. "3.6" -> "3.5" on line 4
505. "9.4 and 9.5" -> "9.5 and 9.6" on line 9 and throughout the re\ st of the paragraph
508. "asuccessful" -> "a successful" on line 3
509. "9.6" -> "9.7" on line 2
510. "9.7" -> "9.8" on line -2
512. "25" -> "24" on line -2.
514. "3.66" -> "9.38" on line -4
528. "followng" -> "following" on lines 8-9
531. "9.13" -> "9.12" on line 9
533. "9.9" -> "9.10" on line 1
537. "22" -> "21" on line -1
543. Several errors in references to Theorems for Chapter 3.

Thanks are due to the following people, who have sent errata notices: Marcelo Albertini, Alex Daifotis, Evangelos Georgiadis, Micha Hofri, Sumit Kumar Jha, Carlos Roca, Stefan Vargyas, Bruce Wolk, csoroz, and especially Steve Kroon, who has provided most of the entries on these lists.

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.

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