Errata

- on page 113, the sentence "The input to Binary Search is a indexed collection A of elements". This should read "The input to Binary Search is a sorted indexed collection A of elements"
- in the discussion of red-black trees on page 131-133, the explanation of the example unclear or the diagram is incorrect. On page 133, the text reads"In Step 2 the colors of the nodes are updated to ensure condition 4 of red-black trees." However, condition 4 is violated fro node 17 which has one red and one black child node. Then "In Step 3 the tree is rotated to the right to ensure condition 5 of red-black trees." But the diagram shown in Step 2 doesn't seem to violate the condition that every simple path from a node to one of its descendant leaf nodes contains the same number of black nodes. [My guess is that the diagram in Step 2 is the culprit, that the node labeled 17 was meant to be colored black.]

Note from the Author or Editor:
on page 113, the sentence "The input to BINARY SEARCH is an indexed collection A of elements" should read "The input to BINARY SEARCH is an ordered, indexed collection A of elements"

Figure 5-11 shows the resulting steps when inserting the key 14 into the red-black tree. You can confirm these steps using existing animations of red-black tree algorithms. One such animation can be found at http://gauss.ececs.uc.edu/RedBlack/redblack.html and this shows what happens within the fixAfterInsertion method of the algs.model.tree.BalancedTree class.

The mathematical representations of ?capacity constraint(0≤f(u,v)≤c(u,v))? and ?skew symmetry(f(u,v)=-f(v,u))? are conflict each other.

Note from the Author or Editor:
While preparing the Japanese translation of "Algorithms in a Nutshell" we ran into the same issue. In the end, we decided to
rewrite the text associated with Skew Symmetry as follows:

Each edge (u,v) has a defined flow f(u,v). For mathematical
convenience, one can define for this edge that f(v,u) = -f(u,v).
Doing so enables network flow algorithms to add flows together
when determining the net flow from vertex u to v.

In network graphs, each edge is directed. Using Figure 8-2 as an
example (p. 228) up to 10 units can "flow" from the source vertex
s and vertex v1. In this instance 5 units are actually flowing from
s to v1. Now how do we represent this information?

We start on p. 228 by saying "Each edge (u,v) has a flow f(v,u)
that defines the number of units of the commodity that flows from
u to v. An edge also has a capacity c(u,v) that constrains the
maximum number of units that can flow over that edge."

So we try to associate values with EDGES. Thus:

edge(s,v1).flow = 5
edge(s,v1).capacity = 10

This is a bit unwieldy to write in practice, so it is conveniently
shortened to be:

f(s,v1)=5
c(s,v1)=10

but the assumption is always that there is a specific edge under
consideration. Internally within the algorithm (see structures in
Figure 8-4 on p. 233) you will see that EdgeInfo contains both
"capacity" and "flow" attributes.

For this edge from s to v1, we can conveniently state that there
are "-5" units flowing from v1 back to s.

The mistake in the text as written is that it becomes confusing to
think of f(u,v) having a negative value, especially when
considering the capacity constraint earlier. The trick is that this
is just a convention and applies only to a single edge.

In Figure 8-2 you can see that

edge(v2,v4).flow=2 meaning 2 units are flowing from v2 to v4
edge(v4,v2).flow=0 meaning 0 units are flowing from v4 to v2

However, if the network graph began having 3 units flow from
v4 to v2 (allowed by the capacity) you would see the following:

edge(v2,v4).flow=2
edge(v4,v2).flow=3

Given the "edge from v2 to v4" we can state that f(v2,v4)=2 and
f(v4,v2)=-2.

Given the "edge from v4 to v2" we can state that f(v4,v2)=3 and
f(v2,v4)=-3.

The elapsed time of op1 at the input size of 100,000 on the implementation A is reduced compared to one at the input size of 1,000.

Note from the Author or Editor:
The intent of this made-up example is to show how different implementations of the same data structure can lead to wildly different performance.

It would be distinctly unlikely for 100,000 operations on A to take 0.0016 ms where 1,000 operations on A required 0.008 ms.

This should have been "0.016" ms for 100,000 operations, resulting in a total of 4,100 ms for the row of A on 100,000.

The point is the same, however, showing how orders of magnitude difference can occur simply by an ill-advised selection of data structure.

the k=8th largest element
should be
the k=8th (smallest) element

Note from the Author or Editor:
There can be only one largest element (by definition!). Our use of the phrase "8th largest element" was short-hand to refer to the 8th element if all elements were arranged in order increasing from smallest to largest. In the future, we will avoid this phrase.

The square brackets should be parentheses and helper function sub1 is not defined in Example A-7 or the code repository. Thus the largeAdd function in Example A-8 should be as follows.

(define (largeAdd probSize)

(let loop ((i probSize)

(total 0))

(if (= i 0)

total

(loop (- i 1) (+ i total)))))

Note from the Author or Editor:
The Scheme interpreter we used was "MzScheme version 207, Copyright (c) 2004 PLT Scheme, Inc."

In MzScheme, the 'sub1' function is already defined (and it works as expected) and you can use square brackets (i.e. []) interchangeably with parentheses in order to enhance the visual representation of Scheme code.

Diagram of kd-tree omits labels on lines V, H.

Note from the Author or Editor:
Within Figure 9-19(a) you can see little vertical and horizontal lines within the circles representing the nodes of the kd-tree; these lines designate whether a node is a vertical partition or a horizontal partition.