Errors in the textbook

Textbook errors for Algorithms in C (3rd Ed.) by Sedgewick.

This text seems to have a number of errors in its presentation. We have divided the errors into four categories, in decreasing order of importance. Presumably, most students shouldn't care much about the fourth category, but we are including them here anyhow.

In all cases, an error is described by the page it appears in. The "first" paragraph on a page is the paragraph at the very top of the page, regardless of which page starts it.

We want your errors! Submit them to Amit Kumar and your suffering will not be in vain.

Code errors

Page 19, Program 1.4. The code inside the for loops is wrong. The code should be:

for (i = p; i != id [i]; i = id [i])
  {id [i] = id [id [i]];}
for (j = p; j != id [j]; j = id [j])
  {id [j] = id [id [j]];}

(Eva Tardos)

Page 93, first paragraph. The code for deletion of the node following node x is wrong, and should be:
```
t = x -> next; x -> next = t -> next;
```
(Haye Chan)
Page 101, Table 3.1. The section on "circular, never empty" linked list is wrong. The code for first insert should be changed to:
```
head -> next = head;
```
(Haye Chan)
Page 101, Table 3.1. In the same section, the code for loop traversal is very wrong, as it will never execute the body of the loop. The test
t != head
will be failed immediately. I would suggest changing it to:
```
t = head;
do {
...body...
t = t -> next;
} while (t != NULL);
```
(dan brown)
Pages 150 and 152, Programs 4.6 and 4.8. The type of the UFunion function should be void, not int. (Eva Tardos)
Page 156, Program 4.10. There should be a typecast in the malloc statement in the function link NEW (), as:
```
link x = (link) malloc (sizeof *x);
```
(Dan Ryazansky). This is a fairly consistent error in the text, and in general, if you're not familiar with C, you should either come talk to us about how one should use malloc, or look at page 142 of the Kernighan and Ritchie reference on C, which discusses why this typecast is necessary. (Also, dan objects to the use of *x here in the sizeof expression--while it is true that sizeof doesn't evaluate its expression, it's still rude to make reference to objects like *x that don't yet exist.)
page 177, Program 4.20 the function QUEUEget is wrong. First it should check if the queue is empty, and return some sort of error message if it is. Second, it should check if the queue has one element, say by the instruction
```
if (q->head=q->tail)
```
and in this case reset the tail to
```
NULL
```
. (Rami Baalbaki)
Page 300, Program 6.17. The last lines of code is wrong; as written, the code copies into the first r-l+1 entries of the b array and then copies out of the entries with indices from l to r. A good way around this problem is to change the last line to:
```
 for (i=l; i <= r; i++) a [i] = b [i - l];
```
(Eva Tardos)
Page 299, in the one line code
```
 for (i = 0; i < N; i++) b[cnt[a[i]]++]; 
```
there must be something in the right hand side. Replace it by
```
   for (i = 0; i < N; i++) b[cnt[a[i]]++] = a[i];
```
(Haye Chan)
Page 521, Program 12.13. To find the k'th smallest element it checks if the left subtree has size t. If so, it returns the root. But then, it is returning the (k+1)'th smallest element. Modify the code to
```
   Item selectR(link h, int k)
   { int t = h->l->N;
     if (h==z) return NULLitem;
     if (t > k-1) return selectR(h->l,k);
     if (t < k-1) return selectR(h->r,k-t-1);
   }
```
(Eva Tardos)
Page 526, Program 12.16 Replace the line
```
 b = STinsert(b,a->item) 
```
by the line
```
 b = insertT(b,a->item) 
```
as STinsert just takes one parameter. (Rami Baalbaki)
Page 521. Program 12.13. The program checks h == z after the statement t = h->l->N;. It should check for h before assigning t to this value. (Rami Baalbaki)

COURSE PACKET, Page 428. In the visit procedure, when it pops a value k from the stack (the first statement in the while loop), it should check that it has not visited k before. So, the correct code is :

    visit (int k)
    {
      struct node *t;
      push(k);
      while(!stackempty())
       {
         k = pop();
         if (val[k] == 0)   ---- This is the change 
         {
           val[k] = ++id;
           for (t = adj[k]; t!=z; t = t->next)
                push(t->v);
          }
       }
    }

(Eva Tardos)

Major idea errors

Page 18, Figure 1.9. The top two pictures in this figure are what would result if we used the rule that whenever the pair entered are in the same component, we don't perform path compression. This is certainly not clear from the text, and in fact, is not what happens in the case of path compression by halving in Program 1.4. At the very least, this should be clearer. (Renny Shen)
Page 18, Figure 1.9 (again). The last picture in this figure is wrong; this output is what would result if we processed the pair 6 8, not 4 8 as the book claims. (dan brown)
Page 530. Line 3 - it says that Program 13.1 runs in linear time. But that is not true. It runs in O(n lgn) time. (Eva Tardos)

Minor idea errors

Page 7, first paragraph. The relation specified is transitive, not associative. (dan brown)
Page 15, Figure 1.6. Change "quick-find" in line 4 to "quick-union." (Victor Chang)
Page 16, Property 1.3. The algorithm follows at most 2 lg N + 1 pointers, not lg N, as stated. At most one path is of length lg N; the other is of length at most lg N -1. Also, to find that we're at the top of a path, 2 more pointers must be traversed; the overall total is 2 lg N + 1. Also, the symbol lg is not defined in this chapter. (Ronnie Choy)
Page 99, Figure 3.8. The unordered list is the one to which a points and the ordered list is the one to which b points, not the other way around, as the book suggests. (Ronnie Choy)
Page 155, second paragraph. A get operation decreases the size of the queue, and a put operation increases the size of the queue, not the other way around as the book suggests. (Jiesang Song)
Page 380, third paragraph. A node at position k has children at positions 3k-1,3k and 3k+1 (the nodes are numbered from 1 to N). (Vardges Melkonian)
Page 380, third paragraph. As above, the parent of k should be floor((k+2)/3) and not floor(k/3). (Ryan Kennedy)
Page 580, first paragraph. It says that cost of generating a new random number for each character in the key will be prohibitive. But this is not true. We can generate this random number once when setting up the hash function, store it aat some place and then use it. (Eva Tardos)

Typos

Page 7, Figure 1.1. There's a typo in the last line of the text of the figure--6-1 should appear in the second column, rather than having the 6 and the 1 in the second and third columns. (Rami Baalbaki)
Page 1, Figure 1.9. Fix "making make" error. (The subsequent content is also incorrect.) (dan brown)
Page 578, Program 14.1. The prime is 127, not 117 in the 6th line from top. (dan brown)
Page 46, it should be a_0*N*H_N + a_1*N + a_2 instead of 2*a_0*N*H_N + ... (Ronnie Choy)
Page 307, second paragraph. Replace i < j by i > j (Haye Chan)
Page 592, Figure 14.8. Top row, hash value for P is 8, not 6. (Jiesang Song)
Page 419, Figure 10.9. There are two b-y's in the figure. Remove the right one. (Jiesang Song)
Page 139. In the last set of postfix notations, it should be (4*6) instead of (4+6). (Rami Balbaki)