The Gateway to Computer Science Excellence
+1 vote
236 views
Suppose you have a hash table that can hold $100$ elements. It currently stores $30$ elements (in one of $30$ possible different locations in the hash table).  The probability that your next two inserts will cause at least one collision is  ( by assuming a totally random hash function)   __________
in Programming by Veteran (75k points)
edited by | 236 views
+1
We need to round off till 2 decimals ..

0.5170 is taken as wrong answer :(

2 Answers

+8 votes
Best answer

Second Method to solve this problem :-
3 cases are possible when we insert 2 elements in hash table

Case 1- Collision on First insertion and Not Collision on Second Insertion

            P(case-1) = (30/100)* (69/100) = 0.207

Case 2- Not Collision on First insertion and Collision on Second Insertion

            P(case-2) = (70/100)* (31/100) =0.217

Case 3- Collision on both First insertion and Second Insertion

       P(case-3) = (30/100)*(31/100) = 0.093

Finally,

 Required Probability = P(Case-1) or P(Case-2) or P(Case-3)

                              =0.207 + 0.217 + 0.093 = 0.517

Note - This method is only efficient when number of insertion is less.

by Active (1.1k points)
selected by
0

@ShiveshRoy @Bikram shouldnt it be 30/100 and 30/100 for collision on first insertion means that we are hasihng to one of the 30 possible options and 2nd time collision also means that we are hashing again to one of these 30 slots ... pls explain ..

+5 votes
1-p0 = 1- (70/100 * 69/100 )
by Veteran (75k points)
0

sir can you please explain further

i think possibility of collision as follow > atleast one collision means one or two collision are possible

for 1 collision > first insertion cause collision or second insertion cause collision

                     =  30/100    or     31/100

for 2 collision > (30/100)*(31/100)

ans will (30/100  +  31/100 +  (30/100)*(31/100))

is this correct way?

+2

If you have a hash table with M slots and N keys to insert in it, then the probability of at least 1 collision is:

(Probability of Collisions) P  N M = 1 -  P N M  (Probability of no cillision)

= 1 - ( 70/100  *  69/100 ) 

= 0.5170

+1

sir i get it from your comment

can you give same answer without complement form (1-P), i asked bcoz number of insertion is less(2)

+1

actually this is the rule , please read this slide

https://cseweb.ucsd.edu/classes/sp15/cse100-ab/lectures/Lec18_ann_DM.pdf

slide number 12 and 13

+3

@Manoj_Kumar you can solve this way using your approach :

For that 3 cases are possible 

Case 1- Collission on First insertion and Not Collision on Second Insertion

            P(case-1) = (30/100)* (69/100) = 0.207

Case 2- Not Collission on First insertion and Collision on Second Insertion

            P(case-2) = (70/100)* (31/100) =0.217

Case 3- Collission on both First insertion and Second Insertion

       P(case-3) = (30/100)*(31/100) = 0.093

Finally,

 Required Probability = P(Case-1) or P(Case-2) or P(Case-3)

                              =0.207 + 0.217 + 0.093 = 0.517

0
But this is little bit lengthy approach to solve the problem
+1
@shivesh

very good solution, if possible write this as an answer . Good solve.
0
Sure @Bikram Sir..
0
@ShiveshRoy sir please clarify my doubt in your solution. If chaining is used for collision resolving (instead of probing) then won't the cases give different answer? ex case1 : (30/100)*(70/100) because there will still be 70 free slots after the 1st collision. Likewise for the other cases.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,405 answers
198,628 comments
105,467 users