$35.00
Description

Hash Table Probabilities (3 points)


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




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 ^{m}_{m} ^{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 _{m}^{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:




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 ^{m}_{m} ^{1}
m 2 _{=} m^{2} 3m+2
m m^{2}
(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 _{m}^{1} ^{m}_{m} ^{2} = ^{m}_{m}_{2}^{2} . Chance of collision on third but not on second is 1 ^{m}_{m} ^{1} _{m}^{2} = ^{2m}_{m}_{2} ^{2} . Total
chance of 1 collision is ^{m} ^{2} + ^{2m} ^{2} = ^{3m} ^{4}
m^{2} m^{2} m^{2}




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 _{m}^{1} _{m}^{2} = _{m}^{2}_{2}

RedBlack Trees (2 points)


Company X has created a new variant on redblack trees which also uses blue as a color for the nodes. They call these \redblackblue trees”. Below 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 contain the same number of black nodes.

(2 points) In class we found that the height, h, of a redblack tree is 2 log_{2}(n + 1) (where n is the number of keys). Find and prove that a similar bound on height of the redblackblue trees.
(Hint: You can use the same approach as we did to show h 2 log_{2}(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 2^{bh(x)} 1 internal nodes. Using the root of the tree as x we know that the number of nodes n 2^{h=3} 1 ! n + 1 2^{h=3} ! log_{2}(n + 1) h=3 ! 3 log_{2}(n + 1) h. Thus h 3 log_{2}(n + 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 require a change in color to complete the insertion rather than O(log(n))

Btrees (4 points)


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

in order into the Btree shown below. Assume this Btree 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

(2 points) Suppose you have a Btree of height h and minimum degree k. What is the largest number of keys that can be stored in such a Btree? Prove that your answer is correct.
(Hint: Your answer should depend on k and h. This is similar to theorem we proved in the Btree 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 Btree 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 Btree 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
_{3}^{5} 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

(2 points) Give pseudocode for a bottomup dynamic programming
algorithm to compute ^{n}_{k} using the above recurrence.
Algorithm 1 int choose(int n, int k)

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

for i = 0 to n do

j = 0;

while j i and j k do

if j == 0 or j == i then

C[i][j] = 1;

else

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

end if

j + +;

end while

end for

return C[n][k];


(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