Hashing problems

[prasad pisal]

1) A hash table can store a maximum of 10 records.Currently there are records in the location 1,3,4,7,8,9,10.The probability of a new record going into location
2, with a hash function resolving collisions by linear probing is
0.6 or  0.1 or 0.2 or 0.5

2) Consider the hashing function that resolves collision by quadratic probing.Assume the address space is indexed from 1 to 8.which of the following locations
will never be probed if the collision occurs at position 4 ?
4 or 5 or 8 or 2

3) A hash table has space for 100 records.what is the probability of the collision before the table is 10% full?
0.45 or 0.5 or 0.3 or 0.34 ( approximately)

4) You are given a hash table with n keys and  m slots, with the simple uniform hashing assumption (each key is equally likely to be hashed into each slot). Collisions are resolved by chaining. What is the probability that the first slot ends up empty?

[SUYASH GUPTA]

I shall say nice questions... Can you tell me the source of these question and also that I will require a few days to reply to these as some of these topics are out of my touch...

[amol bhangdiya]

1)  For a new record going into location 2, we have 6 slots 7,8,9,10,1,2 as its is by linear probing.
     so probability will be 6/10=0.6

2) Consider hashing function that resolves conflict by quadratic probing as,
    h(k,i) = [ h1[k] +c1*i+ c2*i^2] mod m
    consider c1 as 3 and c2 as 1
    We have first collision at location 4, If we find series of probe with above quadratic probing we get sequence which does not include 5.

4) There are n keys, each key can be mapped to m locations. total sample space=m^n
    For first slot to be empty n keys will be mapped to remaining m-1 locations. 
    required probability = (m-1)^n / m^n

I did not get question 3. Anyone wants to give it a try?