## Foundations of Computer Science/C Edition --- Errata

Page 7, 7th line of Example 1.1: delete "struct" from "struct LIST next;" (thanks to Matthew O'Keefe)

Page 19, Item 4, Line 4-5: "tilde for left shift" should be "tilde for negation." (Thanks to Ricardo Urena)

Page 23, Lines 6-8: The parameters Type, CellName, and ListName should be EltType, CellType, and ListType, respectively. (thanks to Charlie Burns)

Page 23, Line -15: We need a * and not a comma before LIST. That is to say, the line should read typedef struct CELL *LIST;

Page 26, 9th line of item (3): "previous values" should be "previous value." (Thanks to Sylvia Wiebrock)

Page 46, Line -14: delete "is" from "The goal is of". (Thanks to Chiec La Luong)

Page 48, Line 9: E_2 should be E_1. (thanks to Matthew O'Keefe)

Page 50, Exercise 2.4.2: Example 2.11, not 2.10.

Page 56, Line 11: "all of A[0..m] are sorted". (Thanks to Sylvia Wiebrock)

Page 56, Line 14: "Part (b)" instead of "Part (a)". (Thanks to Sylvia Wiebrock)

Page 85, Line 10: "n-i" instead of "n-i+1". (Thanks to Sylvia Wiebrock)

Page 87, Fig. 2.32: Replace the Pascal-isms "sum =" and "find0 =" by "return" (2 times each).

Page 87, Exercise 2.9.1: PrintList is in Fig. 2.31(a), not (b).

Page 88, Line 4: "need" is repeated. (Thanks to Sylvia Wiebrock)

Page 104, Example 3.8, Line 2: "number of times". (Thanks to Sylvia Wiebrock)

Page 106, Line 9: "and" not "And". (Thanks to Sylvia Wiebrock)

Page 116, Line 5: lower-case "a" instead of upper-case.

Page 131, Lines 6-8: "O(n^2)+O(n)" should be "O(1)+O(n)" on Line 6. Then, on Line 7, we need to reorder the terms so O(n^2) is second. On Line 8, refer to the second term, rather than third term, as the dominant one. (Thanks to Ugo Buy)

Page 155: Missing reference: Hartmanis, J. and R. E. Stearns, "Computational complexity of recursive sequences," Proc. Fifth Annl. Symp. on Switching and Automata Theory," pp. 82--90, 1964. (Thanks to Sylvia Wiebrock)

Page 167, Line -2: The first "and" should be "at". (Thanks to Arunprasad Marathe)

Page 171, Line 11: "to appear" should be "may appear". (Thanks to Sylvia Wiebrock)

Page 173, bottom: If you multiply and divide in the order n/1*(n-1)/2*...*(n-m+1)/m all partial results will be integers. (Thanks to Arnold Lebow)

Page 174, Fig. 4.10: delete "int n, m;" (Thanks to Sylvia Wiebrock)

Page 175, Line -13: "much less efficient than". (Thanks to Arunprasad Marathe)

Page 178, Line 23: "pair" should be "pairs". (Thanks to Sylvia Wiebrock)

Page 178, Line -3: "i_m be the number of items in the m th group for m = 1, 2,...,k" (i.e., i and m reverse roles). (Thanks to Arunprasad Marathe)

Page 181, Line -5, -4: "m bins" and "n identical objects" (i.e., m and n reverse roles). (Thanks to Arunprasad Marathe)

Page 182, last line of Example 4.16: "6+3-1" is better expressed as "3+6-1" to match the formula. (Thanks to Arunprasad Marathe)

Page 182-183: The idea behind the "Distributing Distinguishable Objects" is flawed. The formula given there assumes that the order of the items within the bins matters, e.g., in Example 4.17 it is different if a child receives an apple then a pear, or a pear then an apple. If we do not care about order within a bin, then the proper formula is \$\prod_{j=1}^k {{m+i_j-1}\choose{i_j}}\$. (Thanks to Prasad Sistla)

Page 184, Line 5: "and and" should be "and an". (Thanks to Sylvia Wiebrock)

Page 199, Line 23: Only one "more." (Thanks to Loong Nguyen)

Page 199, Line -8 (excluding footnote): R_3 should be R_1. (Thanks to Kelly Schwarzhoff)

Page 206, Line 20: "0-05" should be "0.05". (Thanks to Arunprasad Marathe)

Page 208, last sentence (continues onto p. 209): "Thus, the fact that a compound event's probability is known only within a range may not present a great problem, as long as we can deduce that the probability of the event is "high." (Thanks to Sylvia Wiebrock)

Page 211, Exercise 4.11.3(c), Line 2: "drops at least 5 degrees" (not 4 degrees).

Page 220, Line -10: "... are not identical, but order within bins matters" (Thanks to Sylvia Wiebrock)

Page 228, Line 4: "The label can be something simple," (Thanks to Sylvia Wiebrock)

Page 237, Fig. 5.12: pNODE c needs to be declared. (thanks to Matthew O'Keefe)

Page 244, Line (1) of Fig. 5.19: delete parenthesis after "op."

Page 255, Line -16: "records" should be "structures". (Thanks to Sylvia Wiebrock)

Page 257, Exercise 5.6.1, Line 2: "records" should be "structures". (Thanks to Sylvia Wiebrock)

Page 257, Exercise 5.6.5, Line 1: delete "a" before "full". (Thanks to Sylvia Wiebrock)

Page 258, Exercise 5.6.6, Line 1" "record type" should be "data structure". (Thanks to Sylvia Wiebrock)

Page 261, Line 3: "or" should be "of". (Thanks to Sylvia Wiebrock)

Page 263, Fig. 5.35, Lines (4) and (5): == should be =.

Page 270, Line 8-9: add 1 to each of the 3 exponents on these lines. 2^h becomes 2^{h+1} (twice) and 2^{h+1} becomes 2^{h+2}. (Thanks to Sylvia Wiebrock and John Pinto)

Page 271, Line 1: "For" should be "for". (Thanks to Sylvia Wiebrock)

Page 271, Exercise 5.8.2(a): The "1+" should be omitted from the formula. Alternatively, the formula as it is gives the average number of comparisons that must be made to find v, rather than the depth at which it is found (Thanks to Arnold Lebow)

Page 279, Exercise 5.9.2: "induction on j". (Thanks to Sylvia Wiebrock)

Page 285, Line -8: "pp." should be "p." (Thanks to Sylvia Wiebrock)

Page 287, Line -2: delete "that". (Thanks to Sylvia Wiebrock)

Page 299, Line 25: "typdef" should be "typedef."

Page 300, 7th line below Fig. 6.9: "L" should be "pL". (Thanks to Sylvia Wiebrock)

Page 314, Line -2: "record type" should be "union type". (Thanks to Sylvia Wiebrock)

Page 317, Fig. 6.27, Line (4): "if (i >= MAX)". (Thanks to Sylvia Wiebrock)

Page 325, title of Fig. 6.33: the LCS selected is actually cbba. (Thanks to Sylvia Wiebrock)

Page 370, Line 12: "is" after "There". (Thanks to Sylvia Wiebrock)

Page 396, Line -19: delete one of the "that"s. (Thanks to Sylvia Wiebrock)

Page 420, Line -16, -14, -9, -1: replace "record(s)" by "structure(s)". (Thanks to Sylvia Wiebrock)

Page 421, Line -12: "record" should be "structure" (twice). (Thanks to Sylvia Wiebrock)

Page 425, Line 2 of Fig. 8.9: "Grade" should be "Phone". (Thanks to Sylvia Wiebrock)

Page 426, Line 3: "Grade" should be "Phone". (Thanks to Sylvia Wiebrock)

Page 438, Line 20: "b" should be "B". (Thanks to Sylvia Wiebrock)

Page 449, Exercise 8.9.5: add "whenever C is a condition about R alone". (Thanks to Sylvia Wiebrock)

Page 455, Fig. 9.3: The arc from PrintList to MergeSort should be from main to MergeSort. (Thanks to Matthew O'Keefe)

Page 457, Line -7 through -5: Each of these cycles needs to repeat the first node at the end. Thus, add ",v_1" after "v_k" on Line -7, and add ",v_i" at the end of the cycles on Lines -6 and -5. (Thanks to Sylvia Wiebrock)

Page 474, Line 3: delete semicolon at end.

Page 476, Line -8, -7: "The while-loop iterates as many times as there are edges." Note m is technically the larger of the number of nodes and edges. (Thanks to Sylvia Wiebrock)

Page 485, Line 1: "takes time" should be "is". (Thanks to Sylvia Wiebrock)

Page 490, Line 1: delete semicolon at end.

Page 495, Exercise 9.6.6: While valid, the hint can be ignored. There is a simple induction (not complete) that doesn't need the identity at the end of the exercise.

Page 495, Exercise 9.6.8, last line: "are" should be "be".

Page 497, Line 18: "the sum of m_u is at most m." Note that m is an upper bound on the number of edges, not the exact number of edges. (Thanks to Sylvia Wiebrock)

Page 497, Lines 29-30: "forward in the order" should be "from front to rear in the order."

Page 510, Line 1: delete semicolon at end.

Page 510, Line 14: "dist[1]" should be "dist[0]". (Thanks to Sylvia Wiebrock)

Page 515, Line -1: "arc[v][w] = arc[w][v]". (Thanks to Sylvia Wiebrock)

Page 518, title of Fig. 9.55: "best distances to node 3". (Thanks to Sylvia Wiebrock)

Page 520, Line 10: "dist[u][v]" should be "dist[v][w]". (Thanks to Sylvia Wiebrock)

Page 521: Second exercise numbered 9.9.8 should be 9.9.9. (Thanks to Sylvia Wiebrock)

Page 527, Line -7, -6: "Numerische". (Thanks to Sylvia Wiebrock)

Page 536, Exercise 10.2.4: We omitted the possibility that the first character is underscore. (Thanks to Joshua Rosenblum)

Page 546, Line 15: "input" should be "output" (of the command on the left of the |). (Thanks to Sylvia Wiebrock)

Page 551, Line -20: "record(s)" should be "structure(s)" (twice). (Thanks to Sylvia Wiebrock)

Page 584, Fig. 10.40: The loop on state c should have label 1, not 0. The arcs between c and d should have their labels complemented. Also, states c and d need double circles; they are accepting. (Thanks to Ricardo Urena, Jon Morrow, and Sylvia Wiebrock)

Page 588, Exercise 10.9.2: "Convert the automata of Exercise 10.4.3..." (Thanks to Sylvia Wiebrock)

Page 591, Line 9 of text: "is a mechanical way". (Thanks to Sylvia Wiebrock)

Page 592, Line 15: "if E is an expression" should be replaced by "if E stands for `any expression' ". (Thanks to Sylvia Wiebrock)

Page 603, Line 2 below figure: "production (6)" should be "production (8)". (Thanks to Sylvia Wiebrock)

Page 604, Line 11 of text: delete comma after "children". (Thanks to Sylvia Wiebrock)

Page 605, Fig. 11.13 title: "tree" instead of "trees". (Thanks to Sylvia Wiebrock)

Page 609, figure in box: the node labeled "1" should be "3" (Thanks to Jack Reese)

Page 610, Line 10: "" should be "". (Thanks to Sylvia Wiebrock)

Page 618, Line 9: delete comma after ENDM. (Thanks to Sylvia Wiebrock)

Page 618, Line -13: "but" should be "by". (Thanks to Sylvia Wiebrock)

Page 621, Line -14: "mandatory that" should be "manditory for". (Thanks to Sylvia Wiebrock)

Page 633, Exercise 11.7.5: Add " else " to production (1). (Thanks to Sylvia Wiebrock)

Page 638,Line 7: "m states" should be "m+1 states". (Thanks to Sylvia Wiebrock)

Page 642, Line -13: "12,3" should be "12.3". (Thanks to Sylvia Wiebrock)

Page 645, Line 12: "left-hand" and "right-hand" are reversed. (Thanks to Tom Fountain)

Page 646, Line 15: "than" should be "that". (Thanks to Sylvia Wiebrock)

Page 647, Line 10: "value" should be "values". (Thanks to Sylvia Wiebrock)

Page 647, Line -1: "declared" should be "defined". (Thanks to Sylvia Wiebrock)

Page 658, Line 7: "and" should be "any". (Thanks to Sylvia Wiebrock)

Page 679, Lines 16 and 22: "AND" should be "NOT". (Thanks to Sylvia Wiebrock and Jack Reese)

Page 681, Line -12: "to" should be "do". (Thanks to Sylvia Wiebrock)

Page 685, Line -8: "AND" should be "NOT". (Thanks to Sylvia Wiebrock)

Page 685, Line -5: "law 12.12" should be "law 12.15". (Thanks to Sylvia Wiebrock)

Page 690, Line 11: "right-hand" should be "left-hand." Also, "left-hand" should be "right-hand" twice on line 13. (Thanks to Arun Marathe)

Page 696, Line 7: p should be p-bar. (Thanks to Sylvia Wiebrock)

Page 708, Line 8: x-bar should be y-bar. (Thanks to Sylvia Wiebrock)

Page 727, Line -4: parentheses around "d+1" are needed. (Thanks to Sylvia Wiebrock)

Page 729, Line 6 below figure: "d+1 smaller MUX's" should be "2^d+1 smaller MUX's". (Thanks to Sylvia Wiebrock)

Page 733, Line 6 of text: "Student" should be "StudentID". (Thanks to Sylvia Wiebrock)

Page 736, Line 7: "Student" should be StudentID" (Thanks to Sylvia Wiebrock)

Page 737, Line 2 of Example 14.3: "Student" should be StudentID" (twice) (Thanks to Sylvia Wiebrock)

Page 753, just below (14.6): We need to add the additional condition that Y is not free in E. (Thanks to Vassos Hadzilacos)

Page 759, Line -12: "chapter" should be "section". (Thanks to Sylvia Wiebrock)

Page 760, Line 21: delete parenthesis before "csg". (Thanks to Sylvia Wiebrock)

Page 763, Line 10: delete one "side". (Thanks to Sylvia Wiebrock)

Page 763, Lines 4 and 10 of Example 14.22: "Student" should be StudentID" (Thanks to Sylvia Wiebrock)

Page 764, Line 11: "sub(S) = 12345". (Thanks to Sylvia Wiebrock)

Page 764, Lines -8 and -14: swap "line (4)" with "line (5)". (Thanks to Sylvia Wiebrock)

Page 764, Line -6: "from (1)" should be "from (5)". (Thanks to Sylvia Wiebrock)

Page 768, Line 1 of Exercise 14.9.5: "Student" should be "StudentID" (Thanks to Sylvia Wiebrock)

Finally, thanks to the following people who caught errors in the solution manual for the book: Tom Fountain, Anandi Gnanalingam, Glenn Mitchell, Dave Stone.

Jeffrey D. Ullman
`ullman @ cs.stanford.edu`
650-494-8016 (home)
650-725-2588 (FAX)