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.