Skip to content

20.2 A recursive structure

20.2-1

Write pseudocode for the procedures $\text{PROTO-vEB-MAXIMUM}$ and $\text{PROTO-vEB-PREDECESSOR}$.

See the two algorithms, $\text{PROTO-vEB-MAXIMUM}$ and $\text{PROTO-vEB-PREDECESSOR}$.

20.2-2

Write pseudocode for $\text{PROTO-vEB-DELETE}$. It should update the appropriate summary bit by scanning the related bits within the cluster. What is the worst-case running time of your procedure?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
PROTO-vEB-DELETE(V, x)
    if V.u == 2
        V.A[x] = 0
    else
        PROTO-vEB-DELETE(V.cluster[x.high], x.low)
        inCluster = false
        for i = x.high * sqrt(u) to (x.high + 1) * sqrt(u) - 1
            if PROTO-vEB-MEMBER(V.cluster[x.high], i)
                inCluster = true
                break
        if inCluster == false
            PROTO-vEB-DELETE(V.summary, x.high)

When we delete a key, we need to check membership of all keys of that cluster to know how to update the summary structure. There are $\sqrt u$ of these, and each membership takes $O(\lg\lg u)$ time to check. With the recursive calls, recurrence for running time is

$$T(u) = T(\sqrt u) + O(\sqrt u\lg\lg u).$$

We make the substitution $m = \lg u$ and $S(m) = T(2^m)$. Then we apply the Master Theorem, using case 3, to solve the recurrence. Substituting back, we find that the runtime is $T(u) = O(\sqrt u\lg\lg u)$.

20.2-3

Add the attribute $n$ to each $\text{proto-vEB}$ structure, giving the number of elements currently in the set it represents, and write pseudocode for $\text{PROTO-vEB-DELETE}$ that uses the attribute $n$ to decide when to reset summary bits to $0$. What is the worst-case running time of your procedure? What other procedures need to change because of the new attribute? Do these changes affect their running times?

We would keep the same as before, but insert immediately after the else, a check of whether $n = 1$. If it doesn't continue as usual, but if it does, then we can just immediately set the summary bit to $0$, null out the pointer in the table, and be done immediately. This has the upside that it can sometimes save up to $\lg\lg u$. The procedure has the big downside that the number of elements that are in the set could be as high as $\lg(\lg u)$, in which case $\lg u$ many bits are needed to store $n$.

20.2-4

Modify the $\text{proto-vEB}$ structure to support duplicate keys.

The array $A$ found in a proto van Emde Boas structure of size $2$ should now support integers, instead of just bits. All other pats of the structure will remain the same. The integer will store the number of duplicates at that position. The modifications to insert, delete, minimum, successor, etc will be minor. Only the base cases will need to be updated.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
PROTO-vEB-DELETE(V, x)
    if V.u == 2
        V.A[x] = 0
    else
        PROTO-vEB-DELETE(V.cluster[x.high], x.low)
        inCluster = false
        for i = x.high * sqrt(u) to (x.high + 1) * sqrt(u) - 1
            if PROTO-vEB-MEMBER(V.cluster[x.high], i)
                inCluster = true
                break
        if inCluster = false
            PROTO-vEB-DELETE(V.summary,x.high)

20.2-5

Modify the $\text{proto-vEB}$ structure to support keys that have associated satellite data.

The only modification necessary would be for the $u = 2$ trees. They would need to also include a length two array that had pointers to the corresponding satellite data which would be populated in case the corresponding entry in $A$ were $1$.

20.2-6

Write pseudocode for a procedure that creates a $\text{proto-vEB}(u)$ structure.

This algorithm recursively allocates proper space and appropriately initializes attributes for a proto van Emde Boas structure of size $u$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
MAKE-PROTO-vEB(u)
    allocate a new vEB tree V
    V.u = u
    if u == 2
        let A be an array of size 2
        V.A[1] = V.A[0] = 0
    else
        V.summary = MAKE-PROTO-vEB(sqrt(u))
        for i = 0 to sqrt(u) - 1
            V.cluster[i] = MAKE-PROTO-vEB(sqrt(u))

20.2-7

Argue that if line 9 of $\text{PROTO-vEB-MINIMUM}$ is executed, then the $\text{proto-vEB}$ structure is empty.

For line 9 to be executed, we would need that in the summary data, we also had a $\text{NIL}$ returned. This could of either happened through line 9, or 6. Eventually though, it would need to happen in line 6, so, there must be some number of summarizations that happened of $V$ that caused us to get an empty $u = 2$ $\text{vEB}$. However, a summarization has an entry of one if any of the corresponding entries in the data structure are one. This means that there are no entries in $V$, and so, we have that $V$ is empty.

20.2-8

Suppose that we designed a $\text{proto-vEB}$ structure in which each cluster array had only $u^{1 / 4}$ elements. What would the running times of each operation be?

There are $u^{3 / 4}$ clusters in each $\text{proto-vEB}$.

  • MEMBER/INSERT:

    $$T(u) = T(u^{1 / 4}) + O(1) = \Theta(\lg\log_4 u) = \Theta(\lg\lg u).$$

  • MINIMUM/MAXIMUM:

    $$T(u) = T(u^{1 / 4}) + T(u^{3 / 4}) + O(1) = \Theta(\lg u).$$

  • SUCCESSOR/PREDECESSOR/DELETE:

    $$T(u) = T(u^{1 / 4}) + T(u^{3 / 4}) + \Theta(\lg u^{1 / 4}) = \Theta(\lg u \lg\lg u).$$