Awesome q2a theme
0 votes
8 views

https://gateoverflow.in/57653/cormen-2nd-edition-exercise-11-2-1

WHY WE CANT DO LIKE THIS …...NUMBER OF COLLISIONS(X) : 0        1        2          3       4    …………………...N-1

                                                                                                   P(X):   0/M   1/M    2/M…………………… … ………….(N-1)/M

 

                                                         

ago in DS by (25 points) | 8 views
0

WHY WE CANT DO LIKE THIS 

You can, but to get the expected value you would have to multiply them and sum them up.

0
ya i am multiplying them and doing their sum  but see the approach it is different …..they are multiplying by 1 every time ...
0

Ok, I think I know what’s wrong here, the value of probability you are calculating is the probability of collision at nth insertion, not the probability of exactly k collisions.

0
ya exactly ...but how will it happen if i do like i am thinking ? and why 1 is multiplied every time in the solution?
0

how will it happen if i do like i am thinking

Then you would have to calculate the probability of exact k collision and multiply it with k, and what I’ve looked online this is not easy.

0
ok it is  difficult…..so can u please explain what is the meaning of multiplying by 1 in each term? not able to relate with concept of expectation ...
0

Maybe it’s because the number of new collision that may have occurred at kth collision is 1, and the probability of collision at kth insertion is k-1/m.

So expected value of new collision = $1 \times \frac{k-1}{m}$

We want the expected value of collisions when n values are hashed into the table, so we can just sum them up $$\sum_{k=1}^{n}\frac{k-1}{m}$$ to get the expected number of collisions as expected value of the sum of several random variables is equal to the sum of their expectations.

0
ok thank u for efforts…..

Please log in or register to answer this question.

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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,953 questions
3,113 answers
14,322 comments
95,780 users