Errata for Algorithms, 4th Edition, Third Printing (October 2012)


CHAPTER 1

p. 104, diagram

Printed: orphaned object points to 12/31/1999
Fixed: orphaned object should point to 1/1/2011
Reported by Mikael Hassam, 27-Nov-12.

p. 117, Exercise 1.2.15

Printed: String input = StdIn.readAll();
Fixed: String input = in.readAll();
Reported by Bin Zhang, 07-Nov-12.

p. 200

Printed: you cannot fit more than about 32 million int value or 16 million double values
Fixed: you cannot fit more than about 256 million int value or 128 million double values
Reported by Christopher Kirby, 31-Jan-13.

p. 204

Printed: A substring takes constant extra memory and forming a substring takes constant time.
Fixed: This remains true in Java 6 but changed in Oracle/OpenJDK Java 7, Update 6. Now, a substring takes linear extra memory and time. See this article for more details.
Reported by Kevin Wayne, 12-Dec-12.

p. 220

Printed: calling find() for each pair
Fixed: calling connected() for each pair
Reported by Mark Fox, 06-Feb-13.

p. 228

Printed: private int find
Fixed: public int find
Reported by Kevin Wayne, 04-Oct-12.

p. 258

Printed: largest increment less than N/3
Fixed: smallest increment greater than or equal to floor(N/3)
Reported by Mark Fox, 15-Feb-13.


CHAPTER 2

p. 304, Exercise 2.3.14

Printed: 2 / (j - i)
Fixed: 2 / (j - i + 1)
Reported by Ervin Varga, 05-Apr-13.

p. 334, Exercise 2.4.34

Printed: exch(i, N--)
Fixed: exch(qp[i], N--)
Reported by Ervin Varga, 05-Apr-13.


CHAPTER 3

p. 454, Exercise 3.3.40

Printed: if (!isRed(h.left.left))
Fixed: if (isRed(h.left.left))
Reported by Bin Zhang, 23-Mar-13.


CHAPTER 4

p. 573, figure

Printed: there are 5 objects marked as reachable that are not reachable
Fixed: make them reachable
Reported by Alexander Kanavin, 03-Jan-12.

p. 620

Printed: PrimMST takes an edge v from the priority queue.
Fixed: PrimMST takes a vertex v from the priority queue.
Reported by Paulo Feofiloff, 15-Feb-13.

p. 621

Printed: Edges 4-7 and 2-7 do not affect the priority queue
Fixed: Edge 2-7 does not affect the priority queue. Edge 4-7 (0.37) should replace edge 0-4 (0.38) on the priority queue until edge 4-5 replaces it.
Reported by Alex Liu, 09-Dec-12.

p. 623

Printed: The number of edges on the priority queue is at most V.
Fixed: The number of vertices on the priority queue is at most V.
Reported by Paulo Feofiloff, 15-Feb-13.


CHAPTER 5

p. 715

Printed: The efficiency of this code depends on substring() being a constant-time operation.
Fixed: This property no longer holds beginning in Java 7, Update 6.
Reported by Kevin Wayne 12-Dec-12.

p. 770

Printed: at position 15 and slide to the right five positions
Fixed: at position 15 and slide to the right four positions
Reported by Heryandi 04-Jan-13.

p. 842

Printed: The efficiency of compress() depends on substring() being a constant-time operation.
Fixed: This property no longer holds beginning in Java 7, Update 6.
Reported by Kevin Wayne 12-Dec-12.


CHAPTER 6

p. 883

Printed: The efficiency of the constructor depends on substring() being a constant-time operation.
Fixed: This property no longer holds beginning in Java 7, Update 6. to use charAt().
Reported by Kevin Wayne 12-Dec-12.