Errata

I'm very backlogged on these.
Please be patient for a reply. Thanks!

All errors

  DATE   PAGE  WHO  PROBLEM
--------  ---  ---  ----------------------------------------------------------
06/21/06  xvii EEO  The last word inthe third line should be "Chapter", not "Chap-ter"
02/24/10  017  TM   In Section 1.5.2, line 2, change "add" to "write".
09/26/06  024  BLS  Line 9 in Figure 1.18 should by cmp.compare not cmp.compareTo
09/23/10  027       On line 3, change [15] to [14].
06/01/07  029  KD   In Def 2.4, change "all constants c" to "all positive constants c"
09/26/10  030  MT   Five lines from the bottom,
                    max(O(f(N)),O(g(N))) should instead be O(max(f(N),g(N)))
09/26/10  031  MT   Nine lines from the bottom, replace "oscillates"
                    with "does not exist".
11/06/06  036  EEO  In rule 3, replace "page 44" with "page 30"
06/21/06  058  EEO  The second line in the second paragraph should state that
                    the first element of the list is A0 (not AN as written)
06/24/10  059  MAW  Change "deleting the second element" to "deleting the third element"
10/16/07  064  GO   In last code fragment, need to return total before ending.
06/21/06  076  EEO  Paragraph 5, change "public inner" to "private inner"
06/21/06  077  EEO  Line 10 should refer to Figure 3.26, not Figure 3.25.
09/26/06  078  EEO  Caption for Fig 3.26 should have MyLinkedList instead of MyList
04/10/06  081  MAW  In the remove method, the okToRemove flag should be set
                    to false instead of true on line 31.
               EEO  Change line 30 to
                       MyLinkedList.this.remove( current.prev );
               EEO  After line 31, add a line:
                       expectedModCount++;
               EEO  Caption for Fig 3.32 should have MyLinkedList instead of MyList
10/18/07  081  DS   In later printings, line 19 was inadvertantly changed
                    in an attempt to fix the above error. The flag should
                    be set to true on line 19, and false on line 31.
06/21/06  080  EEO  getNode throws an exception if idx > size(), rather than
                    idx > size() - 1, but since it is called directly by
                    get, set, and remove( int idx ), all those routines fail
                    to throw an exception when the index is size(). The 
                    simplest fix is as follows: change getNode to accept
                    two additional parameters (lower and upper), to be
                    used in the test at line 11. Provide a second getNode
                    with only one parameter, that passes 0 and size() -1.
                    This will fix get, set, and remove. But it breaks add,
                    because size() is a valid index for add. Change add
                    to invoke the three-parameter getNode, with 0, and size()
                    as the lower and upper bounds. This fix is in the
                    revised online code.
02/24/10  097       Make the splice method public, and add a space after the first (
02/07/06  108  MAW  First sentence of Sec 4.2.1, change "tree has at most"
                    to "tree node has at most"
09/26/06  114  EEO  Line 43, replace Figure 4.23 with Figure 4.25
11/06/06  115  EEO  Line 5 in Fig. 4.18:  replace "@return node containing the
                    matched item" by "@return true if the item is found, false
                    otherwise".
10/10/10  120  MT   In the last sentence of the first paragraph in Section 4.3.5,
                    clarify that in the case of remove, the "accessed item" 
                    refers to the replacement node in the two-item case.
02/07/06  123  MAW  Next to last line, change .328 to 1.328.
08/01/06  124  PJV  Figure 4.30, the far right node at height 7 is missing its left child. 
02/07/06  132  MAW  Last occurrance, change "rotateWithLeftChild" to
                    "rotateWithRightChild"

07/01/11  135  DS2  Deletions in AVL tree aren't that hard.  Third edition code
                    shows it can be done with one extra line of code.
10/11/10  135  MT   In lines 4, 11, 19, 20 of Section 4.5, change O(N) to THETA(N).
02/07/06  135  MAW  In Sec 4.5, paragraph 2, line 2, change "as long at it" to
                    "as long as it"
02/07/06  147  MAW  Item 5, change "L children" to L "data items"
02/07/06  148  MAW  Line 9, change "first level could " to "next level could"
06/21/06  148  EEO  The last word in the fourth sentence in the third paragraph
                    should be "item", not "child".
10/16/07  153  GO   Four lines from the bottom, change "two characters" to "two words"
02/07/06  165  MAW  In Exercise 4.51 change "in a binary search tree" to
                    "in an N node binary search tree" (with N italicized)
09/26/06  175  EEO  In line 27 of Figure 5.9, replace "theSize" with "currentSize"
10/20/09  183  GO   The constructors do not use a prime number for the table size.
                    Fix allocateArray (line 35) to do so.
12/22/10  184  CY   Although it is mentioned in the text on pg 181, the code for
                    findPos should have a comment to explain that table must be half-empty.
12/22/10  194  MT   Eight lines from the bottom, remove the parentheses around mod 10.
11/06/06  207  EEO  The caption for Fig. 6.8 should read "Procedure to insert
                    into a binary heap" instead of "Procedures to insert into
                    a binary heap".
05/21/08  240  BC   In Exercise 6.17, replace "full complete" with "perfect binary"
06/24/10  248  HJ   On the third line of 7.2.3, replace "element comparisons"
                    with "tests"
06/25/10  256  SW   In the first paragraph of 7.5.1, "at most 2N" can be more
                    accurately stated as "less than 2N", and "at most 2 log i
                    (with floor function)" is more accurately stated as
                    "less than 2 log (N-i-1) (with floor function retained)"
09/26/06  257  HK   In heapsort, the loop at line 7 can start at a.size( ) / 2 - 1.
               WD   It must if zero length arrays are allowed.
05/21/08  259  CK   In the fourth figure, move Cctr one more spot to the right.
12/22/10  296  MT   Three lines from the bottom, replace 2 occurrences of big-Oh by big-Theta.
02/08/06  286  MAW  In Exercise 7.10, change "line 2" to "line 11" in two places.
06/21/06  300  EEO  In the second line from the bottom of the page, "tree" should
                    be replaced by "forest".
12/22/10  323  MT   For completeness, we should mention how the indegrees are
                    computed and that it takes time O( |E| + |V| ).
12/22/10  337  MT   The pseudocode would be cleaner if NOT_A_VERTEX is avoided by using
                        while( there is an unknown distance vertex )
                    Similarly,  after the if( !w.known ) test, it would be
                    cleaner to add a line (with associated braces)
                                    DistType cvw = cost of edge from v to w;
06/25/10  342  SW   Paragraph 4, line 2, change "words to be connected" to
                    "first word on the ladder"
11/06/06  356  EEO  Figure 9.58:  replace "//Edge e = (u.v)" by "//Edge e = (u,v)".
06/01/07  356  EEO  In Figure 9.58, line 4, replace DisjSet with DisjSets
12/22/10  356  MT   Add additional code to collect and return the MST edges.

07/11/06  ???  MAW  At the end of Chapter 9, in the references, add the
                    following as the best deterministic minimum spanning tree algorithm:
                     Bernard Chazelle: A minimum spanning tree algorithm with
                     Inverse-Ackermann type complexity. J. ACM 47(6): 1028-1047 (2000)
06/25/10  402  SW   Last paragraph, change "M-1 extra" to "at most M-1 extra"
06/25/10  434  SW   Change "C is odd" to "A and C are odd"
08/26/09  434  MAW  The 48-bit random number generator has C=11.
02/08/06  459  MAW  Somehow in the typesetting, Exercise 10.58(a) was made into
                    10.59, Exercise 10.58 should have a, b, c, and then what is
                    typeset as Exercise 10.60, should be 10.59 and subsequent
                    exercises renumbered.
10/28/10  461  MAW  Line 7 of the references, change [38] to [39].
06/25/10  471  SW   Line 3 of the proof, change "two trees" to "two queues"
06/25/10  472  SW   Change "(collection) of" to "(collection of)"
06/25/10  480  SW   Change "ith youngest" to "ith oldest"
10/17/10  485  MT   In the proof, AT is used as amortized time, but this is
                    never explicitly stated.
10/17/10  486  MT   In line 19, chage R_f(T) to either R_f(root) or R(T).
10/17/10  487  MT   In the last paragraph, in order to show that insert
                    takes O(log N) amortized time, we should also show that
                    the step of adding the leaf into the tree adds at
                    most log N to the potential. Similarly some care needs
                    to be taken when describing the non-splaying steps
                    in the deletion, which also change the potential.
                    The arguments are not complicated, and should have been included. 
11/24/08  506  ME   Change "coloring the root red" to "coloring the root sentinel red"

Credits

BC    Brian Curless
BLS   Barbara Li Santi
CK    Craig Kovatch
CY    Chee Yap
DS    Dominic Savoie
DS2   Dan Sleator
EEO   Evelyn Obaid
GO    Greg Ozbirn
HE    He Jiang
HK    Heinrich Kuettler
KD    Ketil Danielsen
ME    Mitch Edelman
MT    Martin Tompa
PJV   Peter J. van Wesep
SW    Shi Weili
TM    Thomas Meyer
WD    William Deng

Printing History

1 2 3 4 5 6 7 8 9 10