Algorithm ADA made easy

Question

consider the following keys that are hashed into table in the order using giving hash function h(i)=(2i+5)mod11

12,44,13,88,23,94,11,39,20,16,5 Assume hash tables has locations from 0to 10.If hash table uses chaining to handle the collisions what is the probability of new elements'x' fit inside hash table without any collision

I am getting answer 0.5

Answer 1

The numbers will be hased as:

12 => 7

44 => 5

13 => 9

88 => 5

23 => 7

94 => 6

11 => 5

39 => 6

20 => 1

16 => 4

5 => 4

Hence, Slots that would be occupied will be (1, 4, 5, 6, 7, 9).

So the required probability= 5/11 = 0.45

Comments

This is the solution provided by ME so i wanted to check if my approach was correct or not

---

No, I think the answer should be 0.45 only and not 0.2 as given by ME.

It is asked to find out the probability that a new element fits inside the hash table without any collision.

So, Probability= No. of free slots/Total number of slots

       Probability= 5/11 = 0.45

What do you think?

---

^ u r right .....

---

@shivangi acc 2 given solution what ll b " probability that a new element fits inside the hash table with collision."= 1-1/5=4/5 ...... does it making any sense ?/

Answer 2

Yep i think 0.45 is correct