Problems for talk on "Dynamic Range Reporting in One Dimension"
1) van Emde Boas: Most hash tables work on keys of a fixed number of
bits, whereas the vEB data structure needs to hash variable-length
prefixes of keys.
Explain how to convert variable length keys of length at most w into
distinct fixed length keys of length 2w (or better).
2) New data structure: Argue that the query time for FindAny(a,b)
can be improved slightly from O(log log w) to O(log log (w-lcp(a,b))),
where lcp(a,b) is the length of the longest common prefix of a and b.
Hint: Argue that only the O(log(w-lcp(a,b))) tries of lowest order need
to be searched.
3) Extra credit (hard): Improve the answer from the last question to
expected time O(log log log(b-a)).