[DGW2009] textbook 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 early 2009). Errors and corrections will be listed here as they are found. Errors may be typographical or factual. The lecturers' decision on what constitutes an error is final and not subject to appeal.

When reporting errors by email (to one of the textbook authors), 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 1, 2009) found by Andre Nies

• p9, last paragraph: 'The above "brute-force"...' should be 'The (below) "brute-force"...' (Figure 1.2)
• Ex3.24: The hash function should be floor(k/10).
• p119. line 9: 'edged' should be 'edge'
• p134: Disjoint sets and union-find not described in Section D1.

Errors and corrections (Semester 2, 2009)

• p70. ...that they ``wrap around'' the array when *the*-*they*; found (Nov 11, 2009):esoh002
• p77. 2nd paragraph: "exists a that maps" -- "exists a *function* that maps"; Found (Nov 11, 2009):esoh002
• p90+p241, Exercise 4.2.4: the textbook solution is given in matrix representation while the question asks for adjacency lists. Found (Oct 21, 2009):vjon018.
• p98, Exercise 5.2.1: `visit can' should be `can visit'. Found (Oct 19, 2009):bdow009.
• p181, selectionSort: if (a[posMin] ≥ a[k]) posMin=k; Found (Oct 29, 2009):mwil392.

Errors and corrections (Semester 2, 2010)

• p13 Defn 1.7 "at most as fast" -> "at least as fast". Found (2010-09-09) rpar074.
• p34 bottom: "list size 1" -> "lists of size 1". Found (2010-11-09) jtim017.
• p65 line 3: extra right parenthesis. Found (2010-11-09) jtim017.
• p77 Division subheading: q(k,m) should have m, not n, in definition. Found (2010-11-09) jtim017.
• p98, Exercise 5.2.2: "starting a a root" -> "starting at a root". Found (2010-11-09) jtim017.
• p183 QuickSort comments: "CUROFF" -> "CUTOFF". Found (2010-09-14) kpra032.
• p198 para 2: "safe guard" -> "safeguard". Found (2010-11-07) kkim087.

Errors and corrections (Semester 1, 2012)

• p37: Replace nT(n)=(n+1)T(n-1)+c{2n+1}/{n(n+1)} with nT(n)=(n+1)T(n-1)+c(2n-1). Found 22-May-2012 by Ulrich Speidel.
• p39. The partitioning algorithm "R starting at the end" -> "R starting at the end index plus one". Found (2012-03-29) tkim021. Note the until loops first execute the increment/decrement instructions before testing the conditionals.
• p54, Table 3.1: "District Columbia" -> "District of Columbia"; "Rheinland Pfalz" -> "Hesse". Found by Ulrich Speidel.
• p59, Exercise 3.2.2: Sample solution assumes n=10^6. Found (10-May-2012) mcha174 and (13-May-2012) htir002.
• p71: "...table in Figure 3.3" -> "in Table 3.3". Found pgup014.
• p89 line 3. Default vertex labels are usually 0,1,...,n-1.
• p182 in comment: "quckselect" -> "quickselect". Found kaun017.
• p228 Solution to Exercise 1.3.3: "...iff there exist" -> "iff there exists". Found kaun017.

Errors and corrections (Semester 2, 2012)

• p11 line 3 of Example 1.5: Swap symbols < and ≤ (twice). Found mhar263.
• p118. Q.peek() should be Q.pop(). Found (05-Oct-2012) by David Welch.
• p131. S_m should be S_k in the proof of Theorem 6.12. Found (05-Oct-2012) by David Welch.