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. |
p. 23
Printed: | if (c > 0) return Double.NaN; |
Fixed: | if (c < 0) return Double.NaN; |
p. 52
Printed: | 10 & 6 is 14 |
Fixed: | 10 | 6 is 14 |
p. 55, Exercise 1.1.7c
Printed: | for (int j = 0; j < N; j++) |
Fixed: | for (int j = 0; j < 1000; j++) |
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) |
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; |
p. 76, test client
Printed: | Interval1D x and Interval1D y |
Fixed: | Interval1D xinterval and Interval1D yinterval |
p. 76, test client
Printed: | Point |
Fixed: | Point2D |
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. |
p. 81
Printed: | s.rank("."); |
Fixed: | s.indexOf("."); |
p. 94-95
Printed: | avg() |
Fixed: | mean() |
p. 99, Whitelist client
Printed: | set.rank(key) == -1 |
Fixed: | !set.contains(key) |
p. 104, orphaned object figure
Printed: | b = a; |
Fixed: | a = b; and corresponding fix in text |
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. |
p. 140, table
Printed: | to be or that to be |
Fixed: | to be or not to be |
p. 162, Exercise 1.3.9
Printed: | ( ( 1 + 2 ) * ( ( 3 - 4 ) *( 5 - 6 ) ) |
Fixed: | ( ( 1 + 2 ) * ( ( 3 - 4 ) *( 5 - 6 ) ) ) |
p. 171, Exercise 1.3.49
Printed: | with three stacks |
Fixed: | with a constant number of stacks |
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. |
p. 202
Printed: | plus M times 16 bytes (overhead for the row arrays) |
Fixed: | plus M times 24 bytes (overhead for the row arrays) |
p. 203, array of objects figure
Printed: | object overhead is 12 bytes |
Fixed: | object overhead is 16 bytes |
p. 204, array of objects figure
Printed: | memory for char[] array is 36 bytes |
Fixed: | memory for char[] should be 56 bytes |
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] |
p. 213, Exercise 1.4.36
Printed: | linked list of Integer memory: ~ 64 N |
Fixed: | linked list of Integer memory: ~ 56 N |
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 |
p. 231
Printed: | not only is weighted quick-find with path compression |
Fixed: | not only is weighted quick-union with path compression |
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 |
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 |
p. 289
Printed: | puts (a[i]) into position |
Fixed: | puts (a[j]) into position |
p. 311
Printed: | reverse the order and print them in increasing order |
Fixed: | reverse the order and print them in decreasing order |
p. 312, table
Printed: | contents (ordered) column is truncated to first 5 items |
Fixed: | recrop figure |
p. 317, remove the maximum figure
Printed: | H is parent if I |
Fixed: | H and I should be exchanged in sink down |
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. |
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) |
CHAPTER 3
p. 469, figure
Printed: | symbol table value associated with C is 5 |
Fixed: | it should be 4 |
p. 471
Printed: | if (N > 0 N == M/8) resize(M/2) |
Fixed: | if (N > 0 && N == M/8) resize(M/2) |
p. 476, table
Printed: | separate-chaining hash table memory: ~48N + 64M |
Fixed: | ~48N + 32M |
p. 481, Exercise 3.4.12
Printed: | with the hash values given below |
Fixed: | hash values not given below - add table |
CHAPTER 4
p. 520, figure
Printed: | 18 edges and 19 vertices |
Fixed: | 17 edges and 18 vertices |
p. 523, figure
Printed: | avgDegree() returns an int |
Fixed: | should return a double |
p. 540
Printed: | while (!q.isEmpty()) |
Fixed: | while (!queue.isEmpty()) |
p. 558, tinyGex2.txt
Printed: | 3 10 |
Fixed: | 5 0 |
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) |
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. |
p. 596, tinyDGex2.txt
Printed: | 1 11 |
Fixed: | 0 5 and direct edge from 0 to 5 |
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<Edge> pq = new MinPQ<Edge>(G.edges()) |
Fixed: | MinPQ constructor must takes an array, not an Iterable |
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 |
p. 677
Printed: | we use a version of DirectedCycle from Section 4.3 |
Fixed: | we use a version of DirectedCycle from Section 4.2 |
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 |
CHAPTER 5
p. 721, figure
Printed: | Gray bar on fourth column, under the sells subarray and above the word she. |
Fixed: | Remove it. |
p. 777
Printed: | if (patHash == txtHash) return 0; |
Fixed: | if (patHash == txtHash && check(0)) return 0; |
p. 790
Printed: | No mention of empty string ε |
Fixed: | Add empty string ε to definition, which denotes the set containing only one element—empty string. |
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 |
p. 840
Printed: | (so we output 83 and add RAC to the table) |
Fixed: | (so we output 83 and add RAB to the table) |
CHAPTER 6
p. 870, 872
Printed: | put() several times |
Fixed: | add() |
p. 878
Printed: | N-character text string has N(N-1)/2 substrings |
Fixed: | N-character text string has N(N+1)/2 substrings |
p. 880
Printed: | substring.length() |
Fixed: | lrs.length() |
p. 889
Printed: | // Check local equilibrium at each vertex. |
Fixed: | // Check local equilibrium at vertex v. |
p. 890
Printed: | Figure: reference to the same Edge object |
Fixed: | Figure: reference to the same FlowEdge object |
p. 891
Printed: | Third figure: flow on edge 0->2 is 1 |
Fixed: | Third figure: flow on edge 0->2 should be 2 |
p. 897
Printed: | residualCapTo() |
Fixed: | residualCapacityTo() |