Errata for the CS60 TextBook by Robert Keller

Edition of August 1997

Last update: 21 March 1998

These are errors in the printed textbook. The on-line version will be corrected as time permits.

If you report an error which has not already been spotted, you receive one bonus point.

• Page 6, first full paragraph, second line "Thus, book starts" should be "Thus, this book starts. [Chris Schied]
• Page 13, para. 3, line 5: delete "will"
• Page 30, line 6: omit period after "Jean"
• Page 31, line 3: "old_mail" should be "current_mail" and "older_mail" should be "old mail"
• Page 38, both display captions: "apple icon" should be "yin-yang icon"
• Page 42: There is no exercise #2
• Page 51, 2nd para, line 1: "reference" should be "references"
• Page 61: mid-page, "once cannot" should be "one cannot"
• Page 62: Third sentence should read "It is difficult to present functional programming..." instead of "functionally programming."
• Page 70 (Exercise #1 grammar) - "definitions" should be "definition"
• Page 94, in sentence beginning "Implement a function ....", replace "no duplicates are" with "all duplicates have been"
• Page 95, "When it is removed, node 5 becomes a leaf." should read "When it is removed, node 6 becomes a leaf." [Jason Dorsett]
• Page 155, second definition of 'find' (breadth-first case) should be

          find(P, [Node | Nodes], Graph, Seen) =>
                  Targets = get_targets(Node, Graph),
                  New = difference(Targets, Seen),
                  Find(P, append(Nodes, New), Graph, [Node | Seen]);
  

  (the arguments of difference were reversed, rather than those of append, as stated in the text)
• Page 156, exercise 2, "tree" should be "graph"
• Page 179, para. 1, line 2: "discuss" should be "discusses" [Dan Darcy]
• Page 181, para. 2, last sentence, "is can" should be "is" [Jason Dorsett]
• Page 183, line 5: "Funtions cons make..." -> "Function cons makes..." [Dan Darcy]
• Page 183, line -4: insert "way" after "elegant" [Virginia Stoll, Dan Darcy]
• Page 188, opening sentence of 4.5: "to implement" should be "may be used to "implement"
• Page 189, line 6: Delete "The previous figure illustrates..." since there is no previous figure [Dan Darcy]
• Page 191, last line: "M. head" should be "M.head"
• Page 192, Exercise 1, line 2: delete "of" [Dan Darcy]
• Page 192, Exercise 3, line 1: replace "in" at end with "into a" [Dan Darcy]
• Page 192, Exercise 4, line 1: add "a" after "in" at end [Dan Darcy]
• Page 193, Exercise 13: insert "a" before "DLL" [Dan Darcy]
• Page 195, line 11: "of the left sub-tree, the a post-order" should be "of the left sub-tree, then a post-order" [Dan Darcy]
• Page 195, Exercise 19: End second sentence with a question mark [Dan Darcy]
• Page 196, line 2: "key words numbers or phrases" should be "key words, numbers, or phrases" [Dan Darcy]
• Page 197, line 21: "Each character is added to h time a constant" should be "Each character is added to h times a constant" [Dan Darcy]
• Page 198, exercise 2; omit, since polys have not been covered in the text
• Page 199, first display: the & notation means "address of" and was not introduced before this point (it is from C++)
• Page 210, line before second display: "express rules from changing" should be "express rules for changing" [Dan Darcy]
• Page 210, line 11 (second line after third display): "However, the end" should be "However, they end" [Dan Darcy]
• Page 210, line 12: "the rules are not actually rex" should be "the rules are not actually in rex" [Dan Darcy]
• Page 210, line 14: insert "which" before "is able" [Dan Darcy]
• Page 210, line 15: "soltuion" should "solution" [Dan Darcy]
• Page 210, line 16: "in the case the" should be "in the case that the" [Dan Darcy]
• Page 216, line -7: "a totally of |A1||A2| ways" should be "a total of |A1||A2| ways" [Dan Darcy]
• Page 217, line 1: the last character (a dash) should be omitted [Dan Darcy]
• Page 217, line 4: the last "-1" should be omitted [Dan Darcy]
• Page 219, exercise 2 should come after exercise 6.
• Page 219, line 2: there should be an blank line between problems 3 and 4 [Dan Darcy]
• Page 219, two lines before the "15 puzzle", "block" should be "blocks" [Dan Darcy]
• Page 221, Exercise 12: Should end with a question mark. [Dan Darcy]
• Page 250, line 8: "(called methods )." should be "(called methods)." [Dan Darcy]
• Page 254, last para., 4th line: move "expressly" to after "dealing" [Jason Dorsett]
• Page 256, second para., first line: insert "one" after "allows" [Jason Dorsett]
• Page 259, first line of text: "before" should be "after" [Jason Dorsett]
• Page 259, Sec. 7.8, line before the display: "allow to" should be "allow" [Jason Dorsett]
• Page 260, second display caption: "Sack" should be "Stack" [Chuck Scheid]
• Page 260, line -1: omit comma. [Dan Darcy]
• Page 263, caption, "repository" should be "repositories"
• Page 270, line 8: "extends..." is wrong font. [Dan Darcy]
• Page 271, 2nd line, "re;atively" should be "relatively"
• Page 271, 2nd para, 4th line, delete "as soon as possible."
• Page 273 Line before 7.2, "abstrations" should be "abstractions" [Jason Dorsett]
• Page 273, last para, 5th line, delete "while."
• Page 274, line 8: omit "are" [Dan Darcy]
• Page 274, Exercise 1: delete the words "based on" [Jason Dorsett]
• Page 274, Exercise 1: "bias.." should be "bias."
• Page 276, Sec. 7.14 line 6: " is a" should be "is an" [Jason Dorsett]
• Page 276, line -1: "remove" is wrong font. [Dan Darcy]
• Page 282, line beginning "Window": "objectwhich" should be "object which" [Jason Dorsett]
• Page 282, Sec. 7.16, 2nd paragraph, "approaching" should be "approach" [Jason Dorsett]
• Page 283, before last display, "type of data they contain" should be "the type of data each contains".
• Page 283, line -5: "immutable;" -> "immutable," [Dan Darcy]
• Page 285, second sentence: Replace with "We could just compare references to the objects, which would mean that two objects are equal only when they are in exactly the same storage location. Alternatively, we could compare them more deeply, component-by-component. In this case, there is the issue of how those components are compared, e.g. by reference or more deeply, and so on. Hence there is a spectrum of possibilities for equality comparison." [Matt Azuma]
• Page 283, second display: remove third ";" in the "for" statement [Jason Dorsett]
• Page 292, 2nd para., "an Enumeration" should be "Enumerations (and interfaces in general)"
• Page 292, 2nd para., "method be" should be "method may be"
• Page 293, Item labeled "2.", "later" should be "latter"
• Page 294, Sec 7.23, 2nd para, 2nd line, "have to used" should be "have to use"
• Page 294, Sec 7.23, 2nd para, 5th line, "take" should be "takes", "return" should be "returns"
• Page 295, line -3: remove 2nd "a function" [Jason Dorsett]
• Page 303, line 3: "infinite, set" -> "infinite set" [Dan Darcy]
• Page 304, line -3: "its" -> "it is" [Dan Darcy]
• Page 311: The second grammar rule, S -> ( S ), overlaps with the text. [Jason Dorsett]
• Page 313: The grammar given does not correspond to the preceding one discussed, as stated. The first rule should instead be:

  E:
    V
    E '+' V
  

  and the second rule should be omitted. [Jason Dorsett]
• Page 313, line 2: insert "of" after "instead" [Virginia Stoll]
• Page 314, under "Grammar for Regular Expression", 3rd line, "form" should be "formed" [Jason Dorsett]
• Page 316, line 13: "language: i.e." -> "language, i.e." [Dan Darcy]
• Page 325, last para heading: remove ".i." and ";" [Virginia Stoll]
• Page 330, first sentence: "precedencedetermination" should be "precedence determination" [Eric Pabst]
• Page 342, line 2: "to deeply" should be "too deeply"
• Page 347, last display (factorial): "0" should be "1"
• Page 348, First Sentence "math occcasionally texts use" should be "math texts occcasionally use" [Jason Dorsett]
• Page 348, last para, line 1: "tee" should be "tree"
• Page 360, 2nd display, the word "downward" belongs on the previous line, after "bit"
• Page 361, 2nd table, last line, "110" should be "111" [Eran Karmon]
• Page 362, line 8: "separate" -> "separate and" [Dan Darcy]
• Page 362, line -6: "encoded," -> "encoded" [Dan Darcy]
• Page 364, the headers are really botched.
• Page 366, first display, the left node labeled 101 should be 100
• Page 366, second display, there is an unlabeled node, which should be labelled 1011. Also, that node should be connected to 1011.
• Page 367, third display from the bottom, the headers aren't aligned properly
• Page 369, exercise 1, "Construct the corresponding functions bit functions..." should be "Construct the corresponding bit functions..." [Virginia Stoll]
• Page 383, line -4: insert "or" before "several" [Chuck Scheid]
• Page 386, caption: "A n" -> "An" [Dan Darcy]
• Page 389, line 9: "E1 to E11 and E10," is repeated. [Dan Darcy]
• Page 390: The second left parenthesis in the Boole/Shannon expansion equation should be in bold-face. [Dan Darcy]
• Page 391, line -1: "for a" -> "form a" [Dan Darcy]
• Page 417, The second equation is missing an opening parenthesis; " ( 1 + 2 ) < 4 ) ||..." should be "( ( 1 + 2 ) < 4 ) ||..." [Virginia Stoll, Dan Darcy]
• Page 423, The explicit quanitification of grandmother(X, Y) is "...if ('there exists' x) mother(X, Z) and parent(Z, Y)]" and should be "...if ('there exists' Z) mother(X, Z) and parent(Z, Y)]" [Virginia Stoll]
• Page 433, fourth line of paragraph: "predicates" should be "functions"
• Page 434, first two lines: periods should be semicolons.
• Page 434, in third display: period should be omitted.
• Page 443 In complete specification s and max are used for the same variable. Either the s needs to be changed to max or vice versa [Jason Dorsett]
• Page 448 Bottom of Page Notes:, "k and n variables" should be "k and f variables" [Jason Dorsett]
• Page 448, Near the bottom, "Ai and A'j are the same assertion, except that has its k and n ..." should be "... except that A'j has its k and n..." [Virginia Stoll]
• Page 458, 1st paragraph, 5th line. "square" should be "squared".
• Page 466, Near the middle of the page,, delete "If we don't count assignments as an operation," (it then proceeds to count them) [Virginia Stoll]
• Page 482, Above the caption "sqrt(n) vs. log(n)" there exists no corresponding plot [Virginia Stoll]
• Page 485 in the table: N log N for 10000 should be 132877, not 13287.
• Page 494: Near the bottom of the first paragraph, "then a sequence of size would take..." should be "then a sequence of the same size would take..." [Virginia Stoll]
• Page 495: At the beginning of the last paragraph, "If the range of is very large, ..." should be "If the range is very large, ..." [Virginia Stoll]
• Page 496, third line: "is" should be "are"
• Page 504, In the last line of pseudocode, "... remove a[i] to the heap ..." should be "... remove a[i] from the heap ..." [Virginia Stoll]
• Page 511, The heading is "Sets Implementation..." and should be "Set Implementation..." [Virginia Stoll]
• Page 511, At the beginning of the first paragraph, "This is perhaps the simplest way..." should be "Perhaps the simplest way..." [Virginia Stoll]
• Page 511, The second sentence in the first paragraph should end with one period instead of two. [Virginia Stoll]
• Page 517: In the list of terms for chapter review, "profililng" should be "profiling" [Virginia Stoll]
• Page 521: Near the end of the third paragraph, "of well-balanced parenthesis strings also..." should be "of well-balanced parenthesis strings, also..." [Virginia Stoll]
• Page 524: The header "Example An Edge-Detector" should be "Example: An Edge-Detector" [Virginia Stoll]
• Page 526: In the header "Imperative Program view of Finite-State Machines" the word "view" should be capitalized [Virginia Stoll]
• Page 530: The headers on the state-transition table are misaligned (they should not line up so it looks like one column is "next symbol") [Virginia Stoll]
• Page 532: The paragraph that starts "The arcs and nodes are differently, ..." should start "The arcs and nodes are labeled differently, ..." [Virginia Stoll]
• Page 533: Above the graph, "Here is its graph" should end with either a ":" or a "." [Virginia Stoll]
• Page 547, diagram. The top arrow from state c to state a should be from d to a instead.
• Page 548, there is an unwanted tab
• Page 551, grammar productions, there is an unwanted tab
• Page 551, diagram: remove the 0 on the left of state C and the second 0 under state F.
• Page 567, In the second sentence, "transducer" should be "transducers" and "as a "feedback" systems." should be "as "feedback" systems." [Virginia Stoll]
• Page 567 After the header, "clearer on what it is corresponds to" should be "clearer on what corresponds to" [Virginia Stoll]
• Page 558, Kleene's theorem display: Omit second period.
• Page 570, In the middle of the second paragraph, "the signal input is sample" should be "the signal input is sampled" [Virginia Stoll]
• Page 571, In the last paragraph, "and AND-gate" should be "an AND-gate" [Virginia Stoll]
• Page 577, first table. The entries for the input values should be shifted over to the right so that they are aligned with the labels "0" and "1".
• Page 589, line before display: omit period after "parallel composition".
• Page 593, In the last paragraph, "to which we wish transfer." should be "to which we wish to transfer." [Virginia Stoll]
• Page 594 In the middle of the last paragraph, "which of the three states the device is in are all controlled" should be "which of the three states the device is in is controlled" [Virginia Stoll]
• Page 604 In the sentence after the first example, "3 both to hold" should be "3 to hold" [Virginia Stoll]
• Page 606 Near the end of the second paragraph, "The label pseudo op" should be "The label pseudo-op" [Virginia Stoll]
• Page 609 In the first sentence, "entry an exit." should be "entry and exit." [Virginia Stoll]
• Page 610 In the last line, "in the same as" should be "in the same way as" [Virginia Stoll]
• Page 611 In the first paragraph, there is a reference to chapter "Computing on Demand", which doesn't exist. [Virginia Stoll]
• Page 611 In the first paragraph, "must be set up before hand." should be "must be set up beforehand." [Virginia Stoll]
• Page 628 In the definition of "based indexed addressing", "containing and index." should be "containing an index." [Virginia Stoll]
• Page 635 Near the beginning of the second paragraph, "to have an to deal with" should be "to have an interrupt to deal with" [Virginia Stoll]
• Page 641 The first sentence should end with a period. [Virginia Stoll]
• Page 641 In the second sentence, "several compute agents" should be "several computing agents" [Virginia Stoll]
• Page 643 In the section of code, "finishing child" should have "//" (comment marks) before it, and should probably be indented to match the first part of the comment. [Virginia Stoll]
• Page 644 In the third paragraph, there is a reference to a chapter "Computing on Demand", which doesn't exist. [Virginia Stoll]
• Page 645 Near the top of the section of code, "read end" and "write end" should both have "//" before them, and should probably be indented to match the other comments. [Virginia Stoll]
• Page 647 At the end of the first paragraph, "in principal" should be "in principle" [Virginia Stoll]
• Page 651 Above the header "Figure to be added..." there exists no diagram. [Virginia Stoll]
• Page 652 In the second paragraph, "He should how" should be "He showed how" [Virginia Stoll]
• Page 653 In the first paragraph, "in the game of life, for example patterns" should be "in the game of life; for example, patterns" [Virginia Stoll]
• Page 655 In the first sentence, "conducing" should be "conducting" [Virginia Stoll]
• Page 655 In the second sentence, "instructions streams" should be "instruction streams" [Virginia Stoll]
• Page 657 In the first paragraph, "to share an a variable" should be "to share a variable" [Virginia Stoll]
• Page 661 In the last line, "to something from another processor's memory" should be "to get something from another processor's memory" [Virginia Stoll]
• Page 664 In the second paragraph, "From the programmers point" should be "From the programmer's point" [Virginia Stoll]
• Page 664 In the second paragraph, "knowing the servers address" should be "knowing the server's address" [Virginia Stoll]
• Page 669, top paragraph, "Similar, we also have" should be "Similarly, we have" [Virginia Stoll]
• Page 670, last paragraph, "it's 0's and 1's" should be "its 0's and 1's" [Virginia Stoll]
• Page 674, sentence ending "any polynomial algorithm." should end "any polynomial algorithm is undecided." [Virginia Stoll]
• Page 675, second full paragraph, "to any speed up method" should be "to any speedup method" [Virginia Stoll]
• Page 676, first paragraph, "the top-left and gate" should be "the top-left AND gate" [Virginia Stoll]