# 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 + 1
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

p. 334

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

#### CHAPTER 3

p. 408, top figure

 Printed: 8 keys in left subtree (twice) Fixed: 6 keys in left subtree (twice)

#### CHAPTER 4

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

p. 660

 Printed: public Iterable pathTo(int v) Fixed: public Iterable pathTo(int v)

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)

#### 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.