Errata for Algorithms, 4th Edition, Fifth Printing (June 2014)


CHAPTER 1

p. 19

Printed: ArrayOutOfBoundsException
Fixed: ArrayIndexOutOfBoundsException
Reported by Tiru Bokka, 03-Jun-14.

p. 46

Printed: 84 48 68 10 18 98 12 23 54 57 48 33 16 77 11 29
Fixed: 84 48 68 10 18 98 12 23 54 57 33 16 77 11 29
Reported by Dave Anderson, 10-Jan-15.

p. 118, Exercise 1.2.18

Printed: The solution does not properly implement the one-pass algorithm.
Fixed: See Accumulator.java.
Reported by Rindra Ramamonjison, 27-Feb-15.

p. 202

Printed: a String object of length N typically uses 40 bytes for the String object
Fixed: a String object of length N typically uses 32 bytes for the String object
Reported by Ken Voskuil, 29-Jan-15.

p. 227

Printed: the number of array accesses is exactly 2i + 3 because site 0 is at depth i. Thus, the total number of array accesses is 2(1 + 2 + ... + N) ~ N^2.
Fixed: the number of array accesses is exactly 2i + 1 because site 0 is at depth i - 1. Thus, the total number of array accesses is 3 + 5 + 7 + ... + (2N - 1) ~ N^2.
Reported by Jonson, 14-Jun-14.


CHAPTER 2

No errata reported at this time.


CHAPTER 3

p. 407

Printed: min() throws java.lang.NullPointerException if symbol table is empty
Fixed: should return null or throw a java.util.NoSuchElementException
Reported by Gopi Jeyaram, 20-Oct-14.

p. 409

Printed: select() throws java.lang.NullPointerException if k is invalid index
Fixed: should return null or throw a java.util.NoSuchElementException
Reported by Gopi Jeyaram, 20-Oct-14.

p. 453, 455 (Exercise 3.3.39 and 3.3.40)

Printed: moveRedLeft() and moveRedRight()
Fixed: Need extra call to flipColors(h) as last line in if statements
Reported by Francesco Mari, 23-Sep-14.

p. 474

Printed: call resize(2*M) when N >= M/2 and resize(M/2) when (N >= 0 && N <= M/8)
Fixed: call resize(2*M) when N >= 8*M and resize(M/2) when (N >= 0 && N <= 2*M)
Reported by Chong-Lim Kim, 10-Jul-15.


CHAPTER 4

p. 529

Printed: wt[find[v]]
Fixed: sz[find[v]]
Reported by Michael Bell, 21-Jun-14.

p. 573

Printed: The "potentially accessible objects" point to the gray nodes
Fixed: The "potentially accessible objects" should point to the white nodes
Reported by Andrey Dubinchak, 08-Oct-14.

p. 621

Printed: second figure: 4 0-4 0.38
Fixed: second figure: 4 4-7 0.37
Reported by Andrey Dubinchak, 09-Nov-14.

p. 653

Printed: figure: distTo[6] is 1.49
Fixed: it should be 1.51
Reported by Andrew Mastin, 16-Apr-16.

p. 656

Printed: using time and space proportional to E V log V
Fixed: using time proportional to E V log V and space proportional to V^2
Reported by Chong-Lim Kim, 03-Aug-15.

p. 675

Printed:
Fixed:
 
Add to third bullet: Then relax 7->5, 5->4 and 5->7, which are ineligible.
Add to fifth bullet: Then relax 6->0 and 6->2, which are ineligible.
Reported by Chong-Lim Kim, 15-Aug-15.


CHAPTER 5

p. 736

Printed: cnt += size(next[c]);
Fixed: cnt += size(x.next[c]);
Reported by Daniel Pacak, 05-Jan-15.

p. 763

Printed: they are the first j-1 characters in the pattern
Fixed: they are the first j-1 characters in the pattern starting at index 1
Reported by Chong-Lim Kim, 15-Aug-15.

p. 771

Printed: If the string character causing the mismatch does appear in the pattern
Fixed: If the string character causing the mismatch does not appear in the pattern
Reported by Christian Chua, 20-Apr-15.


CHAPTER 6

p. 883

Printed: private Suffix(String s, int index)
Fixed: private Suffix(String text, int index)
Reported by Mike Müller, 05-Jul-16.

p. 889

Printed: private boolean isFeasible(FlowNetwork G)
Fixed: private boolean isFeasible(FlowNetwork G, int s, int t)
Reported by Anton Khabbaz, 16-Jul-14.