# 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(".");

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

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)

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

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.

p. 627

 Printed: MinPQ pq = new MinPQ(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.