The Gateway to Computer Science Excellence
+4 votes
168 views
Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $’r’$ insertions?

$A)\left ( 1-\frac{N}{k} \right )^{r}$

$B)\left ( 1-\frac{k}{N} \right )^{r}$

$C)\left ( 1+\frac{N}{k} \right )^{r-1}$

$D)\left ( 1-\frac{k}{N} \right )^{r-1}$
in DS by Veteran (119k points) | 168 views

3 Answers

0 votes
Option b. Since chaining is used

For 1st insertion  :(N-k) slots will be used  for insertion only  as k  slot to be left unfilled

Similarly for 2nd and 3rd insertion because here in chaining we can use same slot again and again according to hash function there is not chance of collision so (N-k) slot for 2nd 3rd insertion too

Total no of possibility for r insertion =N^r

Therefore probability =(N-k) ^r/N^r
by (145 points)
edited by
0
for 1st insertion N-1 slot left unfilled

right?
0 votes

Here, We are using chaining as a resolution technique so if a collision happens at some place then we will get an extra bucket at that place.

Now here in question, we have N slots and we don't want any insertion in the last K slots, so remaining slots where we can insert value is N-K slots.

First Insertion :

The probability that the first insertion done at N-K slots is, (N-K/N)

 

Second Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) = (N-K/N)^2

 

Third Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N)  * (N-K/N)= (N-K/N)^3

 

so for, rth Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) * ...... r times= (N-K/N)^r

 

So answer is (N-K/N)^r which is nothing but (1-(K/N))^r Option B

by (11 points)
0
Can it be thought like that the probability of filling k slots out of N is k/n right now probability of not filling those k slots would be 1- k/n right now we want only r insertions not more than that so it would be raised to the power r please have a look at this logic is it right
0 votes

Let N=6 , k=2 and r =4;

           

                                                                                            <---------------- k ---------------->

<----------------------------------------------------  N  ---------------------------------------------------->

First insertion :

probability that the last k slot unfilled = 4/6;

Second insertion :

probability that the last k slot unfilled = 4/6*4/6;        [ Since collision resolution is done using chaining]

third insertion:

probability that the last k slot unfilled = 4/6*4/6*4/6;

fourth insertion 

probability that the last k slot unfilled = 4/6*4/6*4/6*4/6;

i.e. probability that the last k slot unfilled after 4th insertion is = (4/6)^4;

     probability that the last k slot unfilled after rth insertion is = (N-k/N)^r;

                                                                                                         = (1 - k/N )^r;

Option B

 

by (483 points)

Related questions

+2 votes
0 answers
4
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,324 answers
198,405 comments
105,169 users