Homework #5 Solution

$35.00

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