Errata list for "The Algorithm Design Manual"
---------------------------------------------
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...
---------------------------------------------------------------------------
All known errata as of November 15, 2006.
Please send additional errata/comments to skiena@cs.sunysb.edu