# 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 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 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, slide 36. negligible -> negligable.

• Lecture 5, slide 46. $\rho^n$ -> $\rho^{-n}$.

• 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. How often does equality hold, on average?" • 25. "less than M" -> "less than or equal to M" on line 8 • 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. Change initial condition in Exercise 2.17 to$A_1 = 1$. • 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. • 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. • 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. • 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. • 171. First plus should be a minus on both lines 4 and 5. • 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. • 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}$• 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. • 254.$\phi^N$->$\phi^{N+2}$in the third row. • 260. "$2$" -> "$2z$" in the denominator in the middle box in Figure 6.2 • 274. "+2" -> "-2" on line 19. • 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. • 353. longest cycle for 2134 and 1432 in Table 7.2 should be 2 and not 3. • 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. • 367.$\times$->$\star$on line -1 • 368.$\times$->$\star$on line -9 • 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) • 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 • 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

• 543. Several errors in references to Theorems for Chapter 3.

Thanks are due to the following people, who have sent errata notices: Marcello Albertini, Alex Daifotis, Micha Hofri, Sumit Kumar Jha, Carlos Roca, Stefan Vargyas, Bruce Wolk, csoroz, and especially S teve 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}$.

• 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}]$.