Reference no: EM132264397

Question 1.
(a) Textbook Exercise 11.2-2 (page 261). Just write down your final result.

(b) Textbook Exercise 11.4-1 (page 277). For each method, just write down your final result.

Question 2.
Consider the AVL-tree T as shown in Fig. 1 below, where the numbers are the keys stored.
(a) Copy the tree in your write-up, and for each node v label the height of the subtree rooted at v. (We define the height of a null node to be 0 and the height of a leaf to be 1). Verify that this is indeed a valid AVL-tree.

(b) Suppose now we insert a key 19 to the tree T, and then insert another key 4 to T. For each insertion, show the resulting tree right after the insertion (i.e., before any re-balancing), and the tree after each structural change during re-balancing, as well as the final tree.

(c) Ignoring the insertions in part (b), suppose we delete the key 14 from the tree T as shown in the figure. We use the policy that when an internal node with no null child is deleted, we replace the deleted key with its successor key in the tree whenever the successor key is available. Show the tree right after the deletion (i.e., before any re-balancing), and the tree after each structural change during re-balancing, as well as the final tree.

Figure 1: The AVL-tree for Question 2.

Question 3.

Show the results of deleting keys 18, 15, 13, in that order, from the (2,4)-tree shown in Fig. 2 below

(where the numbers shown are the keys stored), using the one-pass top-down deletion algorithm of B-trees as discussed in class and described in the Textbook pages 500-502.) Note that for both the transfer and the fusion operations in Step 3a and Step 3b, if the immediate left and right sib-lings are both available for the operation, we use the policy of always using the left sibling. For each deletion, show the tree after each structural change and the final tree, and also state the case number being applied.

(Note: 5 points for each deletion.)

Figure 2: The (2,4)-tree for Question 3.

Question 4. Textbook Problem 11-2 (page 283, slot-size bound for chaining).

Do every part but skip part (d). However, assume the results of part (d) to do part (e), i.e., assume that some constant c > 1 exists such that Qko < 1/n³ for k₀ = c lg n/ lg lg n and that P_k < 1/n² for all k > k_o (and of course k < n).

Hints:
1. You may find the following Bool's inequality (as discussed and proved in class) useful: Let A_i be an event for i = 1, 2, ...., n. Then Pr{A₁ U A₂ U ..... U A_n} ≤ ∑ⁿ_i=1 Pr {Ai}.

2. For part (c), first show that Q_k < 1/k!, (by arguing that (1 - 1/n)^n-k < 1 and so on), and then apply Stirling's approximation on k!. You do not need to prove Stirling's approximation.

3. For part (e), observe that

E[M] = ∑ⁿ_x=0 x Pr{M = x} = ∑_x≤t x Pr{M = x} + ∑ⁿ_x>t x Pr{M = x},

where ∑_x≤t x Pr{M = x} is related to Pr{M ≤ t} and ∑ⁿ_x>t x Pr{M = x} is related to Pr{M > t}, for any t  ∈ (0, n). Compare with the E[M] formula to be proved and choose a suitable value for t. Finally, use this E[M] formula and the results of part (d) as stated above to derive the O() bound for E[M].

Question  5.

Textbook Problem 18-2 (page 503, joining and splitting 2-3-4 trees).
(Notes: 4 points for (a), 6 points for (b), 10 points for (c), and 7 points for (d).)