Reference no: EM1373332

1. Early printings of CLRS3 say on pages 546-547 "we treat min and max differently: the element stored in min does not appear in any of the clusters, but the element stored in max does." This is not true (they may have corrected it in later printings)-what that sentence should say is "we treat min and max differently: the element stored in min does not appear in any of the clusters, but unless the vEB tree contains just one element (so that the minimum and maximum elements are the same), the element stored in max does." Rewrite the code for vEB-Empty-Tree-Insert, vEB-Tree-Insert, and vEB- Tree-Delete so that indeed, max does not appear in any of the clusters, just as min does not appear in any of the clusters.

2. Problem 20-1, parts (a) and (b) only, on page 557. In part (b), be careful that you do not get snagged by the pitfall described in the middle of page 86 of CLRS3. (Hint : For part (b), can you prove, under reasonable assumptions, that P(u) = u - 2?) Do not do parts (c)-(g); instead, do the following replacement for part (c):

(c) We can store all of the array-of-pointers substructures in a single array outside the vEB tree itself. This would change the recurrence (20.5) to

P(u) = (√u + 1)P(√u) + O(1).

Solve this recurrence. Does this idea improve the vEB structure?

3. Consider the "dynamic range minimum query problem." Let S ⊆ U = {0, 1, 2, . . . , u-1}. Each s ∈ S is labeled with a real number v(s). We need to maintain a data structure on S that supports the following operations:

• initialize(S): Construct and initialize the data structure for S.
• decreaseKey(s, x): If x < v(s), change v(s) to x; otherwise, do nothing.
• minimum(x): Return min{v(s)|s ∈ S, s ≤ x}.

Show how a vEB tree can be used to support these three operations. Analyze the time/space complexity of your algorithms.