1. Question 1 Given a tree whose head is a pointer r and in which each vertex ha

Question

1. Question 1 Given a tree whose head is a pointer r and in which each vertex has a pointer lef t(x) to the left child and r(x) for the right child. Give an algorithm that finds the number of vertices in the tree that have at least one null (namely not both of its children are there).

2. Question 2: If we use the division methods with m = 2r for some integer r. Why would it be not such a good hash function? On the other hand, say that every key is chosen at random from 0 to n 1 and n. Explain why choosing a prime n is better than a non prime.

3. Question 3: Let h be the multiplicative method with A = 2/9. Show 10 different numbers that are hashed to the same slot. Do it also for the mod function and arbitrary m.

4. Question 4: Give an algorithm for the question if Given two pairwise distinct arrays A and B, are A and B the same array but in different order.

5. Question 5: Say that we have a universal hash function with m = n. But we keep the list sorted. What is the worst running time and expected running time for insert?

Explanation / Answer

Question 3

Two step process

Step 1:

Multiply the key k by a constant 0< A < 1 and extract the fraction part of kA.

Step 2:

Multiply kA by m and take the floor of the result.

The hash function using multiplication method is:

h(k) = [m(kA mod 1)]

where "kA mod 1" means the fractional part of kA, that is, kA - [kA].

Advantage of this method is that the value of m is not critical and can be implemented on most computers.

A reasonable value of constant A is

A=2/9=0.22222

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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