Errata and Clarifications

Chapter 1, page 10, fourth itemized paragraph

Contributor(s): Mingzhou Song

Replace

A[currentMax]
with
A[i]

Chapter 1, page 12, last paragraph

Contributor(s): Peter Duffy

Replace

=7n-2
with
=7n-4

Chapter 1, page 50, Exercise C-1.5

Contributor(s): Pranava K. Jha, Ed Hong, Ivy Lo, Mingzhou Song, Marc Kirschenbaum, Kaare Fiedler Christiansen

Replace

n=1
with
n=0

Chapter 1, page 50, Exercise C-1.6

Contributor(s): Pranava K. Jha, Marc Kirschenbaum, Joe O'Rourke

Replace

n=1
with
n=0

Chapter 2, page 69, Method insertBefore

Contributor(s): Tara Whalen, Aron Klein, Kaare Fiedler Christiansen

Remove

an error occurs if p is the first position

Chapter 2, page 80, sixth line of second paragraph

Contributor(s): Kaare Fiedler Christiansen

Replace while with for.

Chapter 2, page 84, second line of first paragraph

Contributor(s): Jeffrey Shallit

Replace

Section 2.3.1
with
Section 2.3

Chapter 2, page 129, caption of Code Fragment 2.58

Contributor(s): Louise Skouboe

In the last line, replace

at at
with
at a

Chapter 3, page 150, Step 1 of the removal algorithm

Contributor(s): Mark Winands

Note that in Step 1, we could have selected y as the right-most internal node in the left subtree of w.

Chapter 3, page 158, first paragraph

Contributor(s): Sharat Chandran, Frederick Beaupre, Troy Vasiga, David Mount

Replace

let x be a child of y with larger height.
with
let x be the child of y defined as follows: if one of the chidren of y is taller than the other, let x be the taller child of y; else (both children of y have the same height), let x be the child of y on the same side as y (that is, if y is a left child, let x be the left child of y, else let x be the right child of y).
Remove the sentence
The choice of x may not be unique, since the subtrees of y may have the same height.

Chapter 3, page 190, line 3 of first paragraph

Contributor(s): Mark Winands

Replace

Section 3.1.2
with
Section 3.1.5

Chapter 3, page 213, Exercise R-3.14, paragraph c

Contributor(s): Kaare Fiedler Christiansen

Replace

an unique
with
a unique

Chapter 3, page 215, Hint for Problem C-3.24

Contributor(s): Gwendoline Chien

Replace

smallest j
with
largest j
Also, the summation should be from i=0 to j-1.

Chapter 5, page 260, line 3 of third paragraph

Contributor(s): Penny Anderson

Replace

vi<vj
with
vi > vj

Chapter 5, page 280,

Contributor(s): Erik Meineche Schmidt, Mikkel Nygaard

Throughout the page, replace

total weight exactly w
and similar expressions with
total weight at most w

Chapter 6, page 305, Algoritm 6.7

Contributor(s): Mingzhou Song

Add the line

label v as explored
as the first line.

Chapter 6, page 311, Algorithm 6.10

Contributor(s): Vicki Allan, Gerth S. Brodal

In the while loop condition and the assignment statement of the last line, change s to v.

Chapter 6, page 318, caption of Figure 6.15

Contributor(s): Mark Ture, Vicki Allan, Kaare Fiedler Christiansen

In the last line, remove

, and (SFO,LAX) is a cross edge

Chapter 6, page 326, Algoritm 6.19

Contributor(s): Mingzhou Song, Gerth S. Brodal

Add an arrow above G in G.opposite. Replace the second to last line with:

if i>n then
            return v1, ... , vn
else

Chapter 7, page 343, Algorithm 7.2

Contributor(s): Mingzhou Song, Louise Skouboe

Remove arrow above G in second statement.

Chapter 7, page 346, caption of Figure 7.5

Contributor(s): Nikos Triandopoulos

Replace

Theorem 7.1
with
Lemma 7.1

Chapter 7, page 360, first line of last paragraph

Contributor(s): Mingzhou Song

Replace

description the algorithms
with
description of the algorithms

Chapter 7, page 378, Exercise C-7.9

Contributor(s): Nikos Triandopoulos

Change

for each flight f ∈ A
to
for each flight f ∈ F

Chapter 8, page 388, Figure 8.6

Contributor(s): Vicki Allan

Replace the figure with this one.

Chapter 8, page 397, Figure 8.6

Contributor(s): Vicki Allan

Step 2 should say that we compute a maximum flow for H.

Chapter 9, page 421, Second paragraph

Contributor(s): Helmar Burkhart

Replace

Thus, in the worst case, ..., time
with
Note that, when m = n/2, this algorithm has quadratic running time O(n2)

Chapter 9, page 437, Algorithm 9.15

Contributor(s): Troy Vasiga

Replace statement

i ← start(v)
with
i ← start(w)

Chapter 10, page 457, Algorithm 10.3

Contributor(s): Derek Corneil

In the last statement, replace

EuclidBinaryGCD(|a-b|/2, b)
with:
EuclidBinaryGCD(|a-b|/2, min(a,b))

Chapter 10, page 498, line 2 of third paragraph

Contributor(s): Eugene Luks

Value m should be defined to be [(log p)/3].

Chapter 10, page 500, Code Fragment 10.17

Contributor(s): Eugene Luks

The static variable ENTRYSIZE should be set to 10, not 15.