Mastering Algorithms with C

Errata for Mastering Algorithms with C

Submit your own errata for this product.


The errata list is a list of errors and their corrections that were found after the product was released. If the error was corrected in a later version or reprint the date of the correction will be displayed in the column titled "Date Corrected".

The following errata were submitted by our customers and approved as valid errors by the author or editor.

Color Key: Serious Technical Mistake Minor Technical Mistake Language or formatting error Typo Question Note Update



Version Location Description Submitted By Date Submitted Date Corrected
Printed
Page xv

Updated the "How to Contact Us" section in the Preface to read: We have tested and verified the information in this book to the best of our ability, but you may find that features have changed (or even that we have made mistakes!). Please let us know about any errors you find, as well as your suggestions for future editions, by writing to: O'Reilly & Associates, Inc. 101 Morris Street Sebastopol, CA 95472 1-800-998-9938 (in the U.S. or Canada) 1-707-829-0515 (international/local) 1-707-829-0104 (FAX) You can also send us messages electronically. To be put on the mailing list or request a catalog, send email to: info@oreilly.com To ask technical questions or comment on the book, send email to: bookquestions@oreilly.com We have a web site for the book, where we'll list examples, errata, and any plans for future editions. You can access this page at: http://www.oreilly.com/catalog/9781565924536/ For more information about this book and others, see the O'Reilly web site: http://www.oreilly.com

Anonymous    Jun 01, 2000
Printed
Page xii
2.4:

"first-in, last-out" (at end of line) now reads "first-in, first-out."

Anonymous    Mar 01, 2001
Printed
Page xiv
Under second item in "About the Code"

"Linux 5.1" now reads "RedHat Linux 5.1."

Anonymous    Mar 01, 2001
Printed
Page 13

Beginning with the third to last line on the page, it did read: "Thus, it remains valid even after f returns...The parameter iptr... so that when f returns..." Now reads: "Thus, it remains valid even after g returns...The parameter iptr... so that when g returns..."

Anonymous    Jun 01, 2000
Printed
Page 17
Figure 2-3, line at bottom

"char b[20]" now reads "char b[20];".

Anonymous    Mar 01, 2001
Printed
Page 22

At the bottom of the page, the last line of code did read: retval = list_ins_next(... Now reads: retval = list_rem_next(...

Anonymous    Jun 01, 2000
Printed
Page 27
The sentence

Think of the fragile leaf of a fern...smaller copy of the overall leaf; or the repeating patterns in a reflection... NOW READS: Think of the fragile leaf of a fern...smaller copy of the overall leaf. Think of the repeating patterns in a reflection...

Anonymous    Dec 01, 2003
Printed
Page 34

The equation at the bottom of the page did read: T(n) = 1 if n = 0 2T(n/2) + n if n > 0 Now reads: T(n) = 1 if n = 2 2T(n/2) + n if n = 1, n > 2

Anonymous    Jun 01, 2000
Printed
Page 36
answer to first question

Previously read "... the frame pointer, keeps track of the top of the stack as a program exicutes. It is also used to determine when the stack has grown too large. An interrupt is raised to signal the error. NOW READS: " ... the frame pointer addresses the top frame on the stack. It's the stack pointer that points to the actual top of the stack (that is, the point where the next stack frame will be pushed). Therefore, although a system could use the frame pointer to determine stack overflow, it probably is the stack pointer that would normally be used."

Anonymous    Dec 01, 2003
Printed
Page 49
Part II, line 5

"first-in, last-out" (at beginning of line) now reads "first-in, first-out."

Anonymous    Mar 01, 2001
Printed
Page 52
first words under "Description of Linked Lists:"

"Singly-linked lists..." wrongly HAD an extra space and an "s" in italics. This has been corrected.

Anonymous    Dec 01, 2003
Printed
Page 64

Line 5 from top did read: if (list_size(list) == 0) Now reads: if (list_size(list) == 1)

Anonymous    Jun 01, 2000
Printed
Page 91
At the top of the page, the lines

old_element = element->next; element->next = element->next->next; ARE NOW FOLLOWED by the two additional lines: if (old_element == clist_head(list)) list->head = old_element->next;

Anonymous    Dec 01, 2003
Printed
Page 99

Remove the text " in real time" under the item "X Window System".

Anonymous    May 01, 2008
Other Digital Version
99

Remove the text " in real time" under the item "X Window System".

Anonymous    May 01, 2008
Printed
Page 133
The 2nd-to-last sentence of the second paragraph under "Set Example: Set

Covering" now reads: The various player skill sets in P that are placed in set C together must cover all of the skills in set S.

Anonymous    Mar 01, 2001
Printed
Page 146-147

All occurrences of "int" in the implementation of hashpjw HAVE BEEN CHANGED to "unsigned int".

Anonymous    Dec 01, 2003
Printed
Page 162
In the table at the top of the page, the first line in the second column

1 / (1 - 0.50) < 2 now reas: < 1 / (1 - 0.50) = 2

Anonymous    Mar 01, 2001
Printed
Page 181

The definition for "Preorder traversal" has been changed to read: "In a preorder traversal for a given subtree, we first traverse its root, then to the left, and then to the right. As we explore subtrees to the left and right, we proceed in a similar manner using the left or right node as the root of the new subtree. The preorder traversal is a depth-first exploration, like that presented for graphs in Chapter 11, Graphs."

Anonymous    Jun 01, 2000
Printed
Page 182

The definition for "Inorder traversal" has been changed to read: "In an inorder traversal for a given subtree, we first traverse to the left, then to the root, and then to the right. As we explore subtrees to the left and right, we proceed in a similar manner using the left or right node as the root of the new subtree."

Anonymous    Jun 01, 2000
Printed
Page 182

The definition for "Postorder traversal" has been changed to read: "In a postorder traversal for a given subtree, we first traverse to the left, then to the right, and then to the root. As we explore subtrees to the left and right, we proceed in a similar manner using the left or right node as the root of the new subtree."

Anonymous    Jun 01, 2000
Printed
Page 190
section on bitree_merge

2nd line says "... by calling bitree_merge." This now reads "...by calling bitree_init."

Anonymous    Mar 01, 2001
Printed
Page 205
Under the section "bitree_remove", "Furthermore," HAS BEEN DELETED from

the second-to-last sentence.

Anonymous    Dec 01, 2003
Printed
Page 207

Change the value inside the circle to the far right from 81 to 83.

Anonymous    May 01, 2008
Other Digital Version
207

Change the value inside the circle to the far right from 81 to 83.

Anonymous    May 01, 2008
Printed
Page 215

A line of code has been added at the end of the page to read: static void destroy_right(BisTree *tree, BiTreeNode *node);

Anonymous    Jun 01, 2000
Printed
Page 219

In the function destroy_left, the calls did read: bitree_rem_left(tree, *position); bitree_rem_right(tree, *position); Now read: destroy_left(tree, *position); destroy_right(tree, *position);

Anonymous    Jun 01, 2000
Printed
Page 269
top of the page

It is the responsibility of the caller to manage the storage associated with data2. "data2" is now in ConstantWidth italics font.

Anonymous    Mar 01, 2001
Printed
Page 277
Example 11-2, last line on page

now reads: ...graph->match, NULL);

Anonymous    Mar 01, 2001
Printed
Page 277
last line on the page

The line that reads: set_init(&adjlist->adjacent, graph->match, graph->destroy); NOW READS: set_init(&adjlist->adjacent, graph->match, NULL); **AUTHOR'S RESPONSE It is important to note that when inserting an edge into a graph, the data2 parameter of graph_ins_edge must have *its own* storage allocated for it. For example, data2 cannot share storage with a vertex passed to graph_ins_vertex at some earlier time. For example, to create the graph below, we should do something like the following: Graph: --------- a -> b b --------- data2 = (char *)malloc(2); strcpy(data2, "b"); graph_ins_vertex(&graph, data2); data1 = (char *)malloc(2); strcpy(data1, "a"); graph_ins_vertex(&graph, data1); data2 = (char *)malloc(2); strcpy(data2, "b"); graph_ins_edge(&graph, data1, data2); Note that before the call to graph_ins_edge, we allocate new storage for data2. This is because inside of graph_ins_vertex, set_init initializes each new adjacency list with graph->destroy, which will be called once for each vertex in the adjacency list when the graph is destroyed. Since every vertex also appears in the list of AdjList structures, without its own storage each vertex will be destroyed more than once. One solution is to set the destroy parameter of set_init to NULL. However, this alternative poses problems in the form of consistency issues. The important thing to remember, therefore, is simply this: Before any piece of data is inserted into a data structure, it must have *its own* storage allocated for it. (Notice that it is perfectly acceptable in the call to graph_ins_edge, however, not to allocate new storage for data1 because data1 is used only to look up in which adjacency list data2 will be inserted; in other words, the graph does not have a pointer to data1 once the operation completes.

Anonymous    Aug 01, 2005
Printed
Page 290
There is an erroneous comma in the middle of the return statement.

Anonymous    Dec 01, 2003
Printed
Page 291

Change "acrylic" to "acyclic".

Anonymous    May 01, 2008
Other Digital Version
291

Change "acrylic" to "acyclic".

Anonymous    May 01, 2008
Printed
Page 304
In the second paragraph under the section on implementation and

analysis, the third sentence did read: "Since the element at the left of the sorted set..." Now reads: "Since the element just to the right of the sorted set..."

Anonymous    Jun 01, 2000
Printed
Page 323

In Example 12.5, change the line of code: int mgsort(void *data, int size, int esize, int i, ... to: int mgsort(void *data, int esize, int i, ... That is, remove "int size, " since this parameter is not used. We should also make sure that this is changed in the code on disk.

Anonymous    May 01, 2008
Other Digital Version
323

In Example 12.5, change the line of code: int mgsort(void *data, int size, int esize, int i, ... to: int mgsort(void *data, int esize, int i, ... That is, remove "int size, " since this parameter is not used. We should also make sure that this is changed in the code on disk.

Anonymous    May 01, 2008
Printed
Page 325

The second sentence in the "Description" section did read: "The argument k specifies the maximum integer in data." Now reads: "The argument k specifies the maximum integer in data, plus 1."

Anonymous    Jun 01, 2000
Printed
Page 325

The sentence in the "Complexity" section did read: "...the maximum integer in the unsorted set." Now reads: "...the maximum integer in the unsorted set, plus 1."

Anonymous    Jun 01, 2000
Printed
Page 325

The first sentence in the last paragraph on the page did read: "...the largest integer being sorted." Now reads: "...the largest integer being sorted, plus 1."

Anonymous    Jun 01, 2000
Printed
Page 327
If the allocation of storage for the sorted elements fails, we should

free the storage just allocated for the counts before returning. Thus, the lines: if ((temp = (int *)malloc(size * sizeof(int))) == NULL) return -1; should read: if ((temp = (int *)malloc(size * sizeof(int))) == NULL) { free(counts); return -1; }

Anonymous    Dec 01, 2003
Printed
Page 345

The values in the first three columns for i=4 in Figure 13.1 should be 4, 0.0, 0.5. That is, changed the value in the third column of this row, 1.5, to 0.5.

Anonymous    May 01, 2008
Other Digital Version
345

The values in the first three columns for i=4 in Figure 13.1 should be 4, 0.0, 0.5. That is, changed the value in the third column of this row, 1.5, to 0.5.

Anonymous    May 01, 2008
Printed
Page 346
2.1:

"i < k" now reads "i < j".

Anonymous    Mar 01, 2001
Printed
Page 363
Under "Related Topics", another related topic HAS BEEN ADDED before

"Error Approximation". The new topic READS AS FOLLOWS: Numerical Representation in Computers The representation of numbers in computers is finite. Consequently, computers are limited in the way they can work with certain types of numbers, such as those that are extremely small or large. An understanding of these limitations is important before undertaking most serious work in numerical analysis. This chapter assumes an understanding of these limitations.

Anonymous    Aug 01, 2005
Printed
Page 374
The ninth line down of code did read:

for (i = 0; i < (size / 8); i++) { Now reads: for (i = 0; i <= ((size - 1) / 8); i++) {

Anonymous    Jun 01, 2000
Printed
Page 451
The second sentence in the fourth paragraph on the page has been

changed to read: "To do this, we must ensure that the largest value that the block can store, considering its total number of bits, is less than n."

Anonymous    Jun 01, 2000
Printed
Page 503
middle of page, after the sentence

The straddle test determines the orientation of p3 relative to p2 and of p4 relative to p2 with respect to p1. The following HAS BEEN ADDED: It then determines the orientation of [p1] relative to [p4] and of [p2] relative to [p4] with respect to [p3]. Note that [ ] above indicates an item in constant width italic font. ALSO the sentence that begins: If the orientations are different, or if either orientation is 0... NOW READS: If the orientations of the points in either computation are different or 0, the straddle test succeeds, and the algorithm returns that the line segments intersect; otherwise, the line segments do not intersect.

Anonymous    Aug 01, 2005
Printed
Page 503-504

Code should be this: /***************************************************************************** * * * -------------------------------- lint.c ------------------------------- * * * *****************************************************************************/ #include "geometry.h" /***************************************************************************** * * * --------------------------------- lint --------------------------------- * * * *****************************************************************************/ int lint(Point p1, Point p2, Point p3, Point p4) { double z1, z2, z3, z4; int s1, s2, s3, s4; /***************************************************************************** * * * Perform the quick rejection test. * * * *****************************************************************************/ if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x) && MAX(p3.x, p4.x) >= MIN(p1.x, p2.x) && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y) && MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) { { return 0; } /***************************************************************************** * * * Determine whether the line segments straddle each other. * * * *****************************************************************************/ if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0) s1 = -1; else if (z1 > 0) s1 = 1; else s1 = 0; if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0) s2 = -1; else if (z2 > 0) s2 = 1; else s2 = 0; if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0) s3 = -1; else if (z3 > 0) s3 = 1; else s3 = 0; if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0) s4 = -1; else if (z4 > 0) s4 = 1; else s4 = 0; if ((s1 * s2 <= 0) && (s3 * s4 <= 0)) return 1; /***************************************************************************** * * * Return that the line segments do not intersect. * * * *****************************************************************************/ return 0; }

Anonymous    May 01, 2008
Other Digital Version
503-504

Code should be this: /***************************************************************************** * * * -------------------------------- lint.c ------------------------------- * * * *****************************************************************************/ #include "geometry.h" /***************************************************************************** * * * --------------------------------- lint --------------------------------- * * * *****************************************************************************/ int lint(Point p1, Point p2, Point p3, Point p4) { double z1, z2, z3, z4; int s1, s2, s3, s4; /***************************************************************************** * * * Perform the quick rejection test. * * * *****************************************************************************/ if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x) && MAX(p3.x, p4.x) >= MIN(p1.x, p2.x) && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y) && MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) { { return 0; } /***************************************************************************** * * * Determine whether the line segments straddle each other. * * * *****************************************************************************/ if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0) s1 = -1; else if (z1 > 0) s1 = 1; else s1 = 0; if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0) s2 = -1; else if (z2 > 0) s2 = 1; else s2 = 0; if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0) s3 = -1; else if (z3 > 0) s3 = 1; else s3 = 0; if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0) s4 = -1; else if (z4 > 0) s4 = 1; else s4 = 0; if ((s1 * s2 <= 0) && (s3 * s4 <= 0)) return 1; /***************************************************************************** * * * Return that the line segments do not intersect. * * * *****************************************************************************/ return 0; }

Anonymous    May 01, 2008