\$35.00

Category:

## Description

1. Hash Table Probabilities (3 points)

1. (1 point) Suppose 2 keys are inserted into an empty hash table with m slots. Assuming simple uniform hashing, what is the probability of:

1. exactly 0 collisions occurring

1 chance of no collision on rst insertion and (m 1)=m chance on second insertion, so probability of 0 collisions is mm 1

1. exactly 1 collisions occurring

1 chance of no collision on rst insertion and 1=m chance of only collision on second insertion, so probability of 1 collision is m1

1. (2 points) Suppose 3 keys are inserted into an empty hash table with m slots. Assuming simple uniform hashing, what is the probability of:

1. exactly 0 collisions occurring

1 chance of no collision on rst insertion, (m 1)=m chance on second

insertion, and (m 2)=m on third insertion, so probability is 1 mm 1

m 2 = m2 3m+2

m m2

(b) exactly 1 collisions occurring

1 chance of no collision on rst insertion, now two cases of only collision occurring, either on second or third insertion. Chance of collision on second and not on third is 1 m1 mm 2 = mm22 . Chance of collision on third but not on second is 1 mm 1 m2 = 2mm2 2 . Total

chance of 1 collision is m 2 + 2m 2 = 3m 4

m2 m2 m2

1. exactly 2 collisions occurring

1 chance of no collision on rst insertion, 1=m chance of rst collision

on second insertion, and 2=m chance of second collision on third insertion so probability of 2 collisions is 1 m1 m2 = m22

1. Red-Black Trees (2 points)

1. Company X has created a new variant on red-black trees which also uses blue as a color for the nodes. They call these \red-black-blue trees”. Be-low are the new rules for these trees:

Every node is red, blue, or black. The root is black.

Every leaf (NIL) is black.

If a node is red, then both its children are black.

If a node is blue, then both its children are red or black.

For each node, all simple paths from the node to descendant leaves con-tain the same number of black nodes.

1. (2 points) In class we found that the height, h, of a red-black tree is 2 log2(n + 1) (where n is the number of keys). Find and prove that a similar bound on height of the red-black-blue trees.

(Hint: You can use the same approach as we did to show h 2 log2(n + 1)).

The number of nodes that are black on any simple path from the root to a leaf is at least h=3 implied by property 4 and 5. It can be shown that a subtree rooted at any node x contains at least 2bh(x) 1 internal nodes. Using the root of the tree as x we know that the num-ber of nodes n 2h=3 1 ! n + 1 2h=3 ! log2(n + 1) h=3 ! 3 log2(n + 1) h. Thus h 3 log2(n + 1)

1. (0 points – just for fun) Adding an additional color didn’t seem to improve our bound on h (i.e., 3 colors allows the tree to become more unbalanced than with 2 colors). What bene t might we get from the extra color?

Insertion would be easier and run in O(1) time since it would only re-quire a change in color to complete the insertion rather than O(log(n))

1. B-trees (4 points)

1. (2 points) Show the results of inserting the keys E; F; G; U; V; W; H

in order into the B-tree shown below. Assume this B-tree has minimum degree k = 2. Draw only the con gurations of the tree just before some node(s) must split, and also draw the nal con guration.

 M B,D,J O,Q A C I K,L N P R,S,T M B,D,J O,Q A C E,F,G,I K,L N P R,S,T M B,D,F,J O,Q A C E G,I K,L N P R,S,T D,M B F,J O,Q A C E G,I K,L N P R,S,T,U D,M B F,J O,Q,S A C E G,I K,L N P R T,U,V,W D,M B F,J O,Q,S,U A C E G,I K,L N P R T V,W D,M,Q B F,J O S,U A C E G,H,I K,L N P R T V,W

1. (2 points) Suppose you have a B-tree of height h and minimum degree k. What is the largest number of keys that can be stored in such a B-tree? Prove that your answer is correct.

(Hint: Your answer should depend on k and h. This is similar to theorem we proved in the B-tree notes).

 level num nodes num keys 0 1 2k 1 1 2k 2k(2k 1) 2 (2k)2 (2k)2(2k 1) . . . . . . . . . h (2k)h (2k)h(2k 1)

This table shows the maximum number of keys for a B-tree of degree k and height h at each given level. Summing the keys gives:

h h

X(2k)i(2k 1) = (2k 1) X(2k)i

i=0 i=0

• (2k 1)(2k)h+1 1 2k 1

• (2k)h+1 1

So the maximum number of keys in the given B-tree is (2k)h+1 1.

4. Choose Function (4 points)

Given n and k with n k 0, we want to compute the choose function using the following recurrence:

n

k

 0 n n 1 n 1 0 Base Cases: n = 1 and n = 1, for n n , for n > k > 0 Recursive Case: k = k 1 + k (1) (1 point) Compute 35 using the above recurrence. 3 ! = 2! + 3 ! 5 4 4 2! + 3! = 1! + 2! + 3 3 3 3 1! + 2! + 1 = 0! + 1! + 1! + 2! + 2 2 2 0! 2 1! 2 2 1! = 1 + 0! + 1! + + + 1 + 0! + + 1 + 1 1 1 1 1 1 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

• 10

1. (2 points) Give pseudo-code for a bottom-up dynamic programming

algorithm to compute nk using the above recurrence.

Algorithm 1 int choose(int n, int k)

1. C[n + 1][k + 1];

1. for i = 0 to n do

1. j = 0;

1. while j i and j k do

1. if j == 0 or j == i then

1. C[i][j] = 1;

1. else

1. C[i][j] = C[i 1][j 1] + C[i 1][j];

1. end if

1. j + +;

1. end while

1. end for

1. return C[n][k];

1. (1 point) Show the dynamic programming table your algorithm creates

 for 5 . 3 0 1 2 3 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 5 1 5 10 10