Errata for

Models of Computation: Exploring the Power of Computing

by

John E. Savage

January 6, 2004

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"