#
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

=7*n*-2

with
=7*n*-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

*v*_{i}<*v*_{j}

with
*v*_{i} > *v*_{j}

###
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**
*v*_{1}, ... , *v*_{n}
**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(*n*^{2})

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