Errata for Algorithms, 4th Edition, Second Printing (January 2012)
CHAPTER 1
p. 30, 31, 206 StdRandom API
Printed: | initialize(seed) |
Fixed: | setSeed(seed) |
p. 42, top figure
Printed: | StdDraw.line(x0, y0, x1, y1) |
Fixed: | StdDraw.line(x1, y1, x2, y2) |
p. 136-137
Printed: | public void push (String item) and public String pop() |
Fixed: | public void push (Item item) and public Item pop() |
p. 145, bottom figure
Printed: | Node last = new Node() |
Fixed: | last = new Node() |
p. 171, Exercise 1.3.45
Printed: | stack does not overflow |
Fixed: | stack does not underflow |
p. 175
Printed: | StdOut.println(count + " triples " + time) |
Fixed: | StdOut.println(count + " triples " + time + " seconds") |
p. 211, Exercise 1.4.23
Printed: | differ by more than |
Fixed: | differ by less than |
p. 227
Printed: | number of array accesses for the union() operation for the pair 0-i is exactly 2i + 2 |
Fixed: | number of array accesses for the union() operation for the pair 0-i is exactly 2i + 3 |
p. 237, Problem 1.5.12
Printed: | by adding a loop to union() that links every site on the paths from p and q to the roots of their trees to the root of the new tree |
Fixed: | by adding a loop to find() that links every site on the path from p to the root directly to the root |
CHAPTER 2
p. 248
Printed: | the number of array accesses is a linear function of the array size |
Fixed: | the number of exchanges is a linear function of the array size |
p. 279, Proposition H
Printed: | Number of passes through the array is precisely floor(lg N). |
Fixed: | Number of passes through the array is precisely ceil(lg N). Delete text referring to 2^n <= N < 2^n+1. |
p. 325
Printed: | top right heap has M and L highlighted in light red |
Fixed: | E should also be highlighted |
p. 333
Printed: | public Item min() |
Fixed: | public Key min() |
p. 334
Printed: | Item item |
Fixed: | Key key |
p. 334
Printed: | exch(k, N--); |
Fixed: | IndexMinPQ.java |
CHAPTER 3
No errata reported.
CHAPTER 4
p. 408, top figure
Printed: | 8 keys in left subtree(twice) |
Fixed: | 6 keys in left subtree (twice) |
p. 544
Printed: | more tinyG.txt |
Fixed: | java Graph tinyG.txt |
p. 585
Printed: | point from vertex consumes organisms of the specifies indicated by the point to vertex |
Fixed: | point to vertex consumes organisms of the specifies indicated by the point from vertex |
p. 592
Printed: | KosarajuSharirCC |
Fixed: | KosarajuSharirSCC |
p. 625, Proposition N
Printed: | up to E find() and V union() operations |
Fixed: | up to E connected() and V union() operations |
p. 653
Printed: | distTo[3] = 0.97 and edgeTo[3] = 3->7 0.37 |
Fixed: | distTo[3] = 0.99 and edgeTo[3] = 3->7 0.39 |
p. 660
Printed: | public Iterable<Edge> pathTo(int v) |
Fixed: | public Iterable<DirectedEdge> pathTo(int v) |
p. 673
Printed: | q.enqueue(w) |
Fixed: | queue.enqueue(w) |
p. 674
Printed: | relax(v) and private void relax(int v) |
Fixed: | relax(G, v) and private void relax(EdgeWeightedDigraph G, int v) |
CHAPTER 5
p. 705, Proposition A
Printed: | Key-indexed counting uses 8N + 3R + 1 array accesses |
Fixed: | Key-indexed counting uses 11N + 4R + 1 array accesses |
p. 749, Proposition K
Printed: | A search hit or an insertion in a TST uses a character compare for each character in the search key. |
Fixed: | In addition to the ~ lg N compares, a search hit or an insertion ... |
p. 764
Printed: | M not initialized |
Fixed: | M = pat.length() |
p. 833, Proposition U
Printed: | (s1, r1) |
Fixed: | (s1, f1) |
p. 833, Proposition U
Printed: | set of n-1 symbols |
Fixed: | set of r-1 symbols |
CHAPTER 6
p. 896
Printed: | return cap - flow; |
Fixed: | return capacity - flow; |