Errata for

Models of Computation: Exploring the Power of Computing

by

John E. Savage

Original Publisher: Addison-Wesley, 1998.

January 6, 2004

This page is located at www.modelsofcomputation.org/errata.html.

Details on the book can be found at http://www.modelsofcomputation.org

These pages contain the important errors in the book that exist in the first printing of the book. Due to an error on the part of the publisher Addison-Wesley, only half of these errors were corrected in the second printing. By agreement with the author, all errors should have been corrected in the third printing. When they were not corrected, Addison-Wesley returned all the rights to the book to the author. All errors reported below have been corrected in the electronic version of the book. Minor errors are not reported. They include such things as spelling mistakes, arrowheads that have the wrong shape or text that is in the wrong font.

PREFACE    
Page
Line/Fig.
Comments (LaTex notation used)
viii
10
Change "four" to "three" and "2-5" to "2-7"
 
30
In this sentence, change 6 to 8 and move the sentence to line 39
 
30
Insert "Finally, Part II contains Chapters 6 and 7 which introduce algebraic and combinatorial circuits and parallel machine models, respectively."
 
31
Delete "introduces ... It" and move sentence after line 35. 
     
CHAPTER 1    
Page
Line/Fig.
Comments (LaTex notation used)
9
1
Insert as first sentence "An {\bf alphabet} is a finite set with at least two elements."
 
26
Change "empty letter" to "empty string".
 
-8
Change "(red,1)" to "(green,1)".
10
Sect. 1.2.5
11, 12, 13
 
Replace "range" by "codomain".
13
-6,-7
Put | | around x on line -7 and around f(x) and g(x) on line -6.
15
-2
Add "other than $\epsilon" after "strings" (twice) -
16
-10
Delete "and output".
25
-6
Replace n^2/24 by n^2/16.
26
24
Replace "inputs" with "outputs".
 
-14
Replace n^3 by n^6.
31
12
Change {0,1} to {a,b,c,d}
     
CHAPTER 2    
40
3,4
Change "range" to "codomain".
43
-10
Change x_1^1 x_2^0 x_3^1 = 1 to x_1^1 \vee x_2^0 \vee x_3^1 = 0.
 
-1
Change $y_1$ to $f$ 
51
-1
Change n = 8 to n = 3.
52
1
Change (1,0) to (0,1) twice.
56
22
61
-10
Change font of |u| to roman bold.
62
13, 14
Delete | |.
65
2
Delete Fig.
67, 70, 71, 72
Change M_{int}(n) to M_{int}(n,c)
67
4
Insert "O(3^{\log_2 n})" after =
68
4
Add \pi_L^{(n)} before f_mult
 
7
After s. add "and $\pi_L^{(n)}$ is the projection operator defined on page 50."
69
15
Change "right" to "left".
 
23,27
Replace "continuous" by "twice continuously differentiable".
 
24
Add "slope of the" before "tangent".
 
25
Change "concave" to "convex".
71
17
Change second > to = and third to >=
72
-5
Change second n to n+1
73
3
Change f(x) to f(w)
74
11
Delete "of an n-tuple"
75
5, 15
Replace \log_2 n by \log_2 (n+1) twice on line 5 and once on line 15
76
15
The above error on page 75 introduces small errors on lines 15, 16, 23, 26, 27, and 31-34. Click here to see the corrections.
 
17
Add "even" at the end of the line.
 
26,27
Change the first two subscripts on the e's to 0 and 1.
78
20
Change "Each vertex has fan-in 2, no" to "The root has two descendants as does every other vertex except for leaves which have none. No"
79
2
Replace -/y by -1/y
 
17
Replace (d+1)N(d) by N(d+1)
 
22
Delete the superscript (n)
80
4,8,10
Add 1 to \lceil \log_2 n \rceil
 
8
Change 2^{n-1} to 2^n -1, 3 2^{n-1} to 2^{n+1}, and -1 on the right.
 
9
Change n+1 to n.
83
2
Change upper limit on second integral from n+1 to n
 
8
Add "(each vertex except a leaf has two descendants)" after "binary tree".
 
Caption to 2.24
Change "depth two and b) depth 4" to "depth one and b) depth 3"
85
3
Replace the statement of Prob. 2.12 b) by "Show that the size and depth of a dual-rail logic circuit for a function $f: {\cal B}^{n} \mapsto {\cal B}$ are at most twice the circuit size (plus the NOTs for the inputs) and at most one more than the circuit depth of $f$ over the basis \{{\sc and}, {\sc or}, {\sc not}\}, respectively."
86
24
Change n log n to n log^2 n
88
4
Change "B^n -> B^n" to B^n -> B^{kn}"
 
7
Add "0 < q < 2 ^k < \log_2 n" after comma
     
CHAPTER 3    
94
9, 10
Change \delta to \lambda
95
20
Change "smaller" to "larger"
 
-11
Change C_{\Omega} to D_{\Omega}
96
-14
Change superscript (T) to (n)
 
-7
Delete first sentence
98
6
Replace \delta_1, \lambda_1, \delta_1, \lambda_1 with "C_{\Omega}(\delta, \lambda) and D_{\Omega}(\delta, \lambda)"
 
19
Insert "c," after "choice input,"
 
27
Replace (q,a) with (q,a,c)
101, 102
 
The exposition on these pages will be improved in the next printing. (Click here to see the improvements.)
103
-2
Replace w by i
111
7
Add "and size" before "of"
 
17
Change "machine" to "memory"
113
23
Change x-1 to x and "itself" to "zero".
 
2nd column, line 3
Add new line: "CLR R_0   Clear the contents of R_0"
114
11,12
Add "Unbounded-Memory" between "the" and "RAM"
 
14
Delete "if M is in C and" and add the phrase "(A stronger definition requiring that M also be in C is used in Section 3.8.)" after sentence.
115
11
Add "input address" after "output words"
117
1, 17
Add 2 after second ( on lines 1 and 17
 
14
Change 2(m to (2m
119
11
Change (q',C) to (q',a',C)
120
2
Add "a)" before "$M$" and "b) $M$" before "accepts"
 
3
Replace this line with "and only if it is in $L$."
121
11
Change \sqrt{2 \pi} to \sqrt{2 \pi n}
124
3
Change "S(n)" to "S"
125
Fig. 3.25
Change c_0 to c_1
126
14
Delete (s_{j-1,t-1})
 
Fig. 3.26
Change output gate of SC_1 and its top input gate to OR gates, shrink circles
128
21,22
Change SATISFIABILITY to SAT
129
-4
Change \subseteq to \in in both places and replace L by L*
 
-1
Add "if $w \in L$ and 0 if $w \not\in L$".
131
Fig. 3.28
Change Thm. to Def. in two places
132
15
Change "Design a DTM" to "Design an NTM"
 
-12
Delete "that"
133
4
Change "nondeterministic" to "deterministic"
 
9
Change "quadratic" to "cubic"
 
10
Change "CIRCUIT SAT" to "SATISFIABILITY"
138
Fig. 3.31
Move > up and move 1 right
147
-3
Change z_i to c_i
149
18
Change n^2 to n^4
150
10
Add "Hint: Because such RAM programs can only have a finite number of registers, encode the contents of the TM tape as a number to be stored in one register."
151
2
Change "fixed" to "free".
     
CHAPTER 4    
155
Fig. 4.2
0 missing on top edge
156
15
Change "on input 1" to "on input 0"TEXT
158
11
second L_1 should be L_2
161
Fig. 4.6
Replace label "0" in (c) by "a"
162
Fig. 4.8
Leftmost label should be y instead of x
165
Fig. 4.15
Caption should refer to Fig. 4.3
 
6
Delete "of length k"
 
9
Change "s" to "s = q_t"
168
6
Change $r_{1,5}^{(5)} & = & 010 + (010)(10+010)^{\ast}$ to $r_{1,5}^{(5)} & = & 010 + (010)(10+010)^{\ast}(\epsilon + 10 + 010)$
 
9
Change $\epsilon + 01 + (010)(01+010)^{\ast} to $\epsilon + 01 + (01)(01+001)^{\ast} (\epsilon + 0) = (01+010)^{\ast}$
169
19, 20, 21
n \geq 0, delete r in rs = 0^d, change n to n-1 in exponent
172
-3
Add "For this purpose we extend the state transition function $\delta$ to strings $\mbox{\boldmath $a$} \in \Sigma^{\ast}$ recursively by $\delta(q,\epsilon) = q$ and $\delta (q, \sigma \mbox{\boldmath $a$}) = \delta (\delta(q, \sigma), \mbox{\boldmath $a$})$ for $\sigma \in \Sigma$."
173
3
Insert "accessible" before "states"
 
6
Insert "with finite $R_L$" after $\Sigma$.
174
-3
Change $q_0$ to $s_0$
175
-1
Change k+1 to j+1
176
7
Change "$q_R$ is an" to "$q_3$ is in a"
 
9
Change "{$q_1$}, {$q_2$, $q_3$}" to "{$q_3$}, {$q_1$, $q_2$}"
 
16
Change ",s," to ",[s],"
 
28
Change "fewer" to "more"
 
31,34,36
Change "$R$ to "$R_L$
 
-3
Change "{$q_1$}, {$q_2$, $q_3$}" to "{$q_3$}, {$q_1$, $q_2$}"
180
2
Change \gamma to \epsilon
 
Fig. 4.26
Change label from s to f to $\beta, \epsilon, \epsilon$
181
9
After "finite set $\Sigma$" insert ", with $|\Sigma| \geq 2$,"
 
14
After "respectively" add "a designated non-terminal start symbol"
182
-11
Change "$a \in V^+$ to "$a \in {\cal N}^+$
 
-10
Change {\cal N}^+ to {\cal N}
 
-10
Add "containing at least one non-terminal symbol" to end of line
183
-2
Change "1}" to "0}"
184
3
Change cMNc to cMcNc
 
-2
Add "L(G) and L(G) \cup {\epsilon}" after "languages" and change "grammar" to "grammars G"
185
-2
Change "every language" to "the language"
 
-1
Due to q -> \epsilon, G_M is not regular. Add text explaining conversion to regular language. The new page 185.
187
-4
Delete "We"
 
-3
Replace "keep the rule" by "except for", delete "and eliminate the rest as follows", delete "and", and add "or B => \epsilon"
189
-5
Delete ( and )
 
-1
Change i \leq n-1 to i \leq n
190
1
Add "and $b_{i,i+1}$" to beginning of line
 
6
Change b_{n-1,n} to b_{n,n+1}
 
9
Change "terminals" to "nonterminals"
 
10
Change i \leq n-1 to i \leq n
 
-1
Change subscript "i" in "($C \to w_i$)" to "i+2"
197
15
Change "$L$" to "$L(G)$"
201
14
The second regular expression is $(01+001)^{\ast}$.
202
-9
Remove {w | ... } and drop b) and make sentence singular
     
CHAPTER 5    
210
25
Add "exactly the" between "accepts" and "strings"
212
8
Change q_4 to q_3
213
-2
Change M_1 to M_k
214
-4
Delete last ) in this line
215
5
Insert "and the tape head at the leftmost position" after "blank tape"
216
4
Insert "Breadth-first search is used."
 
9
Add "one" at beginning, change "inputs" to "input", and add "on each step" after "tape".
 
10
Delete "repeated; that is, the computation is"
 
11
Delete "breadth-first searching"
 
-4
Change DTM to TM
218
-5
Change DTMs to TMs
 
-2
Add "directed" at the beginning of the line
219
14
Change "languages" to "grammars"
 
20
Add \beta, after \Gamma,
 
22
Add ", and not others." at end of line
220
1
Change "Rule (d)" to "Rule (e)"
 
2
Change $\beta$ to $\beta ]$ and delete "(e) removes ]"
 
7
Change "xq -> xq" to "xq -> px"
 
-5
Add Since an NDTM can be simulated by a DTM, all strings accepted by a TM can be generated deterministically in sequence."
221
16
Change the second instance of z'' to z'''
 
-13
Change "valid" to "canonical" and "can be described" to "are a subset of the strings defined".
 
-12
Replace the period that follows in this paragraph with "which a TM can analyze to insure that for each state and tape letter there is a valid action."
 
-3
Add "<, >, \widehat{<}, \widehat{>}"
 
-1
Add "preceded by $\beta$ and" after "U"
222
1
Change \widehat{[} to \widehat{w}_1
 
7
Add "It then changes < to $\widehat{<}$" before "moves"
 
10
Add "U returns to $\widehat{<}$ and removes the mark."
 
Fig 5.10
Add "The left end-of-tape marker is the blank symbol \beta" to the caption. Put \beta in a new first cell.
223
10
Replace sentence "This follows ..." by "Each must be contained in $([(<\{0, 1, \beta, \mbox{\bf L}, \mbox{\bf R}\} \# 1^{\ast}>)^3 ])^{\ast}$ and have a transition for each state and tape letter."
 
12
Delete "canonical"
 
13
Replace "does not correspond to a valid encoding" by "is not canonical".
 
-3
Add "that" in "such the"
224
20
Change "rules" to "definition"
 
-10
Delete "not"
225
9
Change w_j to w_i
226
7
Change L_2 to {\cal B}^{\ast} and add ${\cal B}$ after "alphabet"
 
 
227
Fig 5.12
In caption, change _1 to _2 and _2 to _1
 
8
Add "and L_2 is recursively enumerable" before comma
228
-5
Replace "it" by "the tape" and delete "then"
228
4
Replace "if w is in L(M)" by "if and only if M halts on w"
 
-5
Change "accepts" to "halts"
 
-3
Add "and encoding" after "constructing"
 
-2
Change "empty tape" to "emtpy string"
229
10
Change "accepts" to "halts on"
 
13
Change T(M,w) to L(T(M,w))
 
15
Change T(M,w) to \rho(T(M,w))
 
16
Change second "it" to M
 
-5
Add "over ${\cal B}$" before period
230
9
In this paragraph state that T(M,w) simulates M on w and recognizes strings in L in parallel by alternatively simulating one step in each computation until one of them halts. The current argument presumes that L is recursive, not just recursively enumerable.
 
-8
Change "accepting" to "rejecting"
231
 
Replace "zero function" by "predecessor function" and delete "predecessor function" from line 8 page 232. Insert "zero function" definition after Definition 5.9.1.
232
3
Add )
233
4
Insert new paragraph stating correspondences between building blocks of partial recursive functions (composition, primitive recursion, minimilization) and straight-line programs, programs with for-loops and while loops.
 
-12
Change w_1 to w_i
234
-5
Change "L(M) = \emptyset" to "L(M) is infinite"
235
5
Change "L(G) = \emptyset" to "L(G) \not = \emptyset" and delete the hint
 
-13
Make p bold.
 
-12
Make p bold and precede by "state"
 
-10
Delete ", a"
236
6
Change "primitive" to "partial".
237
2
Add "Algebraic circuits combine operations drawn from an algebraic system."TEXT
     
CHAPTER 6    
239
19
Replace sentence by "In this section we introduce rings, fields and matrices, concepts widely used in this chapter."
 
21
Add "and Fields
 
22
Replace sentence by "Rings and fields are algebraic systems that consists of a set with two special elements, $0$ and $1$, and two operations called addition and multiplication that obey a small set of rules."
 
-7
Make sentence part of preceding paragraph and add sentence "A {\bf field} is a commutative ring in which each element other than \mbox{\boldmath $0$} has a {\bf multiplicative inverse} (for all $a \in R$, $a \not= \mbox{\boldmath $0$}$, there exists an element $a^{-1}$ such that $ a \ast a^{-1} = \mbox{\boldmath $1$}$)."
 
-6
Change "Let N be the natural numbers (the set of non-negative integers)." to "Let Z be the set of positive and negative integers." and change the second instance of N to Z.
242
-8
Add "commutative" before "ring"
243
1,3,7
Insert "over a field R" after A
 
13
Replace "the ring of positive and negative integers" with "a field R"
 
17,18
Change "ring" to "field"
 
-1
Delete "the entries of"
245
11,19
Insert "commutative" before "ring"
247
8
Insert 3 before log n
 
-5
Insert "commutative" before "ring
 
-1,-2,-5
Change A+B to A*B
250
16
Change A^{*} to AxB
251 Theorem 6.4.3 Because Figure 6.4 on page 252 doesn't include computation of Y, depth bound on line -6 should be D(n) = 2D(n/2) + O(log n). Also, change depth bound on line 8 in theorem to O(n).
  -15 Change  to T(n) = 2T(n/2) + 6M(n/2) + 2(n/2)^2
  -4 Delete "closed"
  -1, -2, -4 Change * to \cdot
252 Fig. 6.14
  4, 6, 7 Change * to \cdot
  8 Delete "closed"
 
-3
Change "ring" to "field"
253
8
Change "ring" to "field"
254
5
Change "ring" to "field"
257
4
Change "ring" to "field"
260
2
Change "ring" to "field"
 
-6
Change "substituting A for x, we have" with "it can be shown"
263
-11
Add space after "If"
265
4,5,14,21,22
Change "w" to "\omega"
269
15
Change "w" to "\omega"
271
-1
Change <= to <
 
-5
Change <= to <
  Section 6.8.1 New title : "Sorting Via Bitonic Merging". Apparently, it is a common error, which I have also committed, of referring to Batcher's bitonic merging as odd-even merging. To correct all the errors that result, changes must be made to the following pages: 18 (TOC), 271-3, 301, 309-11, 316, 320, 410, 481, 482, 555. Changes are also required to the following pages in the Index: 625, 648, 650, 661, 664, 665.
272
Fig. 6.11
Change the labels $y_1$, $y_0$, $y_2$, $y_3$ to $y_3$, $y_2$, $y_1$, $y_0$
273
Fig. 6.12
Exchange y_1 and y_3 and exchange y_0 and y_2
 
4
Interchange b-1 and b+1
 
13
Change n-input to 2n-input
 
15
Change (n/2) (log n) to n (log n + 1)
 
16
Change \log n to \log n + 1
 
17
Change C(1) = 1, D(1) = 1 to C(0) = 1, D(0) = 1
 
18
Change + 2^{k-1} to + 2^k and k2^{k-1} to (k+1)2^k
 
19
Change D(k) = k to D(k) = k + 1
 
22
Change BM(n) to BM(n/2)
274
Prob. 6.1
Change N to Z
 
27
Add "commutative" before "ring"
 
-16
Insert "over a field" after "A"
275
-6
Insert "over fiels" after "that"
276
5,6
Change "ring" to "field"
 
16
Insert "over a field" after "A"
 
-3,-4
Change 2n-1 to n
277
19
Change limit on product from n-1 to k-1
278
4
Change C(1) = 1 to C(0) = 1 and D(1) = 1 to D(0) = 1
 
5
Change k2^{k-1} to (k+1)2^k
 
6
Change = k to = k + 1
     
CHAPTER 7    
283
-8
Change "our" to "an"
 
-9
Add "in words" after "messages"
 
-8
Change "message" to "word"
 
-6
Change "unit-length" to "word"
286
-4
Add (0) after 1
287
1
Change "its" to "the"
 
13
Change "x[a_j]" to "x[n+1-a_j]" for j = n, n-1, 1
291
22
Delete ceiling on m/p
 
24
Replace \leq with <
 
30
Add , $n = 2^k$ before period.
 
-8
Replace phrase starting "or ..." with "to $p-1 processors and $n - (p-1) \lceil n/p \rceil$ integers to the remaining processor"
 
-2
Change n/p to p
292
2
Replace "one unit" with "zero"
 
-2
Change "adds" to "sets", insert "to" before "the sum"
 
-1
Change "and" to "plus"
293
-4
Change "adds to" to "sets" and add "to" before "the product"
 
-3
replace "and" by "plus"
296
9
After "array" add "and another n-1 steps to compute the last entry $c_{n,n}$."
298
7
Replace "n cells" by "as far as 2n-1 cells"; Change 4n+2 to 8n-2
 
-10, -9
Change "n" to "2n-1"
 
-7
Change 4n+2 to 8n-2
302
4
Change "descending" to "ascending"
 
5
Change "ascending" to "descending"
 
-2
Change (d-1) to (d-2), a_1, 0) to a_2)
304
2
Change n/2 to n
 
-14
Change "right" back to "left" as in first printingTEXT
305
Fig. 7.17
Add missing arrow to box 1
306
7
Replace by "A fully normal descending algorithm has the above steps followed by the steps in reverse order."
 
8
Replace "or descending" by "(descending)"
 
10
Change "in" to "with", and add "(2T(n)) additional" before "parallel".
307
10
Delete "Each step of"; change n- to 2d-
 
15,16
Change "linear" to $n \times n$
 
17
Change 2 \sqrt{m} -1 to 2 \sqrt{m} -2; Change $m \times m$ to $\sqrt{m} \times \sqrt{m}$
 
19
Change 2 \sqrt{m} -1 to 2 \sqrt{m} -2
 
24
Change "\leq 2d" to "< 2d"
 
25
Change "\leq (2d)" to "< (2d)"
308
22
Before second period add ", where $0 \leq i,j \leq n-1$
 
24
Change n to n-1
 
26
Change $1 \leq j \leq n$ to $0 \leq j \leq n-1, j\not = k$
 
28
Change $1 \leq i \leq n$ to $0 \leq i \leq n-1, i\not = k$
 
31
Change $C_{i,j,k}$ to $C_{i,j,0}$
311
10
Replace text beginning "The first" with the following: "For $1 \leq i \leq n/4$ ($n/4 +1 \leq i \leq n/2$) the top output of switch $i$ is connected to the top input of the $i$th switch in the upper (lower) copy of $P_{n/2}$ and the bottom output is connected to the bottom input of the $i$th switch in the lower (upper) copy of $P_{n/2}$. The connections of output switches are the mirror image of the connections of the input switches."
 
22
Replace "first" by "second"
313
-6
Add "algorithm" after "hypercube"
314
14
Add exponent 2 to \log p
 
-7
Replace "in" with "with slowdown factor" and delete "steps"
316
7
Add "by destination address" before "cooperatively"
 
18
Before "The first" add the following: "To compare destinations, move messages to adjacent vertices on the hypercube, compare, and then reverse the process. (Move them by sorting by appropriate addresses.)"
 
-8
Change $1 \leq i \leq k$ to $0 \leq i \leq k-1$
 
-5
Change first 3 to 2
317
12
Delete "fully"
 
16
Replace "is fully normal" by "consists of a fixed number of normal and fully normal sequences of steps"
 
27
Change 3 to 2
321
1
Change in \sqrt{n} to 3\sqrt{n}
     
CHAPTER 8    
329
-10
Add ", for example"
330
10
Delete "where $k \geq 1$,"
 
-3
Add "(Definitions of time and space on Turing machines are given in Section 8.4.2.)"
337
20
Change k^n to 2^{n^k}TEXT
 
21
Change k^n to 2^{n^k}TEXT
338
-6
Change 8.5 to 8.6
341
8
Delete NSPACE(r(n)) and add "deterministic and nondeterministic space-bounded" before "classes".
 
-14
Change 8.5.6 to 8.5.5TEXT
343
3
Add "for some $k \geq 1$"
 
-15
The proof of Theorem 8.6.1 has been reworked for clarity.
345
-12
Change node_1 to node_2TEXT
346
-10
Change NPSPACE(r(n)) \subseteq coNPSPACE(r(n)) to coNPSPACE(r(n)) \subseteq NPSPACE(r(n))
 
-8
Change coNPSPACE(r(n)) \subseteq NPSPACE(r(n)) to NPSPACE(r(n)) \subseteq coNPSPACE(r(n))
347
15
Change VALIDITY with SATISFIABILITY
 
19
Change \overline{VALIDITY} to coVALIDITY and fix related text.
363
-8
The statement "which implies that there is a path from \overline{x} to x" is incorrect. It is necessary to say that an instance is a "No" instance if and only if there is a variable x such that there is a path in G from x to \overline{x} and one from \overline{x} to x and to use this fact in the proof. Only small changes are needed in the argument. Figure 8.15 changed to add edges for (\overline{x}_3 \vee x_1). (Click here to see correction.)
381
-1
Replace "gate" by "circuit"
385
-4
Change b^T to c^T
386
4
Change "1" to "0".
 
6
Change "Construct" to "Let"
 
7
Replace this line with "${\cal T}$ be a set variables that have value 1. Let ${\cal T}$ be empty initially. Cycle"
 
10
Change "is" to "are" and add "Show that all satisfying assignments contain ${\cal T}$."
     
CHAPTER 9    
402
Fig. 9.4
In caption second sentence is "The input $x_2$ has fan-out 2."
 
-10
Changed 2s' -2 to 2s' +2
407
12,13
Changed (n_j -1) to n_j
411
-1
Add -4 to -3k and to - 3 log_2 n
412
1
Change 3 to 4 in two places
435
19
Move the text from lines 24 and 25 to this line
 
24
Replace the text "more ..." with "at least e(|V|/2)/2 edges."
 
-6
Replace "more than e(5n/2)" with "at least e(5n/2)/2 edges."
454
-7
Replace = 2n-4 with \geq 2n-3
     
CHAPTER 10    
463
Fig 10.1
Caption - Replace text starting "can be" with "Input vertices are on the bottom; edges are directed upward. Four pebbles are shown on the graph when pebbling the leftmost output."
464
3
Change "graph" by "of Fig. 10.1"
 
4
Change 27 to 15
467
2
After "least" add "$k$ pebbles,"
471
-9
Change Problem 10.28 to Section 10.8
474
-2
Change first exponent of n to n + \lceil log n \rceilTEXT
477
-16
Change k to k-1TEXT
 
-16
Change k to k-1TEXT
 
-11
Change D and E to boldTEXT
478
1
Change and to orTEXT
 
7
Drop | | inside first set of ( )
 
14
Delete last "and rows"
 
15
Add "rows of" after "and"
 
-3
Change 2/9 to 1/3
479
7,9,10
Delete \sqrt{2}
 
11
Change n^2/6 to n^2/27; 2\sqrt{2} to 16; 6\sqrt{S} to 27\sqrt{S}; 2/9 to (.35); n^6/2 to n^6/3
482
Fig. 10.9
Change the labels $y_2$, $y_1$, $y_4$, $y_3$ to $y_4$, $y_3$, $y_2$, $y_1$
497
9,10
Replace "has a (1/\mu, m, \tau)-flow" with "is (\alpha,n,m,p)-independent for the appropriate values of \alpha, n, m, and p."
500
13
Replace "the (1/\mu, m, \tau)-flow property" with "(\alpha,n,m,p)-independence"
 
15
Replace "a (1/\mu, m, \tau)-flow" with "is (\alpha,n,m,p)-independent"
 
16
Replace everything after "for" with $p = p = \min (\lambda n, \tau(\mu m)) + \mu m"
 
18
Delete "(b)" and "(x)" after "\tau^{ast}" and the first instance of "\tau(x)"
 
25
Replace everything after "f" with is $(1/\nu, n, m, p)$-independent for $p = \tau^{\ast} + \mu m$.
521
-3
Replace "has an (\alpha, m, p)-flow" with "is $(\alpha, n, m, p)$-independent"
 
-3
Replace "has an (\alpha, m, q)-flow" with "$(\alpha, n, m, q)$-independent"
524
-12
Delete "tight"
 
-11
Add "that are within a factor of $O(\log ^2 n)$ of one another
 
-10
Change "tight" to "good"
     
CHAPTER 11    
533
3
Replace "by a factor of $2^{\beta}$" by "to $S^{\beta}$"
 
4
Add "namely $\beta \approx 7$," after the comma
 
5
Replace "by a factor of about 128" by "from S to about S^7$"
538
Fig. 11.3
Increase step numbers 13-22 by 1
540
1
Change \geq to = at end of line
 
3
Change - to +
 
11
Change L_1 to L-1
 
17
Add "and the output" after "A"
 
18
Change 3n^2 to 2n^+n
542
-16
Change ab/S to \sqrt{ab/S}
     
CHAPTER 12    
581
15
Replace "subtrees (leaves)" by "leaves"
 
16
Add "H_{k-1} with" after "of" and delete "with copies of H_{k-1}" and replace "itself" with "H_1"
585
Fig. 12.4
Lines made thicker to make them all visible
 
-6
Replace "a d-dimensional" with "n-processor"
589
-12
Reduce space between V and comma
590
3
Add "Since the lemma is true if the cost of any vertex exceeds 1/3, assume the converse."TEXT
 
5
Change "consists of the regioiu outside of all edges and vertices" to "is the face of unbounded area."TEXT
 
7
Strike the phrase "; that is, the face has ... "TEXT
591
-12
Change "a) L" to "a) H"
 
8,9,10
Change "the cycle defined by e" to $\xi(3)$
 
12
Change "the cycle defined by (x,y)" to $\xi((x,y))$
 
13
Change "the cycle defined by (x,y)" to $\xi((x,y))$
 
13
Replace "the assumption that" with "If greater than 2c(V)/3, $\xi((x,y))$ is a cycle with fewer faces which is contradicted.
 
-11
Change "e) L" to "e) H"
 
-9
After "empty" add "and $l = h = m$"
 
-7 and -6/DIV>
Change r_l and r_h to l and h
592
19
Change 2c(v)/3 to 7c(v)/9TEXT
593
1
Add "of" to the section heading
594
15
Change "P = 4" to "P = 7"
599
2
The problem now states "Show that every layout of a balanced binary tree on $n$ leaves in which the
 
2
root and the leaves are placed on the boundary of a convex region has area
 
2
proportional to $n \log n$."
 
5
Add "{\bf Hint:} Consider an inscribed quadrilateral defined by the longest
 
5
chord and a chord perpendicular to it."
600
10
Add "from the root" after "path"
 
16
Change "2c(V)/3" to "7c(V)/9"
     
BIBLIOGRAPHY    
 
 
Citations may be off by one, two or three places
609
Ref [103]
Make Kung an author
615
3 (8 in 2nd)
Change "Mealey" to "Mealy" 
626
10, Left Col
Change "binary 564" to "binary 78, 564"
630
9, Left Col
Delete "closed semiring"
632
-18, Left Col
Add 615
636
26, Left Col
Insert "directed graph 10"
637
-11, -12, -13
Delete Euler's constant entry
641
-18, Right Col
Delete "closed"
643
11, Left Col
Delete 612
644
1, Right Col
Change 613 to 614
646
7, Right Col
Add 612
648
18 and 19
Change "Mealey" to "Mealy" 
653
32, Left Col
Change "directed graph, maximal ..." by adding "10" after "graph"
655
-17, Right Col
Delete "of closed semirings"
656
8, Left Col
Add "of semirings"
658
8, Right Col
Delete "closed semirings"
 
12, Right Col
Add "semirings"
659
-14, Left Col
Delete "closed" and move 251 to preceding line
670
24, Left Col
Change "binary," to "binary 78"
672
5, Right Col
Insert "walk 10"