E R R A T A F O R T H E S E C O N D P R I N T I N G O F T H E
P A S C A L E D I T I O N
Page 13, 4th line of INDUCTION: ``Section 1.3''
Page 50, line 13: A[1..m] are already sorted, not A[i..m]
line 16: Part (b) of T(m), not Part (a)
2nd line above Loop Invariants: nondecreasing
Page 96, 2nd line of Example 3.7: insert ``of'' between ``number'' and
``times''
Page 106, line 15: Example 3.13.
Page 112, line 2: Example 3.13.
Page 142, first point. The argument doesn't work. I think it should be:
``... the total running time is O(log n) times the work done at
each call, ... . In the case of merge sort, the work at each call,
including basis calls, is O(n), ...''
Even then the argument implicitly uses the assumption that
2^k f(n/(2^k)) <= f(n), where f(n) is the measure for the work done
at a call with argument size n, that is, the work done at each call
is at least linear.
Page 158, end of second paragraph: delete everything after ``0.37 millisecond''.
Page 168, last line: ``operands'' instead of ``operations''.
Page 192, Exercises 4.10.4 and 4.10.5: the explanation of the loops in
Ex. 4.10.4 in Ex. 4.10.5 is false. Easiest correction:
``while a[i] < 0'' in Ex. 4.10.4. b)
Page 194, Fig. 4.31: 10...0 in two's complement is -2^(n-1).
Page 195, second paragraph: the sum has one 0 too many, so there will be no
carry out of the first place, and the rest of the argument is wrong.
In lines 5 and 6 of that paragraph, swap ``out of the first place''
and ``into the first place''.
1. last line: ``carry out of the first place.'' Delete rest of the
sentence. If there is an overflow, the first position becomes 1,
but there is no carry out of the first place.
2. and 3.: replace ``carry out of the last place'' by ``carry out
of the first place'' three times.
Page 198, line -9: the basis on the two summands is missing.
Page 239, add ; after definition of PTRTONODE.
Page 246, lines 3 and 4 after the box: replace ``has a second argument'' by
``is''.
first line of 1.: delete ``the second argument of''.
Page 257, last line: exponent is (h+1)
Page 258, first line: 2(2^(h+1)-1) +1 = 2^(h+2) -1
line -10: ``we ask, for''
Page 266, Exercise 5.10.2: The induction is on j.
Page 272, entry for Floyd [1964]: p. 701
Page 286, Fig. 6.9: delete ``end'' after line (2), but leave the `;'.
Page 291, line 6: move closing parenthesis from after 2 to after high.
Page 303, Fig. 6.27.: replace `,' in line 2 by `;'.
Page 311, Fig. 6.33: the LCS is cbba.
Page 315, Fig. 6.34: add ' after earth.
Page 355, 1st line of 3rd paragraph: insert ``a'' after ``There''.
Page 381, 4th line of 2nd paragraph in 7.11: delete first ``that''.
Page 409, line (1) of Fig. 8.9: StudentId-Name-Address-Phone relation.
line 3 after Fig. 8.9: ''
Page 422, 1st line of paragraph above Example 8.16.: capital `B' component?
Page 433, Exercise 8.9.5: For completness the condition for the law
might be included.
Page 458, analysis of the running time. The argument is a bit flawed. While
m was defined to be the larger of the number of nodes and the
number of edges, in the analysis of the while-loop, m suddenly
becomes the number of edges. If the graph were very sparse, the
O(n) term might dominate the O(log n) times the number of edges
term. To be exact, one could perhaps write: ``The while-loop
iterates at most m times. Thus the time for this loop is at most
O(m log n), ...''
Page 466, line -10 (without footnote): replace ``takes time'' by ``is''.
Page 467, Fig. 9.27.: add `;' after line (6).
Page 472, Fig. 9.31.: G must be a var parameter.
Page 474, Fig. 9.33.: " in dfsForest.
Page 479, 1st paragraph, 3rd line: the sum over the m_v is m only under
the assumption, that there are more edges than nodes.
Possible correction: ``..., the sum of the 1 is the number of
nodes, and the sum of m_u is the number of edges. As m is the
larger of the two, the time of the loop ...''
line -5: insert ``in'' before O(m).
Page 492, Fig. 9.47.: ``G[v].header'' in line (7).
Page 496, first line after the box: arc[v,w] = arc[w,v]
Page 499, 2nd line of ``Why Floyd's Algorithm Works'':
``only through'' instead of ``through only''?
Page 500, 3rd line of 1.: dist[v,w], not dist[u,v].
Page 507, Dijkstra [1959]: Numerische Mathematik, no b anywhere in it.
Page 526, line -3 of the box: replace ``input'' by ``output''.
Page 543, Exercise 10.5.4 c): the expression should be printed in boldface.
Page 564, Fig. 10.41: swap the labels on the arcs between c and d.
Page 568, Exercise 10.9.2: automata of Exercise 10.4.3? Otherwise the
plural is misleading.
Page 571, 4th line of 2nd paragraph: insert ``a'' between ``is'' and
``mechanical''.
Page 572, Induction. As the operators aren't restricted to equal arguments,
the conventional definition would be better:
``If E_1 and E_2 are expressions, ...
(E_1) ...
E_1 + E_2 ... '', and so on.
Page 582, line -2: production (8), not (6).
Page 583, line 4 of 2.: no comma between ``children'' and ``the roots''.
Page 585, Fig. 11.13: ``Parse tree ...'', singular.
Page 589, Exercise 11.4.2, c) delete period after the string.
line 2 of 11.5: .
Page 595, 4th line of Exercise 11.5.3: ``two or more comparison operators''.
Page 597, line 10: no comma after ``ENDM''.
Page 614, line 7 of the box: ``(m+1) states that A is in ...''
line -4 (without footnote): ``a string of m - j + i 0's''
Page 615, Fig. 11.38.: the automaton is nondeterministic. The figure
suggests that it is possible to ``break out'' of the loop in
state s_j, even though the input is still 0.
Page 619, 2nd line of 12.1: ``The next section, 12.3, ...''
Page 623, line 2: replace ``than'' by ``that''.
Page 651, line 3 of 12.6: swap ``first'' and ``last''.
Page 656, 1st line of 12.24: ``NOT and OR''
last line above 12.24 b): ``NOT and OR''
Page 657, Exercise 12.8.12, last line: `` ... do not hold.''
Page 661, 4th line above the exercises: ``NOT and OR''
last line above the exercises: ``law 12.15, ...''
_
Page 670, last line: ``p is equivalent ...''
_
Page 684, line -3 of the box: ``lines labeled x or y, ...''
_ _
Page 704, line -4 above the figure: | log_2 (d+1) |
Page 706, line -2 of the box: ``we build a 2d-MUX from 2^d +1 smaller MUX's.''
Page 711, line 7: ``Course-StudentId-Grade''
Page 714, 2nd line of Example 14.1: ``Course-StudentId-Grade''
Page 715, 2nd line of Example 14.3: ``Course-StudentId-Grade and
StudentId-Name-Address-Phone''
Page 719, line above the figure: replace `P' by `Q'.
Page 722, Exercise 14.4.1 b): swap the first opening parenthesis before
the ``there exists an y'' and the opening parenthesis before
the second ``there exists an x'' expression to reflect the scope
of the parentheses.
Page 737, line 4: move the larger opening parenthesis before the second
``there exists an x'' to before the ``there exists an y'' expression
and delete one of the small opening parentheses instead.
1st line of 14.8: ``In this section and the next ...''
Page 738, middle formula in the middle of the page: one too many opening
parenthesis before ``csg(...)''
Page 741, line adjacent to ``Body, head,'' : delete one ``side''.
5th line of Example 14.22: ``Course-StudentId-Grade''
line after csg-facts: ``StudentId-Name-Address-Phone''
Page 742, 4.: sub(S) = 12345
A Simplified Inference Rule
last line of 1.: ``line (5)'' instead of (4)
last line of 3.: ``line (4)'' instead of (5)
first line of 4.: ``from (4)'' instead of (3)
2nd line of 4.: ``from (5)'' istead of (1)
Page 746, Exercise 14.9.5, line 1: ``Course-StudentId-Grade''
Page 753, entry for G\"odel [1931]: ``\"Uber formal unentscheidbare
S\"atze der Principia Mathematica und verwandter Systeme'',
Monatshefte f\"ur Mathematik und Physik ...