Mastering Algorithms with C
by Kyle Loudon

This errata page lists errors outstanding in the most recent printing. 

If you have technical questions or error reports, you can send them to
booktech@oreilly.com.  Please specify the printing date of your copy.

This page was last modified on April 17, 2008.

Here's a key to the markup:

        [page-number]: serious technical mistake
        {page-number}: minor technical mistake
        <page-number>: important language/formatting problem
        (page-number): language change or minor formatting problem
        ?page-number?: reader question or request for clarification


Confirmed errors:


{269} the top of the page:
After the "It is the responsibility sentence..." the following should be added:

        Also, it is important to note that when inserting an edge into a
        graph, [data2] 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. The implementation and
        analysis section describes this further.

Note that [] above indicates an item in Courier bold-italics (see the text).
That is, the brackets should not be printed. The item enclosed within the
asterisks should be in italics (again, do not print the asterisks).



{273} under the heading "graph_ins_edge", immediately after the sentence:

        The call to set_insert returns an error if the edge already exists.

add the following (using the same rules as above for [ ] and asterisks):

        It is important to note that when inserting an edge into a
        graph, [data2] 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. This is because inside of
        *graph_ins_vertex*, *set_init* initializes each new adjacency list
        with the function passed as [destroy] to *graph_init*. This function
        is 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 would be
        destroyed more than once.


{323} FIX ON DISK
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.


{503-504} Modify the code for lint.c as shown below.


(40) (40) FIX IN SAFARI
Make Safari match the printed version for this errata:  

2nd paragraph (O-Notation section);
In equation formally defining the meaning of an upper bound function, greater than
and less than symbols are missing. I.e.,
"n  n0" should be (I think) "n > n0" and "f(n)  g(n)" should be (I think) "f(n) <=
g(n)".


[59] FIX ON DISKETTE that comes with the book for this errata:

In Example 5-2, towards the top of page, change the first occurrence
of:
list_size(list) == 0
to:
list_size(list) == 1

We also need to make sure that this is changed in list.c on the disk.


[117] FIX IN SAFARI
Make Safari match the printed version for this errata:

Starts in First Paragraph and continues through the chapter.;
the line reads:
...

If a member, m is in a set, S then membership is indicated by writing m S; otherwise, m S. For example, 
in the set S = {1,2,3}, 2 S, but 4 S. To effectively use sets, we should be familiar with some 
definitions, basic operations, and properties.

...
I do not know what the correct characters are which should be in the 4 places. I am hoping someone more 
knowledgeable about this can fix it.


(Chapter 4.5) FIX IN SAFARI
Make Safari match the printed version for this errata:

Chapter 4.5 (Questions & Answers), first answer;
(I am reading the book on Safari Books Online so it might be an error that is unique to the online 
version. This is also the reason why I can't give a page number.)

The answer to the first question

A: From lowest to highest, the correct order of these complexities is O (1), O (lg n), O (n), O (n lg 
n), O (n^2), O (n^2 lg n), O (n^3), O (2^n), O (3n), O (n!).

should read

A: From lowest to highest, the correct order of these complexities is O (1), O (lg n), O (n), O (n lg 
n), O (n^2), O (n^2 lg n), O (n^3), O (2^n), O (3^n), O (n!).

=> O(3^n) is missing the exponentiation, it is written as O(3n)


{496} FIX
Portuguese version: The use of "VertexColour" or "VertexColor" needs
to be consistent between the code example and the text itself (both in
the book and on the disk), whichever spelling is appropriate for this
locale.