COMPSCI 220 coursebook errors

We will be awarding a prize (most likely, 0.2% added to course marks) to the first finder of each new error in the latest version of the textbook (current version was published in mid-2004). Errors and corrections will be listed here as they are found. Errors may be typographical or factual. Grammatical errors by non-native English speakers will not count for credit. The lecturers' decision on what constitutes an error is final and not subject to appeal.

When reporting errors by email, please include both your name and UPI. Errors found by students will be marked in the form FOUND (DATE): UPI and those not found by a member of the class, but found by the lecturers, will be added to this page by the end of the semester.

Errors and corrections (Semester 2, 2008)

p17, Example 1.13: "less than" sign should be "less than or equal to" sign. FOUND (2008-08-11) arob147.
p65, "leafs" should be "leaves". FOUND (2008-07-25) dton011.
p123 Ex 5.2.5 (i): should read "List all tree arcs in the DFS forest". FOUND (2008-09-15) nmih001.

Errors and corrections (Semester 1, 2008)

p12, Ex 1.1.1: "time" should be explicitly measured in elementary operations. FOUND (2008-04-24) gloh006.
p126 Fig. 5.9: BFS pseudocode does not compute correct level. FOUND(2008-04-30) jgre139.
p128 Sec 5.4: "In BFS, the key value can be taken ..." does not make sense, since we don't keep track of the seen time in our pseudocode. By seen[v] we mean some counter that gives minus the insertion time into the queue. FOUND (2008-04-11) nkir017.

Errors and corrections (Semester 2, 2007)

p40, Thm 2.9 proof, last line: maximum number of comparisons should be n_C - 1 = n_A + n_B - 1. FOUND (2007-08-04): cwu080.
p41 merge pseudocode: input for merge should be in the order array a[n], array indices l,s,r, array t[n]. FOUND (2007-08-04): cwu080.
p166 Sec 7.1: "256M" should be "256MB". Found (2007-10-20): bsmi080.
p166: "arbitrary large" should be "arbitrarily large". Found (2007-10-20): bsmi080.

Errors and corrections (Semester 2, 2006)

p13 Example 1.6: the two uses of the variable m are inconsistent. Replace the first one by m - 1. It is not specified what kind of loop we have: it is of the form "while i < n". FOUND: (2006-07-28) pyap011.
p14 Exercise 1.2.1: Replace (n - 1) by simply n following "then" statement. FOUND (2006-08-05) mdal044.
p15 "In other words .... at most as fast ...." should be "In other words .... at least as fast ....". FOUND (2006-09-19) aahm027.
p82, bottom: "Hash functions are designed in such manner that hash codes are computed fast" should read "Hash functions are designed in such a manner that hash codes are computed quickly". FOUND (2006-09-20) rtio003.

Errors and corrections (Semester 1, 2006)

p3 para 2: "A book of this type written by..." should have a comma, "A book of this type, written by...". FOUND: (2006-06-19) ccar090.
p14: There are inconsistencies throughout the book starting here between using "Big-Oh" and "Big Oh". As listed in the index there is a hyphen in each of the three (Big-Oh, Big-Omega, Big-Theta). FOUND: (2006-06-19) ccar090.
p36, Exercise 2.1.8, line 1: "bubblesort" should be "bubble sort" to follow with the convention for this throughout the chapter. FOUND: (2006-06-19) ccar090.
p50, Example 2.20, last sentence: the word "in" is missing and should read "...has a left child in position 8 and...". FOUND: (2006-06-19) ccar090.
p56, Table 2.7: Building max heap line 4: This lineshould have an italicized entry "65". FOUND: (2006-06-19) ccar090.
p87, last sentence: "...uniform hashing that form more clusters..." should be changed to "...uniform hashing that forms more clusters...". FOUND: (2006-06-19) ccar090.
p121: dfs code correction below had a typo - now fixed. FOUND: (2006-05-23) rgul006.
p125 Thm 5.6 proof: d[s,u] should be d(s, u) on line 9. FOUND (2006-06-17) hlan024.

Errors and corrections (Semester 2, 2005)

p11, table: entry 250503 should be 250500. FOUND: (2005-09-23) psta028.
p19 exercise 1.34: right parenthesis missing in Theta(f(n)). FOUND: (2005-08-08) smer019.
p26, top: instead of Step n-1 and Step n, it should be Step n-2 and Step n-1. FOUND: (2005-08-09) smer019.
p26, paragraph above diagram: ..the scaled relationships for T(n), 2T(n-1), 2^2 T(n-1), ... That last bit should be 2^2 T(n-2) instead. FOUND: (2005-08-09) smer019.
p27, example 1.31, first line: the inequality for T(n) should have subscript 2 for the log. FOUND: (2005-08-09) smer019.
p29, example 1.34: base 2 is used but not shown, whereas log means base 10 elsewhere in book. FOUND: (2005-08-09) smer019.
p34, below Table 2.2. "Note that I_i = M_i in Table 2.1." This should say Table 2.2. FOUND: (2005-08-09) smer019.
p34, line -1: "comparison" should say "move". NOT FOUND.
p35, exercise 2.1.4: ".. during exection of ..." should be "... execution ..". FOUND: (2005-08-09) smer019.
p38, first para: "significally" -> "significantly". FOUND: (2005-08-09) smer019.
p52, just before example 2.26: "in average" -> "on average". FOUND: (2005-08-09) smer019.
p57, step 3: "place the pivot as a[i]" -> "place the pivot at a[i]". FOUND: (2005-08-09) smer019.
p63, line -3: "... array as represented ..." -> "...array is represented ...". FOUND (2005-08-15) iate002.
p66 line 2: "some" -> "same". FOUND (2005-08-15) iate002.
p81 end of Example 3.28: remove parenthesis at end of line. FOUND (2005-08-19) smer019.
p81 line -6: missing full stop between "set" and "If". FOUND (2005-08-15) iate002.
p82 line -2: ".. such manner ..." -> "... such a manner ...". FOUND (2005-08-19) smer019.
p85 Figure 3.17: "probe decrement Delta = -1" -> "probe decrement Delta = 1". FOUND (2005-08-19) smer019.
p88, equations in middle of page: limits of integration in middle should be n and n-m, not n and m-n. FOUND (2005-08-19) smer019.
p89, para above 3.36, last line: "... list references by ..." -> "... list referenced by ...". FOUND (2005-08-19) smer019.
p91, above table: "...1.5...3.0 or and so forth" should not have "or". FOUND (2005-08-19) smer019.
p93: second last paragraph, last line reads: " ... function scatter the keys ... " it should read " ... function scatters the keys ... ". FOUND (2005-08-17) iate002.
p95, Thm 3.40 proof, fifth line: missing space before "It". FOUND (2005-08-19) iate002.
p105, Example 4.20: "The constructed Graph G is call the..." -> "The constructed Graph G is called the...". FOUND (2005-11-06) smcp011.
p110, Table 4.2: the delete node entry for list/list should be Theta(n+e), and the delete arc for list/list should be Theta(d), as mentioned in the text. NOT FOUND.
p117 line 5: "...at least b at most B... -> ...at least b and at most B". FOUND (2005-11-08) iate002.
p121, Figure 5.7: the pseudocode for dfsvisit is wrong, as is dfsvisit in Figure 5.9 and pfsvisit in Figure 5.10. A corrected version is here. NOT FOUND.
p125, line 4: array level should be array d. NOT FOUND.
p127 Thm 5.7 proof last para: "In the first case, w may be seen v..." -> "In the first case, w may be seen before v...". FOUND (2005-11-04) mwat074.
p137, Theorem 5.21 proof: "descendant of the first once seen ... " -> "descendant of the first one seen ... ". FOUND (2005-08-26) iate002.
p139, note: reference to Figure 5.7 should be to Figure 5.15. FOUND (2005-11-08) iate002.
p151 para 4 should have full stop (.) at end. FOUND (2005-11-08) iate002.
p155 proof line 4: correspnding -> corresponding. FOUND (2005-11-08) iate002.
p157, Example 6.14: edge {1, 4} should be {2, 4}. FOUND (2005-11-08) iate002.
p157, penultimate sentence: "restrated" -> "restarted". NOT FOUND.
p158 para 2 line 4: "The if ..." -> "Then if ...". FOUND (2005-11-08) iate002.
p158, Thm 6.15 proof, last para: "...it just chosen..." -> "it has just chosen...". FOUND (2005-11-04) mwat074.
p170: line 6: "... means that that we can design ..." -> "... means that we can design ...". FOUND (2005-08-24) iate002.
p171,line -5: "... {w' | w'is the reverse of some ..." has a missing space. FOUND (2005-08-24) iate002.
p181 para -2, last line: "then" -> "than". FOUND (2005-11-08) iate002.
p184, Ex 7.6.2: there is a colon (:) that should not be there. FOUND (2005-08-26) iate002.
p185, para 2: "... grammar into a "parser," one of ..." should read ... grammar into a "parser", one of ...". Same type of comma error on p192, line 10. FOUND (2005-09-19) iate002.
p201 note "... halts if only if it is ..." should read "... halts if and only if it is ...". FOUND (2005-10-21) iate002.
p229, last para: code referred to is on p. 230, not p. 229. FOUND (2005-08-19) iate002.

Errors and corrections (Semester 1, 2005)

p90, para 2: "The hush function ... " should be "The hash function". FOUND (2005-04-15): mchi067.
p103, Defn 4.15: "... induced by a a subset ..." should be "induced by a subset...". FOUND (2005-06-16): emoo015.
p137, Thm 5.21 proof: in last sentence, ...would have been was reachable" should be "would have been reachable". NOT FOUND.
p148, Thm 6.8 proof: a bad line break in the second paragraph, and in the next paragraph, there is a font error in "P2". NOT FOUND.
p151, Thm 6.9 and proof: the definition of "level" is wrong. It should be the minimum number of arcs in a MINIMUM WEIGHT path to that node from the source. Every minimum weight path from the source to a node can have no more than n-1 arcs since there are no minimum weight cycles. In the proof, note that the subpath gamma_1 must be a minimum weight path to y and hence y has level at most m, so the inductive hypothesis applies. NOT FOUND.
p152, Bellman-Ford pseudocode, inner for loop: "=" should be "<-". NOT FOUND.

Errors and corrections (Semester 2, 2004)

p2, middle of page: "or delete and element" should be "or delete an element". FOUND (2004-08-05): cfat002.
p8, para 2: "...written on..." should be "...written in...". FOUND (2004-07-20): rvan058.
p10, para 2: "...in this case the reminder..." should be "...in this case the remainder...": FOUND (2004-07-25): dbay009.
p10: GCD(1730, 7595 mod 1730) should be GCD(1730, 7515 mod 1730). FOUND (2004-07-24): whsu007.
p11, algorithm slowsum: "array s[m]" should be "array s[m+1]". FOUND (2004-07-29): whsu007.
p13, line 4: "... step." should be "... steps.": FOUND (2004-07-30): rvan058.
p22, Exercise 1.4.1: "log log n" should be "ln ln n" since using log log 10 = 0 doesn't make sense for ratio": FOUND (2004-07-27): rvan058.
p22, last para: "...which is difficult..." should be "...which it is difficult...": FOUND(2004-07-30): etch003.
p40, para before Ex. 2.10: "from c+1" => "from m+1" and "array t as c" => "array t as C": FOUND(2004-08-02): rvan058.
p45, line 1: "arrae" should be "array": FOUND (2004-08-04): rvan058.
p47, partitioning line 7: replace "a_{r-1}" with notation "a[r-1]"
p48, end of 1st para: replace "a_l" with notation "a[l]".
p53, para 3: "thre lines" should be "three lines".
p66, para 1: "some coplexity" should be "same complexity": FOUND (2004-08-04): rvan058.
p67, para 1: "when search for" should be "when searching for": FOUND (2004-09-15): rvan058.
p72, Ex 3.15: "...number of nodes above or to the right plus the number..." should be "...number of nodes to the left including the number...": FOUND(2004-11-02): cpat045.
p75, Def 3.20: for a red-black tree we need to add the property that all internal nodes have two children: (With this change the proof for Theorem 3.21 is now correct.): FOUND(2004-08-16): whsu007. (also "...every path from the root to a leaf must..."; see Exercise 3.3.1 correction below)
p76: "...AA-tree becomes most efficient than..." should be "...AA-tree becomes more efficient than...": FOUND(2004-11-04): dsmi100.
p80, exercises: 3.3.1 "...a node to a leaf." should be "...the root to a leaf"; 3.3.2 "...the AVL one?" should be "...an AVL one?".
p82, Hashing: "... all elements until you find a match" should be " ... all elements until we find a match": FOUND(2004-09-15): rvan058.
p86: line 6: "hash address, h(k), *that* resulted in *a* collision: FOUND(2004-11-05): rvan58.
p89: Lemma 3.36: "T_us(lamda) = 1 + lambda": FOUND(2004-11-05): rvan58.
p90, para under 3.6: "...an an empty..." should be "...an empty...": FOUND(2004-08-14): whsu007.
p91: Table 3.4: the column headed SC for unsuccessful search needs 1 added to all entries (also heading should read T_us): FOUND(2004-11-04): rvan058.
p102: def of cycle: "...in which v_0=v_n and no arcs are repeated." should be "...in which v_0=v_n and no other nodes are repeated.".
p102: Example 4.8: "0,1,3,1,2" should be "1 3 1 2": FOUND(2004-09-06): rvan058.
p103: Example 4.12: "d(3,1)=2" should be "d(3,2)=2": FOUND(2004-09-06): rvan058.
p105: 1st sentence: "...between different the G_i." should be "...between the different G_i.": FOUND(2004-09-06): rvan058.
p115: middle page: "Now once a has been completed search forest has been obtained," should be "...has been completed and a search forest obtained,...": FOUND(2004-11-04): dsmi100.
p128: "...to choose one with smallest key." should be "...to choose one with the smallest key.": FOUND(2004-08-24): rvan058.
p129: "seudocode" should be "Pseudocode" and "...shown in Figure 5.5." should be "...shown in Figure 5.11": FOUND(2004-08-24): rvan058.
p131: (bottom of the page): "...proceed as follow." should be "...proceed as follows.": FOUND(2004-09-20): ashe056.
p132: (top of the page): "...and xome arcs canot..." should be "...and some arcs cannot...": FOUND(2004-09-20): ashe056.
p132: (last paragraph): "...stop if we fins a back arc.." should be "...stop if we find a back arc...": FOUND(2004-9-28): rvan058.
p138: Example 5.23 should refer to "Figure 5.15": FOUND(2004-08-26): rvan058.
p145, in Note: "If the digraph strongly..." should be "If the digraph is not strongly...": FOUND(2004-09-06): rvan058.
p150, Dijkstra2 pseudocode: colour[v] should be colour[x]. Also there is an "x" in the wrong font: FOUND(2004-07-20): tjoh018.
p159, Prim pseudocode: colour[v] should be colour[x], and t_2 should be temp: FOUND(2004-07-20): tjoh018. (NIL to NULL)
p160, sec 6.6: "ow degree polynomial" should be "low degree polynomial": FOUND(2004-09-15): rvan058.
p168, Def 7.4: font of the "s" in "(words)" needs fixing: FOUND(2004-08-11): dsta029.
p183: "d(a,0)=e" should be "d(a,0)=b": FOUND(2004-11-02): nbar043.
p191, 8.4 para 3. "Convention has it that multiplication" should be "multiplications": FOUND(2004-10-25): xwan158.
p201, last para, "a cell symbols from..." should be "a cell a symbol from..": FOUND(2004-10-25): xwan158.
p241, line 9: "...we wish to prove that *the* exists some constant..." should be "...there exists...": FOUND(2004-11-04): dsmi100.
p241, para -2: the 4th root of 16 should be 2. FOUND(2004-07-31): rvan058.
p243, "as log_2 = lg" should be "as also is log_2 = lg": FOUND(2004-07-31): rvan058.
p252: merge index items "perfect hash function" and "perfect hash functions".