Errata

Problem 2

The problem statement contains the following errors:

  1. The sentence “add a new interval p’ to P with p’.first = p.count …” is wrong. The correct version is: “add a new interval p’ to P with p’.first = p.first + p.count …”.
  2. The final value of A is <0|->22, 1|->33, 2|->100, 3|->11, 4|->44, 5|->55>.
  3. Task 1a should read “For any i < N, P’(F’(i)) is an interval containing i” (that is, use F’ instead of F).

Moreover, the check “If i < p.first + p.count then x has already been processed so the state is left unchanged.” is unnecessary.

Problem 3

In lookup ,  ”h[i−1]” should be “log[i - 1].

Leave a Comment