Errata_of_the_Instructor's_Manual.tex

\documentclass[a4paper, fleqn]{article}
\usepackage{clrscode}
\setlength\mathindent{0em}
\parskip = 7bp
\begin{document}
\begin{description}

\item[Page 4-12]
Line 3, it should be $\sum_{i = 0}^{\lg n - 1} \frac{n}{\lg n - i} =
\sum_{i = 1}^{\lg n} \frac{n}{i}$.




\item[Page 4-14, 4-15]
In solution to Problem 4-4 $h$, in the proof of $T(n) = \Omega(n
\lg n)$, the exact form of the inductive hypothesis $T(n) > cn \lg n +
dn$ has not been proved. The same mistake occurs in $i$ on page 4-15.




\item[Page 8-15]
Line 19 of Problem 8-3 $a$, change ``To sort the group with $m_i$
digits'' to ``To sort the group with $i$ digits''.




\item[Page 8-16]
Line 12, change ``\ldots less \textbf{that} the first letter of string
\texttt{y}'' to ``\ldots less \textbf{than} the first letter of string
\texttt{y}''.




\item[Page 9-14]
\begin{enumerate}
\item
In solution to Problem 9-1 \textbf{\textit{b}}, $O$-notation is
introduced to prove the $\Omega$-notation of the best asymptotic
worst-case running time. This is not rigorous.

Actually, the worst-case running time of $i$ extractions from a heap
with $n$ elements is $\Omega(\lg n) + \Omega(\lg(n-1)) + \cdots +
\Omega(\lg(n-i+1)) = \Omega(\lg(n! / (n-i)!))$, which can not be
simplified to $\Omega(i \lg n)$. Thus, total worst-case running time
is $\Omega(n + i \lg(n! / (n-i)!))$.

\item
Solution to Problem 9-2 \textbf{\textit{a}} is not rigorous
either. According to the definition, $x$ is the weighted median only
if $\sum_{x_i < x} w_i < 1/2$, but not $\sum_{x_i < x} w_i \leq
1/2$. Therefore, the first part of the proof should be changed to
\begin{eqnarray*}
\sum_{x_i < x} w_i
& = & \sum_{x_i < x} \frac{1}{n} \\
& = & \frac{1}{n} \cdot \sum_{x_i < x} 1 \\
& = & \frac{1}{n} \cdot |\{x_i : 1 \leq i \leq n \mbox{ and } x_i < x\}| \\
& = & \frac{1}{n} \cdot \left(\left\lfloor\frac{n+1}{2}\right\rfloor -
1\right) \\
& \leq & \frac{1}{n} \cdot \left(\frac{n+1}{2} - 1\right) \\
& = & \frac{1}{n} \cdot \left(\frac{n}{2} - \frac{1}{2}\right) \\
& = & \frac{1}{2} - \frac{1}{2n} \\
& < & \frac{1}{2}.
\end{eqnarray*}
\end{enumerate}




\item[Page 9-18]
Line 12 of solution to Problem 9-3 \textbf{\textit{a}}, change ``In
the initial call, $p = 1$'' to ``In the initial call, $p = 0$''.




\item[Page 12-14]
The solution to Exercise 12.4-1 is actually the solution to Exercise
12.4-2.




\item[Page 13-16]
Problem 13-1 \textbf{\textit{a}}, in either case when deleting a node,
since $y$ is spliced out, all ancestors of $y$ must be changed.




\item[Page 14-12]
Exercise 14.2-2, in case 2 of \proc{RB-Delete-Fixup}, we should add
$\id{bh}[p[x]] \gets \id{bh}[x] + 1$ or $\id{bh}[p[x]] \gets
\id{bh}[w]$ after line 10 in \proc{RB-Delete-Fixup}.




\item[Page 14-17]
In the first version of \proc{Josephus}$(n,m)$, the loop condition of
the \kw{while} loop should be \kw{while} $k > 1$.




\item[Page 16-15]
Line 8, change ``so that $X$ consists of elements in $B$ but not in
$A'$ or $A$'' to ``so that $X$ consists of element in $B'$ but not in
$A'$ or $A$''.

\item[Page 16-15]

The last paragraph is not correct. It is not guaranteed that there are
sufficient $y$ in $B-A'$ to be added to $A-B'$ so that $|C| = |A|$. As
a counter-example, let $(S,l)$ be a graphic matroid in which $S$ is a
set of edges of a complete graph having four vertices $a, b, c$ and
$d$. Suppose that $A = \{ab, bc, cd\}, A' = \{ac\}, B = \{ad, ac,
bd\}$ and $B' = \{bc, cd\}$. Following the proof in the manual, we
will have $X = B' - A - A' = \emptyset, B - A' = \{ad, bd\}$ and $A -
B' = \{ab\}$. Adding either of the two elements in $B - A'$ to $A -
B'$ yields a new set belonging to $l$, however, that new set is not a
maximal independent set in $l$. But adding both the two elements in $B
- A'$ to $A - B'$ will result in a cycle, that is, the resulted new
set does not belong to $l$. Therefore, the proof for the exchange
property of $(S,l')$ may not be correct.

The solution is to change this paragraph and the first paragraph on
page 16-16 to the two paragraphs below:

Applying the exchange property, we add such $y$ in $B-A'$ to $A-B'$,
maintaining that the set we get, say $C$, is in $l$. Then we keep
applying the exchange property, adding a new element in $A-C$ to $C$,
maintaining that $C$ is in $l$, until $|C|=|A|$. Once $|C|=|A|$, there
is some element $x \in A$ that we have not added into $C$. We know
this because the element $y$ that we first added into $C$ was not in
$A$, and so some element $x$ in $A$ must be left over. Also, $x \in
B'$ because all the elements in $A-B'$ are initially in $C$. Therefore
$x \in B'-A'$.

The set $C$ is maximal, because it has the same cardinality as $A$,
which is maximal, and $C \in l$. All the elements but one in $C$ are
also in $A$, while the exception is in $B-A'$, so $C$ contains no
elements in $A'$. Because we never added $x$ to $C$, we have that $C
\subseteq S - A' - \{x\} = S - (A' \cup \{x\})$. Therefore, $A' \cup
\{x\} \in l'$, which is what we needed to show.

\item[Page 22-23]

In the fourth last line of the second paragraph (the nonconstructive proof), $x \in V'' \cup V_C$ should be changed to $x \in V'' \cap V_C$.

\end{description}
\end{document}