University of Oxford Logo University of OxfordDepartment of Computer Science - Home
Linked in
Linked in
Follow us on twitter
Twitter
On Facebook
Facebook
Instagram
Instagram

Algorithm Design with Haskell: Errata (as of 2nd January 2021)

If you have any more corrections, please send them to adwh@cs.ox.ac.uk!

Page 39, Exercise 2.8:

The second equation for the recurrence relation should read T(m,n) = T(m-1,n) + Θ(n)

Thanks to Nickolay Shapovalov for spotting this.

Page 58, Answer 3.14:

The 10 should be n.

Thanks to Kei Hibino for spotting this.

Page 82, line 23:

The sentence should read "Thus, combining the two sets gives back the original set, though not necessarily the same tree." The following two sentences should be deleted.

Thanks to Mo Jia for spotting this.

Page 89, Answer 4.9:

We should set (ys,zs) = partition p xs.

Thanks to Kei Hibino for spotting this.

Page 100, line 4:

The blank line should read [1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 4, 6]

Page 127, line 23:

Delete the "-1" in the inequality. This should also be changed in Exercise 6.10 (p136). Answer 6.10 (p138) also needs correction: the "-1"s in the first condition should be deleted; the final hint should be "arithmetic, and rule of floors"; the final condition should be k ≤ floor((n+9)/10); and the conclusion floor((ceiling(n/5)+1)/2) = floor((n+9)/10) ≥ n/10 Back on p127, the recurrence really should not ignore floors and ceilings, and its analysis is consequently more involved than the text implies.

Thanks to Nickolay Shapovalov for spotting this.

Page 136, Exercise 6.10:

See p127.

Page 138, Answer 6.10:

See p127.

Page 161, last line:

The final x should be xs, so the right-hand side reads minWith cost (map (gstep x) (candidates xs))

Page 198, line 21:

Insert "and delete" between "find" and "a smallest".