Errata list for "The Algorithm Design Manual" (FIRST EDITION) ------------------------------------------------------------- Non-trivial errata are denoted with (*) --------------------------------------- (*) page 7, line -12: move the $d = \infty$ down one line, and indent. (*) page 8, line 7: $\sqrt{(1 - e)^2 + (2 + e)^2}$ should be $\sqrt{(1 - e)^2 + (2 + 2 e)^2}$. page 8, line 15: "try all" should be "try". page 14, line 8: "there exists constants" should be "there exist constants" (*) page 14, figure 1-6 (c): The labels on the diagram are incorrect, meaning c2 and c1 should be swapped. page 14, line -1: "- 100 + 6" should be "- 100n + 6" page 16, line 3: "it likely" should be "it is likely" page 30, line -11: "can be later" should be "can later" page 31, figure 2-1: the arrowhead is missing for the left pointer (*) page 37, lines 1-4: The insertion sort algorithm is not quite correct: $i$ should go from 2 to $n$, j should be decremented within while and the > in the while-test should be < page 55, line 24: "for $i=1$ to $n$" should be "for $i=2$ to $n$" page 55, Figure 3-1: "f(6)=12" should be "f(6)=8" (*) Page 59, line 4: $s_m$ should be $s_n$. Page 60, line 18: "The last characters may be either be matched" should be "The last characters may either be matched (*) Page 64, line -2: The indices of the recurrence should run from $k=i+1$ to $j-1$ instead of $k=i$ to $j$. (*) Page 65, line 8: "for $i=1$ to $n$" should be for $i=1$ to $n-1$" (*) Page 65, line 9: "for $gap=1$ to $n-1$" should be for $gap=2$ to $n-1$" (*) Page 65, line 12: "$\min_{k=i}^j$" should be "$\min_{k=i+1}^{j-1}$" and "$T[k+1,j]$" should be "$T[k,j]$" (*) page 66, line -13: $j_i$ should be $j_k$. (*) page 66, line -13: $j_2,\ldots,j_k$ should be $j_2,\ldots,j_{m-1},j_{m+1},\ldots,j_k$ (*) page 87. line -7: "Since each triangle goes through three points," should be "By Euler's formula on the number of edges in any planar graph," (*) page 87, line -6: "three" should be "less than six" (*) page 87, line -5: "ten" should be "twenty" page 92, line -16: "DFS[G,u]" should be "DFS(G,u)". page 117, line 16: "Backtrack($a,k$)" should be "Backtrack-DFS($A,k$)" (*) page 117, line -5: $k \geq n$ should be $k = n$. (*) page 118, line 18: $k = n+1$ should be $k = n$. (*) page 118, middle: "()(2)" should be "(2)" (*) page 118, middle: "(3,2)(3,2,1)" should be "(3,2) \rightarrow (3,2,1)" (*) page 127, line 8, ">" should be "<" (*) page 127, line 9, (C(s_{i+1})-C(s_i) should be (C(s_{i})-C(s_{i+1})) (flip sign and add right parenthesis) page 134, line -7: "then it does" should be "than it does". (*) page 147, line 4: $3 \leq j \leq n-3$ should be $2 \leq j \leq n-3$ and $z_j$ should be $z_{j+1}$. (*) page 147, line 5: {v_i,n-2, z_n-1, z_n} should be {v_i,n-3, z_n-1, z_n} page 149, line 19: "NP-complete:" should be "NP-completeness proofs:" page 155, line 22: "outputs" should be "output" page 183, output figure: the edge adjacent to node 2 should be labelled "XYZ" page 195, output figure: a horizontal line is missing, on the lower left page 197, line 17: there is an indentation " programs" should be "programs" (*) page 219, line -7: "$a_n=(a_{n-24}-a_{n-55}) \mod 2^{31}$" should be "$a_n=(a_{n-55}-a_{n-24}) \mod 2^{31}$". (*) page 219, line -6: "has a period of at least $2^{55}-1$" should be "has a period length of $2^{85}-2^{30}$". (*) page 222, line 2: "for all $a$" should be "for all $a$ not divisible by $n$" (*) page 222, line 3: "1 <= a <= n" should be "1 <= a < n" page 228, line 8: "backbacker" should be "backpacker" (*) page 233, integral in first expression needs a "dt" (the t should be tau) page 235, line 6: "the total order" should be "a total order" page 236, line -17: "looking up good" should be "looking up the right" page 237, line 21: "of $n/2$" should be "of, say, $n/2$" (*) page 247, line 12: "{3,1,2}" should be "{2,1,3}" page 288, line 6: "can given" should be "can be given". page 289, line -13: "provides a" should be "provides". page 291, last bullet: should say one vertex has in-degree one more than out-degree, and the other has out-degree one more than in-degree (*) page 293, line 2: "(edges whose deletion)" should be "(edges whose deletion disconnects the graph)" page 293, line -1: "Hamiltonian cycle \seepage{matching}" should be "Hamiltonian cycle \seepage{hamiltonian-cycle}". (page 323) (*) page 294, line 14: "always no smaller than" should be "less than or equal to" (*) page 297, line -5: "edge $j$" should be "edge $ij$" in both places (*) page 297, line -3: "$c_j$" should be "$c_{ij}$" (*) page 297, line -1: both $m$'s should be $n$'s (*) page 299, etc: update home page address of Andrew Goldberg to "http://www.star-lab.com/goldberg/soft.html". page 301, last line: "close" should be "closely" page 308, line 12: "for planar" should be "for every non-trivial planar" page 315, line -1: "vica versa" should be "vice versa". (*) page 316, line 18: "the newly formed leaves" should be "all adjacent nodes" (*) page 316, line 20: "resulting tree" should be "resulting trees" (*) page 331, line -1: "chromatic number 2" should be "chromatic number 3" (*) page 334, line 4: "$O(n^2)$" should be "$O(n m \Delta)$" page 334, line 9: extra space before "a vertex" page 335-336, lines -4 to 5: reverse the roles of $G$ and $H$. (*) page 354, line -2: "$O(\lg^2)$" should this be "$O(\lg^2 n)$" page 365, line 3: delete ";" page 381, line -5: "given an" should be "give an" page 384, line -13: "Plucker" should be "Puecker". page 404, line 17: "it pays build" should be "it pays to build" page 432, line 14: "rbaeza" should be "$\sim$rbaeza", ie ~rbaeza page 444, line 13: "Paradalos" should be "Pardalos" page 469, line 22, column 1: "Plucker" should be "Puecker". All of the Errata below should have been fixed in the second printing --------------------------------------------------------------------- page 3, line -2: "to" should be "downto". (*) page 22, lines 8-9: "$k=3$, and $j=l=2$" should be "$j=k=3$, and $l=2$". page 29, line -9: "stored array" should be "sorted array". page 40, figure 2-5(b): the triangle strips do not show up well in the figure. page 42, figure 2-7: the top pointer should more obviously point to 255. page 56, line -13: "$k$ ranges" should be "$k$ or fewer ranges". (*) page 58, line 13: "for $i = 1$ to $k$" should be "for $j = 1$ to $k$" (*) page 61, figure 3-4: matrix entries (0,0)=0 and (1,0)=1 should be highlighted; matrix entry (1,1)=1 should not be highlighted. page 62, line 13: "insertion, deletion," should be "deletion, insertion," (*) page 62, lines 14-15: "Ties can" should be "Ties corresponding to legal transitions can" page 74, line -8: "only few" should be "only a few". page 76, line -6: "actally" should be "actually". page 85, figure 4-4: second node in adjacency list of V1 should be 5, not 3. (*) page 86, figure 4-5: the dual graph does not show up well in the figure. (*) page 94, lines -6 to -5: "$v$ appears before $u$" should be "$u$ appears before $v$". page 106, line 16: "Pain the neck" should be "Pain in the neck". (*) page 126, line 19: "If $(C(S) \leq C(S_i))$" should be "If $(C(S) \geq C(S_i))$" page 146, line 4: "mentioned this" should be "mentioned in this". page 147, line 15: "equivallent" should be "equivalent". page 161, challenge 6-1: "equivallent" should be "equivalent". page 193, line -10: "Schintzl" should be "Schinzel". Also page 391, lines -6 and -8, and page 394, line -9. page 196, line -10: $kd$ should not be italicized. page 210, lines 12 and 13: these lines should be flush with the others. page 211, line 21: this line should be flush with the others. page 214, line -12: "unlikely make" should be "unlikely to make". page 225, line -19: "Hopefully they are used" should be "One may hope that they are used". page 232, line -6: this line should be flush with the others. page 237, line -8: "are sorting" should be "are sorted". page 245, line 24: this line should be flush with the others. page 279, line -4: "coorespond" should be "correspond". page 280, line 16: "than the shortest" should be "then the shortest". pages 297-298, line 1: "where we" should be "We". page 319: line 12: this line should be flush with the others. page 321, line -9: "churritz@crash.cts.com" should be "churritz@cts.com" page 364, line 11: "wallets" should be "wallet". page 375, line -15: "using binary tree" should be "using a binary tree". page 404, line -1: "throughly" should be "thoroughly". page 410, line -6: "all" should be "most". page 426, line 5: "be used" should be "been used". page 428, lines 21-22: "http://www.mpi-sb.de/LEDA/leda.html" should be "http://www.mpi-sb.mpg.de/LEDA/leda.html" page 451, line -22: "Kahamer" should be "Kahaner". page 456, line -16: P{\'5}7 -> P57 bibliography: later versions of geombib are more consistant about conference nicknames like FOCS and SODA. CD-ROM Glitches for "The Algorithm Design Manual" ------------------------------------------------- Macintosh: Old versions of MacOS (7.1) get confused with CD-ROM file name suffixes (;1). However, everything works fine on MacOS 7.5.3, and presumably earlier and later OS versions. Windows NT: The Macromedia sound plugin included on the CD-ROM doesn't work on certain versions of NT. However, the latest plugin available from http://www.macromedia.com works fine. A problem came up accesing "\WEBSITE\FEEDBACK\COMMENTS\COM2.HTML" which probably should renamed because it seems to be interpreted by MS-Operating systems Dos 6.22; Win 95; Win 98, Win Me Windows NT4; Windows 2000 as a serial port. For example COM_2.HTML may be a valid filename. General: The links to figures always jump to the bottom of figures instead of the top. Remember to scroll up. Sorry... --------------------------------------------------------------------------- First edition errata closed as of July 1, 2008 because the second edition is now available.