アルゴリズムイントロダクション 第 3 版 総合版の日本語版の正誤表が見つからなかったのでとりあえず原著のエラーリスト ([Author Errata Page] (http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-3e.php)) から見つけたものをテキトウに訳しました．
エラーリストに載っている全ての項目を訳したものではなく，エラーリストに載っているもののうち，日本語版 (アルゴリズムイントロダクション 第 3 版 総合版 初版 2 刷) でも同様に間違えている部分が見つかったもののみです (見落としている可能性もあります)．
その他，エラーリストには載っていないけれども個人的に見つけた誤り (日本語版固有のものを含む) もあれば追加しています．
英語力が低いので訳はテキトウです．
分冊版は持っていないのでなんとかページ数を対応させてください．
【進捗】
p.1 〜 p.51 (第 1 章 〜 第 3 章の章末問題 3-3 まで)
p.54 〜 p.72 (第 4 章の練習問題 4.3-4 まで)
p.296 〜 p.330 (第 15 章の練習問題 15.4-1 まで)
エラーリストに載っているものと見つけたものを掲載．
p.51 〜 p.53 (第 3 章の章末問題 3-4 以降)
p.72 〜 p.295 (第 4 章の練習問題 4.3-4 以降と第 5 章 〜 第 14 章)
p.330 〜 p.638 (第 15 章の練習問題 14.4-2 以降と第 16 章 〜 第 26 章)
p.980 〜 p.1007 (付録 C 章)
エラーリストに載っているもののみ掲載．
それ以外のページ
まだ．
【エラーレベル】
- さほど重要じゃない誤植
- 技術，説明の小さな誤り
- 技術，説明のちょっと重要な誤り
- アルゴリズムの説明に関する重大な誤り，テキストに大きな変更を要する誤り
1 章 (計算におけるアルゴリズムの役割)
p.8, 7 行目 (エラーレベル 1)
【誤】すべてのの NP 完全問題
【正】すべての NP 完全問題
p.8, 22 行目 (エラーレベル 3)
「トラックの総走行距離が最小になるような配送順序を決める」というような巡回セールスマン問題は NP 完全ではなく NP 困難である．ただし，「トラックの総走行距離が k 以下になるような配送順序があるか？」というような問題であれば NP 完全である．p.911 の定理 34.14 「巡回セールスマン問題は NP 完全である」はコストを k 以下に抑える問題を指していると思われる．
p.10, 7 行目 (エラーレベル 1)
【誤】巨大に思えれるかもしれないが
【正】巨大に思われるかもしれないが
※ 「思えれる」が正しい日本語かどうか自信なし．
2 章 (さあ，始めよう)
p.27, 図 2.3 と説明文を除いて上から 4 行目 (エラーレベル 1)
【誤】時点ででループ不変式は
【正】時点でループ不変式は
p.32, 練習問題 2.3-4 (エラーレベル 2)
【誤】再帰版の挿入ソートの実行時間に対する漸化式を書け．
【正】再帰版の挿入ソートの最悪実行時間に対する漸化式を書け．
3 章 (関数の増加)
p.38, 下から 11 行目 (エラーレベル 1)
【誤】$\frac{1}{2} n^2 - 3n = \Theta (n^2)$ をであること
【正】$\frac{1}{2} n^2 - 3n = \Theta (n^2)$ であること
p.39, 下から 12 行目 (エラーレベル 1)
【誤】関数 $f(n)$ が $O(g(u))$ の要素であるとき
【正】関数 $f(n)$ が $O(g(n))$ の要素であるとき
p.39, 下から 3 行目 (エラーレベル 1)
【誤】漸近的上界であることをだけが主張であり
【正】漸近的上界であることだけが主張であり
p.42, 一番下の $\omega (g(n))$ の定義内 (エラーレベル 3)
【誤】すべての $n \geq n_0$ に対して $0 \leq f(n) < cg(n)$ を満たす
【正】すべての $n \geq n_0$ に対して $0 \leq cg(n) < f(n)$ を満たす
p.46, 4 行目 (エラーレベル 2)
「任意の実定数 $a \geq 0$ に対して関数 $n^a$ は単調増加であり．任意の実定数 $a \leq 0$ に対して関数 $n^a$ は単調減少である」
とあるが，これは $n > 0$ の場合に限る．
※ n が正整数ならば $n > 0$ なので常に成り立つ．
p.48, 1 行目 (エラーレベル 1)
【誤】$f(n)=\lg^k n$
【正】$f(n)=O(\lg^k n)$
p.49, 3 行目 (エラーレベル 1)
【誤】正ではない整数に対して対数は定義されない
【正】正ではない実数に対して対数は定義されない
p.51, 章末問題 3-3 a.
誤りではないかもしれないが，関数リストの中に $(\lg n)!$ というものが登場する．階乗は一般的に非負整数にのみ定義されるので，これは $\lceil \lg n \rceil !$ などとすべきであるように思える．
※ 実数，複素数へ階乗の概念を一般化した関数としてガンマ関数 $\Gamma (z) = \int_0^\infty t^{z-1} e^{-t} dt$ がある．自然数 $n$ について $\Gamma (n+1)=n!$ であり，実数 $x > 0$ について $\Gamma (x+1) = \sqrt{2 \pi x} {\left( \frac{x}{e} \right) }^x \left( 1 + \Theta \left( \frac{1}{x} \right) \right)$ が成り立つ．よって $(\lg n)!$ が $\Gamma (\lg n + 1)$ のことだと考えて，$(\lg n)! = \sqrt{2 \pi {\lg n}} {\left( \frac{\lg n}{e} \right)}^{\lg n} \left( 1 + \Theta \left( \frac{1}{\lg n} \right) \right)$ としてもよい．
4 章 (分割統治)
p.58, 図 4.3 と説明文を除いて上から 4 行目 (エラーレベル 1)
【誤】$n$ 日からなる期間では $\binom{n-1}{2} = \Theta (n^2)$ 個の部分配列を調べる必要があるから
【正】$n$ 日からなる期間では $\binom{n+1}{2} = \Theta (n^2)$ 個の部分配列を調べる必要があるから
※ $\binom{n+1}{2} = \frac{1}{2} n (n+1)$
p.58, 下から 1 行目 (エラーレベル 1)
【誤】求めた 3 つ部分配列の中から
【正】求めた 3 つの部分配列の中から
p.61, 「分割統治アルゴリズムの解析」内の 3 行目 (エラーレベル 1)
「すべての部分配列のサイズは整数である」とあるが，そりゃあそうである．$n/2$ が整数になるということを言いたかったのだと思われる．
p.62, 練習問題 4.1-5
誤りではないが，訳がわかりにくい．
$A[1 \dots j+1]$ の最大部分配列は以下のどちらか (和が大きい方) である．
- $A[1 \dots j]$ の最大部分配列
- $A[i \dots j+1]$ $(1 \leq i \leq j+1)$ の形の部分配列のうち，最も和が大きいもの (即ち，$A[1 \dots j+1], A[2 \dots j+1], \dots ,A[j+1]$ のうち最も和が大きいもの)
後者については $A[1 \dots j], A[2 \dots j], \dots ,A[j]$ のうち最も和が大きいものがわかっていれば，定数時間で決定できる．
p.69, 下から 11 行目 (エラーレベル 1)
【誤】正数 $m < n$
【正】正整数 $m < n$
p.72, 練習問題 4.3-8 (エラーレベル 3)
【誤】漸化式 $T(n) = 4T(n/2) + n^2$
【正】漸化式 $T(n) = 4T(n/2) + n$
p.82, 図 4.7 の説明文内 (エラーレベル 1)
【誤】高さが $\log_b a$ の完全 $a$ 分木
【正】高さが $\log_b n$ の完全 $a$ 分木
p.83, 下から 2 行目 (エラーレベル 2)
【誤】最後の繰返しが行われる値 $n/b^{j-1}$ が最小の値だから，このためには $n/b^{j-1}$ が十分に大きいと仮定すれば十分である．
【正】うまく訳せません (エラーリスト原文：This inequality holds for all but at most a constant number of terms with the smallest such values $n/b^{j–1}$, for which $a^j f(n/b^{j–1}) = O(1)$.)
※ 下のコメント欄も参照してください
p.87, 真ん中の数式の 2 行下 (エラーレベル 2)
【誤】キーは限界 $f(n_j) = O(n^{{\log_b a}-\epsilon})$ の証明である．
【正】キーは限界 $f(n_j) = O((n/b^j)^{{\log_b a}-\epsilon})$ の証明である．
p.90, 章末問題 4-5 a. (エラーレベル 2)
【誤】過半数のチップが故障しているならば
【正】少なくとも半分のチップが故障しているならば
p.93, 8 行目 (エラーレベル 2)
【誤】$i = 1,2,\dots,k$ に対して $a_i$ は正定数，
【正】$i = 1,2,\dots,k$ に対して $a_i$ は $\sum_{i=1}^k a_i \geq 1$ を満たす正定数，
※ 訳に自信ないのと Akra-Bazzi method で検索してもこのような条件をつけているものが見つかりませんでした (エラーリスト原文：for the condition on the $a_i$ coefficients of the Akra-Bazzi method, add the condition that the $a_i$ must sum to at least 1)
p.93, 10 行目 (エラーレベル 2)
【誤】$k \leq 1$ は整定数
【正】$k \geq 1$ は整定数
p.93, 下から 6 行目 (エラーレベル 2)
【誤】$\sum_{i=1}^k {a_i b_i^{-p}} = 1$
【正】$\sum_{i=1}^k {a_i b_i^p} = 1$
p.93, 下から 4 行目の数式 (エラーレベル 2)
【誤】$T(n) = \Theta\left(x^p\left(1+\int_1^x\frac{f(u)}{u^{p+1}}du\right)\right)$
【正】$T(x) = \Theta\left(x^p\left(1+\int_1^x\frac{f(u)}{u^{p+1}}du\right)\right)$
5 章 (確率的解析と乱択アルゴリズム)
p.105, 1 行目 (エラーレベル 2)
【誤】確率は $(n-(n+1)+1)/n!=0!/n!=1/n!$ である．
【正】確率は $(n-(n+1)+1)!/n!=0!/n!=1/n!$ である．
p.109, 8, 10, 11 行目の三箇所それぞれ (エラーレベル 2)
【誤】$\sum_{i=1}^k \sum_{j=i+1}^k$
【正】$\sum_{i=1}^{k-1} \sum_{j=i+1}^k$
p.113, 数式 5.11 (エラーレベル 3)
【誤】$\sum_{j=\lfloor (\lg n)/2 \rfloor + 1}^n \mathrm{Pr} \{ L_j \} \geq 1-O(1/n)$
【正】$\sum_{j=\lfloor (\lg n)/2 \rfloor}^n \mathrm{Pr} \{ L_j \} \geq 1-O(1/n)$
p.113, 10, 11, 12 行目のそれぞれ (エラーレベル 3)
【誤】$\sum_{j=0}^{\lfloor (\lg n)/2 \rfloor}$ と $\sum_{j=\lfloor (\lg n)/2 \rfloor +1}^n$
【正】$\sum_{j=0}^{\lfloor (\lg n)/2 \rfloor -1}$ と $\sum_{j=\lfloor (\lg n)/2 \rfloor}^n$
6 章 (ヒープソート)
p.136, 練習問題 6.5-5 (エラーレベル 3)
【誤】第 4 〜 6 行の while 文の各繰り返しの直前において，配列 A[1..A.heap-size] は，A[i] が A[PARENT(i)] より大きい可能性があることを除けば max ヒープ条件を満足する．
【正】第 4 〜 6 行の while 文の各繰り返しの最初において，もしこれらのノードが存在し部分配列 A[1..A.heap-size] が max ヒープ条件を満足するならば，A[i] が A[PARENT(i)] より大きい可能性があることを除けば， A[PARENT(i)] ≥ A[LEFT(i)] かつ A[PARENT(i)] ≥ A[RIGHT(i)] である．
※ ちょっと訳に自信なし (エラーリスト原文：At the start of each iteration of the while loop of lines 4–6, A[PARENT(i)] ≥ A[LEFT(i)] and A[PARENT(i)] ≥ A[RIGHT(i)], if these nodes exist, and the subarray A[1 .. A.heap-size] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)]).
7 章 (クイックソート)
p.140, 9 行目 (エラーレベル 2)
【誤】どの特定の入力も最悪の振る舞いを (常に) 引き起こすことはない．
【正】配列の要素が全て異なるときは，どの特定の入力も最悪の振る舞いを (常に) 引き起こすことはない (同じ要素があるような場合については，章末問題 7-2 を見よ)．
p.154, 章末問題 7-2 c. (エラーレベル 3)
【誤】手続き RANDOMIZED-QUICKSORT を PARTITION' を呼び出すように修正し，この新しい手続きを RANDOMIZED-QUICKSORT' と名づける．手続き QUICKSORT を修正して手続き QUICKSORT'(p, r) を作れ．QUICKSORT' は RANDOMIZED-QUICKSORT' を呼び出し，同じ値の要素だけから構成されていることが知られていない分割の上にだけ再帰する．
【正】手続き RANDOMIZED-PARTITION を PARTITION' を呼び出すように修正し，この新しい手続きを RANDOMIZED-PARTITION' と名づける．手続き QUICKSORT を修正して手続き QUICKSORT'(A, p, r) を作れ．QUICKSORT' は RANDOMIZED-PARTITION' を呼び出し，同じ値の要素だけから構成されていることが知られていない分割の上にだけ再帰する．
8 章 (線形時間ソート)
p.163, 下から 10 行目 (エラーレベル 2)
【誤】$k=2^r-1$
【正】$k=2^r$
p.163, 下から 9 行目 (エラーレベル 2)
【誤】$k=2^r-1=255$
【正】$k=2^r=256$
p.164, 練習問題 8.3-2 (エラーレベル 2)
【誤】任意のソーティングアルゴリズムを安定なものに修正する
【正】任意の比較ソートを安定なものに修正する
9 章 (中央値と順序統計量)
10 章 (基本データ構造)
p.193, 真ん中 (エラーレベル 3)
【誤】$Q.head = Q.tail + 1$ ならばキューは一杯であり，
【正】$Q.head = Q.tail + 1$，もしくは $Q.head = 1$ かつ $Q.tail = Q.length$ ならばキューは一杯であり，
p.200, 下から 3 行目 (エラーレベル 2)
【誤】オブジェクトの割付け，解放手続きを実現できる．
【正】オブジェクトの解放，割付け手続きを実現できる．
11 章 (ハッシュ表)
p.228, 上から 3 行目 (エラーレベル 2)
【誤】が成立する．ここで，式 (C.25) を用いると
【正】が成立する．もちろん $i>m$ を満たすような任意の $i$ に対しては $\mathrm{Pr} \{ X \geq i \} = 0$ である．ここで，式 (C.25) を用いると
p.228, 上から 4, 5 行目 (エラーレベル 2)
【誤】
\begin{align}
E[X] &= \sum_{i=1}^\infty {\mathrm{Pr} \{ X \geq i \}} \\
&\leq \sum_{i=1}^\infty \alpha^{i-1}
\end{align}
【正】
\begin{align}
E[X] &= \sum_{i=1}^\infty {\mathrm{Pr} \{ X \geq i \}} \\
&= \sum_{i=1}^m {\mathrm{Pr} \{ X \geq i \}} + \sum_{i>m} {\mathrm{Pr} \{ X \geq i \}} \\
&\leq \sum_{i=1}^\infty \alpha^{i-1} + 0
\end{align}
p.230, 図 11.6 内 (エラーレベル 2)
ハッシュ表 $S_7$ 中のキー 40 の格納場所を 7 から 3 に修正．
12 章 (2 分探索木)
p.247, 下から 9 行目 (エラーレベル 2)
【誤】$y$ が $z$ の左の子でなければ
【正】$y$ が $z$ の右の子でなければ
13 章 (2 色木)
14 章 (データ構造の補強)
p.286, 11 行目 (エラーレベル 4)
【誤】第 1 段階ではある 1 個の節点 $y$ を木から削除するか，木の中を上方に移す．そこで，部分木のサイズを更新するために，節点 $y$ (の元々の位置) から根までの単純道を辿りながら，この道上の各節点の size 属性をそれぞれ 1 減らす．
【正】第 1 段階ではある 1 個の節点 $z$ を木から削除し，このとき最大 2 つの他の節点が移動する (節点 $y$ と $x$, 図 12.4)．そこで，部分木のサイズを更新するために，移動した最小の節点 (の元々の位置) から根までの単純道を辿りながら，この道上の各節点の size 属性をそれぞれ 1 減らす．
p.288, 下から 5 行目 (エラーレベル 4)
【誤】第 1 段階で木が変化するのは，削除された節点を木から除去するときに発生する．この節点が 2 つの子を持っていたとすると，この節点の位置にこの節点の次節点が移動する．これらの変化は木を局所的に変更するだけだから，対応する $f$ の更新の伝搬にかかる時間は高々 $O(\lg n)$ である．
【正】第 1 段階で木が変化するのは，節点が削除されるときであり，そのとき最大 2 つの他の節点が木の中を移動する．これらの変化は最小の変化をした節点から根までの単純道に沿って木を局所的に変更するだけだから，対応する $f$ の更新の伝搬にかかる時間は高々 $O(\lg n)$ である．
15 章 (動的計画法)
p.209, 下から 8 行目 (エラーレベル 1)
【誤】維持してしておくことがある．
【正】維持しておくことがある．
P.301, 下から 11 行目 (エラーレベル 1)
【誤】$r_i + r_{n-i}$ を最大化することに対応する．
【正】$r_i + r_{n-i}$ に対応する．
p.307, EXTENDED-BOTTOM-UP-CUT-ROD の 1 行目 (エラーレベル 1)
【誤】s[0..n]
【正】s[1..n]
p.308, 上部の r[i], s[i] の表 (エラーレベル 1)
s[0] の中身を 0 ではなくて空白に修正．
p.313, 下から 14 行目 (エラーレベル 2)
【誤】表 $m$ の主対角線より真に上の部分
【正】表 $m$ の主対角線上と，それより上の部分
p.319, 8 行目 (エラーレベル 1)
【誤】$r$ から $t$ への最長単純道と発見する
【正】$r$ から $t$ への最長単純道を発見する
p.327, 4 行目 (エラーレベル 1)
【誤】「部分部分問題」を共有する
【正】「部分部分問題」を共有するかもしれない
p.327, 下から 15 行目 (エラーレベル 1)
【誤】問題に関するある条件に基づいてある部分問題を除外できなかった．
【正】問題に関する条件に基づいて部分問題を除外できるということはなかった．
p.337, 章末問題 15-3 (エラーレベル 3)
【誤】この問題は制約をつけなければ NP 完全であり，
【正】この問題は制約をつけなければ NP 困難であり，
p.342, 章末問題 15-10 (エラーレベル 3)
【誤】前年と同じ投資先に資金を再投資するならば，手数料は $f_1$ ドルかかり，投資先を変更するならば，手数料は $f_2$ ドルかかる．
【正】各年の終わりに，あなたは前年と同じ投資先に資金を再投資するか，他の投資対象に移す (即ち，既に投資している投資先間で資金を移したり，新しい投資先にお金を移す) か選ぶことができる．前年と同じ投資先に資金を再投資するならば，手数料は $f_1$ ドルかかり，投資先を変更するならば，手数料は $f_2$ ドルかかる．ただし $f_2 > f_1$ とする．
16 章 (貪欲アルゴリズム)
p.372, 章末問題 16-3 e. (エラーレベル 3)
【誤】(c) と (e) の結果が矛盾しない
【正】(c) と (d) の結果が矛盾しない
p.374, 章末問題 16-5 b. (エラーレベル 2)
【誤】最遠要求優先戦略が部分構造最適性を持つことを示せ．
【正】オフライン版のキャッシュ問題が部分構造最適性を持つことを示せ．
17 章 (ならし解析)
p.385, 下から 5 行目 (エラーレベル 2)
【誤】(1 つもアイテムを含まない)
【正】(1 つも枠を持たない)
18 章 (B 木)
p.411, B-TREE-SPLIT-CHILD の下の文の 1 行目 (エラーレベル 2)
【誤】$x$ は分割が実行されている節点 (分割される節点の親)
【正】$x$ は分割が実行されている節点の親 (分割される節点の親)
p.418, 章末問題 18-1 (エラーレベル 2)
【誤】スタックポインタを 1 減らし，適切なページをディスクから読み込み，スタックの先頭を返す．
【正】スタックの先頭を覚えておき，スタックポインタを 1 減らし，適切なページをディスクから読み込み，覚えておいた値を返す．
19 章 (フィボナッチヒープ)
p.439, 練習問題 19.4-2 (エラーレベル 2)
【誤】$D(n) = O (\lg n)$ となる $k$ の値を議論せよ．
【正】$D(n) = O (\lg n)$ となり，ならし計算時間が変化しないような $k$ の値を議論せよ．
※ エラーリスト原文： For what values of k is $D(n) = O(\lg n)$ and the asymptotic amortized operation costs remain unchanged?
20 章 (van Emde Boas 木)
p.458, 3 行目 (エラーレベル 2)
【誤】空の木を $O(u)$ 時間で生成する
【正】空の木を $\Theta(u)$ 時間で生成する
p.460, 14 行目 (エラーレベル 2)
【誤】第 7 行の判定結果にしたがって
【正】第 8 行の判定結果にしたがって
p.464, 練習問題 20.3-6 (エラーレベル 2)
【誤】$O(u)$ 時間かかる
【正】$\Theta (u)$ 時間かかる
p.466, 章末問題 20-1 f. (エラーレベル 4)
章末問題 20-1 の f. は誤っている．つまり，RS-vEB 木の領域量は $\Theta(n \lg n)$ となりうる．
21 章 (互いに素な集合族のためのデータ構造)
p.475, 下から 2 行目 (エラーレベル 2)
【誤】$x$ とその子孫の葉を結ぶ最長の単純道
【正】子孫の葉から $x$ までの最長の単純道
p.478, 17 行目 (エラーレベル 1)
【誤】$A_0(k)$ の定義と上記の補題から
【正】$A_0(j)$ の定義と上記の補題から
p.482, 下から 5 行目 (エラーレベル 2)
【誤】ポテンシャルの増分の和である．
【正】ポテンシャルの変化の和である．
22 章 (基本的グラフアルゴリズム)
p.501, 練習問題 22.2-3 (エラーレベル 3)
【誤】第 5 行と第 14 行を削除しても
【正】第 18 行を削除しても
p.508, 練習問題 22.3-4 (エラーレベル 3)
【誤】第 3 行を削除しても
【正】第 8 行を削除しても
23 章 (最小全域木)
p.532, MST-REDUCE 内 (エラーレベル 3)
擬似コード MST-REDUCE 内の 15 〜 21 行 は $u \neq v$ のときだけ実行するようにしなければならない．
そこで，まず 14 行目の後に新しく [15 if $u \neq v$] を挿入し，もともとの 15 〜 23 行は全て行番号を 1 増やして 16 〜 24 とする．さらに，その新しい 16 〜 22 行をインデントする．
p.533, 章末問題 23-4 (エラーレベル 2)
【誤】あるいは $T$ が最小全域木でないことを証明せよ．
【正】あるいは $T$ が必ずしも最小全域木でないことを証明せよ．
24 章 (単一始点最短路問題)
p.544, 系 24.3 (エラーレベル 2)
系 24.3 から「$s$ から到達可能な負経路を $G$ が含まないと仮定する」の文を削除する．
その証明の後ろに，「この系では $s$ から到達可能な負経路を $G$ が含んでいてもよい (ただし補題 24.2 ではダメ)」という文を追加する．
25 章 (全点対最短路)
26 章 (最大フロー)
p.598, 補題 26.1 の証明 (エラーレベル 4)
補題 26.1 の証明を全面的に修正
http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf
p.602, 7 行目 (エラーレベル 2)
【誤】すべての頂点対 $x, y \in V$ に対して
【正】すべての頂点対 $x, y \in S$ に対して
p.604, FORD-FULKERSON 内 (エラーレベル 1)
【誤】6 if $(u, v) \in E$
【誤】6 if $(u, v) \in G.E$
p.607, 15 行目 (エラーレベル 2)
【誤】$G_f$ 上の $s$ から $u$ への最短路の最後の辺は $(v, u)$ である．
【正】最後の辺として $(v, u)$ を持つ $G_f$ 上の $s$ から $u$ への最短路に沿ってフローは増加する．
p.609, 練習問題 26.2-12 (エラーレベル 3)
【誤】フローネットワーク $G$ が与えられており
【正】整数容量を持つフローネットワーク $G$ が与えられており
p.609, 練習問題 26.2-12 (エラーレベル 2)
$|f| \geq 0$ という条件を追加する．
p.621, 7 行目 (エラーレベル 2)
【誤】つぎに $u$ から $v$ へのプッシュが起こるためには，
【正】つぎに $u$ から $v$ への飽和プッシュが起こるためには，
27 章以降
そのうちやります．
付録 C 章
p.980, 章タイトル
【誤】COUNTING AND PROBABILTY
【正】COUNTING AND PROBABILITY
p.1002, 14 行目 (エラーレベル 2)
【誤】$< b(k;n,p) \sum_{i=1}^\infty x^i$
【正】$< b(k;n,p) \sum_{i=0}^\infty x^i$
p.1005, 練習問題 C.5-5 (エラーレベル 3)
【誤】
定理 C.8 の前提から
\mathrm{Pr} \left\{ { \mu - X \geq r } \right\} \leq { \left( \frac{(n - \mu)e}{r} \right) }^r
を導け．同様に系 C.9 の前提から
\mathrm{Pr} \left\{ { np - X \geq r } \right\} \leq { \left( \frac{nqe}{r} \right) }^r
を導け．
【正】
定理 C.8 から，$r > n - \mu$ について
\mathrm{Pr} \left\{ { \mu - X \geq r } \right\} \leq { \left( \frac{(n - \mu)e}{r} \right) }^r
を導け．同様に系 C.9 から，$r > n - np$ について
\mathrm{Pr} \left\{ { np - X \geq r } \right\} \leq { \left( \frac{nqe}{r} \right) }^r
を導け．
参考文献
p.1021, [44]
【誤】A general method for solving divideand-conquer recurrences
【正】A general method for solving divide-and-conquer recurrences