Errata, First Printing (March 2011)


CHAPTER 1

p. 16

Printed: i++ is the same as i = i + 1 and has the value i in an expression. Similarly, i-- is the same as i = i - 1. The code ++i and --i are the same except that the expression value is taken after the increment/decrement, not before.
Fixed: ++i is the same as i = i + 1; both have the value i + 1 in an expression. Similarly, --i is the same as i = i - 1. The code i++ and i-- are the same except that the expression value is the value before the increment/decrement, not after.
Reported by David Durst, 15-Sep-11.

p. 23

Printed: if (c > 0) return Double.NaN;
Fixed: if (c < 0) return Double.NaN;
Reported by Ali Tekin, 05-Sep-11.

p. 52

Printed: 10 & 6 is 14
Fixed: 10 | 6 is 14
Reported by Zhe Lu, 05-Jul-11.

p. 55, Exercise 1.1.7c

Printed: for (int j = 0; j < N; j++)
Fixed: for (int j = 0; j < 1000; j++)
Reported by Karl Lopes, 14-Nov-11.

p. 59, Exercise 1.1.27

Printed: binomial(N-1, k) and binomial(N-1, k-1)
Fixed: binomial(N-1, k, p) and binomial(N-1, k-1, p)
Reported by David Sprague, 28-May-11.

p. 59, Exercise 1.1.27

Printed: if ((N == 0 || (k < 0)) return 1.0;
Fixed: if (N == 0 && k == 0) return 1.0; and if (N < 0 || k < 0) return 0.0;
Reported by David Sprague, 28-May-11.

p. 76, test client

Printed: Interval1D x and Interval1D y
Fixed: Interval1D xinterval and Interval1D yinterval
Reported by Sam Kramer, 17-May-11.

p. 76, test client

Printed: Point
Fixed: Point2D
Reported by Sam Kramer, 17-May-11.

p. 76, test client

Printed: box.draw()
Fixed: draw box using xlo, xhi, ylo, and yhi and remove draw() methods from Interval1D and Interval2D or provide accessor methods in Interval1D to access endpoints.
Reported by Sam Kramer, 17-May-11.

p. 81

Printed: s.rank(".");
Fixed: s.indexOf(".");
Reported by Pradeep Rao, 05-May-11.

p. 94-95

Printed: avg()
Fixed: mean()
Reported by Sam Kramer, 29-Jun-11.

p. 99, Whitelist client

Printed: set.rank(key) == -1
Fixed: !set.contains(key)
Reported by Kevin Wayne, 02-Mar-11.

p. 104, orphaned object figure

Printed: b = a;
Fixed: a = b; and corresponding fix in text
Reported by Wang Ning, 15-Mar-11.

p. 126

Printed: implementation of the readDoubles() static method; convert between the client's double primitive type and the queue's Double wrapper type.
Fixed: implementation of the readInts() static method; convert between the client's int primitive type and the queue's Integer wrapper type.
Reported by Ali Tekin, 07-Sep-11.

p. 140, table

Printed: to be or that to be
Fixed: to be or not to be
Reported by Max Rubin, 27-Sep-11.

p. 162, Exercise 1.3.9

Printed: ( ( 1 + 2 ) * ( ( 3 - 4 ) *( 5 - 6 ) )
Fixed: ( ( 1 + 2 ) * ( ( 3 - 4 ) *( 5 - 6 ) ) )
Reported by Karl Lopes, 14-Nov-11.

p. 171, Exercise 1.3.49

Printed: with three stacks
Fixed: with a constant number of stacks
Reported by Gustavo Brown, 09-Apr-11.

p. 202

Printed: an array of N Date objects (page 91) uses 24 bytes (array overhead) plus 8N bytes (references) plus 32 bytes for each object and 4 bytes of padding, for a grand total of 24 + 40N bytes.
Fixed: an array of N Date objects (page 91) uses 24 bytes (array overhead) plus 8N bytes (references) plus 32 bytes for each object, for a grand total of 24 + 40N bytes.
Reported by Rishi Narang, 21-Sep-11.

p. 202

Printed: plus M times 16 bytes (overhead for the row arrays)
Fixed: plus M times 24 bytes (overhead for the row arrays)
Reported by Kevin Wayne, 21-Sep-11.

p. 203, array of objects figure

Printed: object overhead is 12 bytes
Fixed: object overhead is 16 bytes
Reported by Natalie Weires, 20-Sep-11.

p. 204, array of objects figure

Printed: memory for char[] array is 36 bytes
Fixed: memory for char[] should be 56 bytes
Reported by Kevin Wayne, 20-Sep-11.

p. 210, Exercise 1.4.18

Printed: a[i-1] < a[i] < a[i+1]
Fixed: a[i] < a[i-1] and a[i] < a[i+1]
Reported by Wang Ning, 21-Mar-11.

p. 213, Exercise 1.4.36

Printed: linked list of Integer memory: ~ 64 N
Fixed: linked list of Integer memory: ~ 56 N
Reported by Wang Ning, 23-Mar-11.

p. 226

Printed: in the worst case, it needs 2 N + 1 array accesses
Fixed: in the worst case, it needs 2 N - 1 array accesses
Reported by Victoria Solomon, 15-Sep-11.

p. 231

Printed: not only is weighted quick-find with path compression
Fixed: not only is weighted quick-union with path compression
Reported by Marcos Lanio, 22-Sep-11.


CHAPTER 2

p. 264, Exercise 2.1.3

Printed: number of times the test a[j] < a[min] fails
Fixed: number of times the test a[j] < a[min] succeeds
Reported by Wayne Snyder, 22-Jul-11.

pp. 272, 274

Printed: C(floor(N/2)) is left half and C(ceil(N/2)) is right half
Fixed: C(ceil(N/2)) is left half and C(floor(N/2)) is right half
Reported by David McKenna, 3-Oct-11.

p. 289

Printed: puts (a[i]) into position
Fixed: puts (a[j]) into position
Reported by Josphat Magutt, 21-Oct-11.

p. 311

Printed: reverse the order and print them in increasing order
Fixed: reverse the order and print them in decreasing order
Reported by Wang Ning, 22-Apr-11.

p. 312, table

Printed: contents (ordered) column is truncated to first 5 items
Fixed: recrop figure
Reported by Kai Sheng Tai, 15-May-11.

p. 317, remove the maximum figure

Printed: H is parent if I
Fixed: H and I should be exchanged in sink down
Reported by Kevin Wayne, 20-Jun-11.

p. 317, insert figure

Printed: N is parent of P (twice)
Fixed: P should be parent of N
Reported by Abhijith Madhav, 23-Aug-11.

p. 318

Printed: See pages 145-147 for implementations of these helper methods.
Fixed: See pages 315-316 for implementations of these helper methods.
Reported by Evgeni Dimitrov, 11-Apr-11.

p. 321

Printed: we can restore the heap invariant with a sink operation (if the key increases) and a swim operation (if the key decreases)
Fixed: we can restore the heap invariant with a sink operation (if the key decreases) and a swim operation (if the key increases)
Reported by Abhijith Madhav, 23-Aug-11.

p. 340

Printed: v.who.compareTo(w.when)
Fixed: v.who.compareTo(w.who)
Reported by Daniel Xu, 01-Oct-11.


CHAPTER 3

p. 469, figure

Printed: symbol table value associated with C is 5
Fixed: it should be 4
Reported by Rishi Narang, 24-Oct-11.

p. 471

Printed: if (N > 0 N == M/8) resize(M/2)
Fixed: if (N > 0 && N == M/8) resize(M/2)
Reported by Kevin Murphy, 22-May-11.

p. 476, table

Printed: separate-chaining hash table memory: ~48N + 64M
Fixed: ~48N + 32M
Reported by Bob Sedgewick, 02-Mar-11.

p. 481, Exercise 3.4.12

Printed: with the hash values given below
Fixed: hash values not given below - add table
Reported by Wang Ning, 04-Jun-11.


CHAPTER 4

p. 520, figure

Printed: 18 edges and 19 vertices
Fixed: 17 edges and 18 vertices
Reported by Ali Tekin, 27-Sep-11.

p. 523, figure

Printed: avgDegree() returns an int
Fixed: should return a double
Reported by Wenley Tong, 27-Oct-11.

p. 540

Printed: while (!q.isEmpty())
Fixed: while (!queue.isEmpty())
Reported by Nikhil Yegya-Raman, 07-Apr-11.

p. 558, tinyGex2.txt

Printed: 3 10
Fixed: 5 0
Reported by Wang Ning, 13-Jul-11.

p. 577, figure

Printed: Entries in column for x: 3 4 4 4
Fixed: Entries in column for x: 3 4 5 5
Reported by Abhijith Madhav, 19-Nov-11.

p. 581

Printed: return order == null)
Fixed: return order != null)
Reported by Anna Simpson, 05-Nov-11.

p. 588, Proposition H

Printed: The first of these is not possible because there is a path from v to s.
Fixed: The first of these is possible; need to fix proof.
Reported by Rob Schapire, 21-Mar-11.

p. 596, tinyDGex2.txt

Printed: 1 11
Fixed: 0 5 and direct edge from 0 to 5
Reported by Wang Ning, 27-Jul-11.

p. 617

Printed: Removes ineligible edges 1-3, 1-5, and 2-7 from the priority queue.
Fixed: Move to after "Adds 5 and 5-7" bullet.
Reported by Abhijith Madhav, 30-Nov-11.

p. 627

Printed: MinPQ<Edge> pq = new MinPQ<Edge>(G.edges())
Fixed: MinPQ constructor must takes an array, not an Iterable
Reported by Kevin Murphy, 22-May-11.

p. 672

Printed: relax 4->7 and 4->5 and put 7 and 4
Fixed: relax 4->7 and 4->5 and put 7 and 5
Reported by Daniel Kang and Nikhil Yegya-Raman, 11-Apr-11.

p. 677

Printed: we use a version of DirectedCycle from Section 4.3
Fixed: we use a version of DirectedCycle from Section 4.2
Reported by Andrew Callahan, 13-May-11.

p. 679

Printed: the number of units of the currency named on row s that is needed to buy 1 unit of the currency named on row t
Fixed: the number of units of the currency named on row t that can be bought with 1 unit of the currency named on row s
Reported by Kai Sheng Tai, 09-May-11.


CHAPTER 5

p. 721, figure

Printed: Gray bar on fourth column, under the sells subarray and above the word she.
Fixed: Remove it.
Reported by Andrew Callahan, 13-May-11.

p. 777

Printed: if (patHash == txtHash) return 0;
Fixed: if (patHash == txtHash && check(0)) return 0;
Reported by Kevin Murphy, 19-May-11.

p. 790

Printed: No mention of empty string ε
Fixed: Add empty string ε to definition, which denotes the set containing only one element—empty string.
Reported by Dave Walker, 15-May-11.

p. 826

Printed: For example, if we encode A with 0, B with 11111
Fixed: For example, if we encode A with 0, B with 1111
Reported by Woo-Hyung Cho, 18-Apr-11.

p. 840

Printed: (so we output 83 and add RAC to the table)
Fixed: (so we output 83 and add RAB to the table)
Reported by Richard Price, 13-Dec-11.


CHAPTER 6

p. 870, 872

Printed: put() several times
Fixed: add()
Reported by Kai Sheng Tai, 06-May-11.

p. 878

Printed: N-character text string has N(N-1)/2 substrings
Fixed: N-character text string has N(N+1)/2 substrings
Reported by Kai Sheng Tai, 06-May-11.

p. 880

Printed: substring.length()
Fixed: lrs.length()
Reported by Kevin Murphy, 22-May-11.

p. 889

Printed: // Check local equilibrium at each vertex.
Fixed: // Check local equilibrium at vertex v.
Reported by Bob Sedgewick, 15-May-11.

p. 890

Printed: Figure: reference to the same Edge object
Fixed: Figure: reference to the same FlowEdge object
Reported by Bob Sedgewick, 15-May-11.

p. 891

Printed: Third figure: flow on edge 0->2 is 1
Fixed: Third figure: flow on edge 0->2 should be 2
Reported by Daniel Kang, 24-Apr-11.

p. 897

Printed: residualCapTo()
Fixed: residualCapacityTo()
Reported by Natalie Weires, 11-Jan-12.