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.