DATA STRUCTURE AND ALGORITHM. ASAP. Please answer completely ! Please answer onl

Question

DATA STRUCTURE AND ALGORITHM.

ASAP. Please answer completely ! Please answer only if the answer is correct, will give thumbs up for correct answers only! thank u

Consider the Boolean matrix method for constructing universal hash functions. Suppose that there are 16 buckets and keys are of 6 bits.

We are given keys x = [0,1,1,0,1,0] and y = [1,1,0,0,1,1].

i. Does the hash function h1 collide on x and y? How about h2?

ii. Consider any hash function h in the family. Consider the first column c of this function. It has 4 bits. Assume that a key has its first bit set to 1. Show that by changing the bits in column c alone, we can span all the 16 slots in the hash table.

iii. Use the above fact to show that the probability of hash functions colliding on the key pair is 1/16.

Explanation / Answer

i)

NO,
Reason: the multiplication picks out the columns of h1 corresponding to where the data has a one and then does a bitwise addition or exclusive or.
For example,let z=1011
( 0 1 0 0 )(1) (0)
h1(z)= ( 1 0 1 1 )(0) = (1)
( 1 1 0 1 )(1) (0)
(1)
picks out the first, third and fourth columns of h1 and adds or exclusive ors them together:
( 0 + 0 + 0 ) (0)
( 1 + 1 + 1 ) = (1)
( 1 + 0 + 1 ) (0)

For h2 as well there will be no coliision.

ii)

we first choose all of h but the ith column. Over the remaining choices of ith column, h(x) is fixed. However, each of the 16(24) different settings of the ith column gives a different value of h(x) (in particular, every time we flip a bit in that column, we flip the corresponding bit in h(x)).

iii)

Now, take an arbitrary pair of keys x, y such that x 6= y. They must differ someplace, so say they differ in the ith coordinate and for concreteness say x[i] = 0 and y[i] = 1

Imagine we first choose all of h but the ith column. Over the remaining choices of ith column, h(x) is fixed. However, each of the 16 different settings of the ith column gives a different value of h(y) (in particular, every time we flip a bit in that column, we flip the corresponding bit in h(y)). So there is exactly a 1/16 chance that h(x) = h(y). .

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.