Errata for Algorithms, 4th Edition, Second Printing (January 2012)


CHAPTER 1

p. 30, 31, 206 StdRandom API

Printed: initialize(seed)
Fixed: setSeed(seed)
Reported by Peter Drake, 27-Jan-12.

p. 42, top figure

Printed: StdDraw.line(x0, y0, x1, y1)
Fixed: StdDraw.line(x1, y1, x2, y2)
Reported by Pieter Audenaert, 12-Mar-12.

p. 136-137

Printed: public void push (String item) and public String pop()
Fixed: public void push (Item item) and public Item pop()
Reported by Marcel Palomino, 10-Jul-12.

p. 145, bottom figure

Printed: Node last = new Node()
Fixed: last = new Node()
Reported by Katherine Pogrebniak and Sara Rubin, 16-Feb-12.

p. 171, Exercise 1.3.45

Printed: stack does not overflow
Fixed: stack does not underflow
Reported by Alexander Kanavin, 27-Aug-12.

p. 175

Printed: StdOut.println(count + " triples " + time)
Fixed: StdOut.println(count + " triples " + time + " seconds")
Reported by Dhiru Kholia, 25-Feb-12.

p. 211, Exercise 1.4.23

Printed: differ by more than
Fixed: differ by less than
Reported by Michael Laszlo, 23-Feb-12.

p. 227

Printed: number of array accesses for the union() operation for the pair 0-i is exactly 2i + 2
Fixed: number of array accesses for the union() operation for the pair 0-i is exactly 2i + 3
Reported by Wu Xudong, 22-Apr-12.

p. 237, Problem 1.5.12

Printed: by adding a loop to union() that links every site on the paths from p and q to the roots of their trees to the root of the new tree
Fixed: by adding a loop to find() that links every site on the path from p to the root directly to the root
Reported by Peter Drake, 27-Jan-12.


CHAPTER 2

p. 248

Printed: the number of array accesses is a linear function of the array size
Fixed: the number of exchanges is a linear function of the array size
Reported by Katherine Pogrebniak, 17-Mar-12.

p. 279, Proposition H

Printed: Number of passes through the array is precisely floor(lg N).
Fixed: Number of passes through the array is precisely ceil(lg N). Delete text referring to 2^n <= N < 2^n+1.
Reported by Ashwin Nanjappa, 10-Jan-11.

p. 325

Printed: top right heap has M and L highlighted in light red
Fixed: E should also be highlighted
Reported by Ashwin Nanjappa, 16-Jan-12.

p. 333

Printed: public Item min()
Fixed: public Key min()
Reported by Natalie Weires, 11-Jan-12.

p. 334

Printed: Item item
Fixed: Key key
Reported by Abhijith Madhav, 20-Feb-12.

p. 334

Printed: exch(k, N--);
Fixed: IndexMinPQ.java
Reported by Michael Laszlo, 22-Feb-12.


CHAPTER 3

No errata reported.


CHAPTER 4

p. 408, top figure

Printed: 8 keys in left subtree(twice)
Fixed: 6 keys in left subtree (twice)
Reported by Mohammad Zia, 08-May-12.

p. 544

Printed: more tinyG.txt
Fixed: java Graph tinyG.txt
Reported by Wu Xudong, 09-May-12.

p. 585

Printed: point from vertex consumes organisms of the specifies indicated by the point to vertex
Fixed: point to vertex consumes organisms of the specifies indicated by the point from vertex
Reported by Ashwin Nanjappa, 27-Feb-12.

p. 592

Printed: KosarajuSharirCC
Fixed: KosarajuSharirSCC
Reported by Noah Apthorpe, 16-Jan-12.

p. 625, Proposition N

Printed: up to E find() and V union() operations
Fixed: up to E connected() and V union() operations
Reported by David Durst, 23-Jan-12.

p. 653

Printed: distTo[3] = 0.97 and edgeTo[3] = 3->7 0.37
Fixed: distTo[3] = 0.99 and edgeTo[3] = 3->7 0.39
Reported by Abhijith Madhav, 22-Feb-12.

p. 660

Printed: public Iterable<Edge> pathTo(int v)
Fixed: public Iterable<DirectedEdge> pathTo(int v)
Reported by Abhijith Madhav, 08-Mar-12.

p. 673

Printed: q.enqueue(w)
Fixed: queue.enqueue(w)
Reported by Natalie Weires, 11-Jan-12.

p. 674

Printed: relax(v) and private void relax(int v)
Fixed: relax(G, v) and private void relax(EdgeWeightedDigraph G, int v)
Reported by Abhijith Madhav, 28-Mar-12.


CHAPTER 5

p. 705, Proposition A

Printed: Key-indexed counting uses 8N + 3R + 1 array accesses
Fixed: Key-indexed counting uses 11N + 4R + 1 array accesses
Reported by Tsuyoshi Miyake, 06-Mar-12.

p. 749, Proposition K

Printed: A search hit or an insertion in a TST uses a character compare for each character in the search key.
Fixed: In addition to the ~ lg N compares, a search hit or an insertion ...
Reported by Natalie Weires, 10-Jan-11.

p. 764

Printed: M not initialized
Fixed: M = pat.length()
Reported by Natalie Weires, 11-Jan-12.

p. 833, Proposition U

Printed: (s1, r1)
Fixed: (s1, f1)
Reported by Ashwin Nanjappa, 12-Mar-11.

p. 833, Proposition U

Printed: set of n-1 symbols
Fixed: set of r-1 symbols
Reported by Ashwin Nanjappa, 12-Mar-11.


CHAPTER 6

p. 896

Printed: return cap - flow;
Fixed: return capacity - flow;
Reported by Noah Apthorpe, 18-Jan-12.