# 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.**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.**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.**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, 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}$.**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}]$.