DS+ Algorithm test

Question

Comments

a will ans ?

---

Yes A is the answer. It would be helpful if you show the hash table with calculations.

---

Here load factor $\large \alpha =\frac{n}{m}$

                        $\large \alpha =\frac{8}{11}$

The expected number of probes in an unsuccessful search is at most $\large \frac{1}{1-\alpha }$

So $\large \frac{1}{1-(8\div 11) }$=3.6

The expected number of probes in a successful search is at most=$\large \frac{1}{\alpha }ln\left ( \frac{1}{1-\alpha } \right )$

So put $\large \alpha =\frac{8}{11}$ you will get 1.6.

For reference:http://web.mit.edu/16.070/www/lecture/lecture_18.pdf

Go to last page.

---

manoj they are assuming uniform hashing....is both things are same

---

Manoj your answer is correct but it is only a co-incident, i guess. Bcoz here we are given the input and for that we have to check. What you have done is counted average which can change for different input. Anyway it would be helpful if you could explain the method in answer key.

---

Yes you are correct.

We generally use above aproach when input is not specified.

However in your example i am unable to interprate the meaning of A,B...Z.

---

@Manoj, here we will be hashing the key and storing the data. But i am not able to understand solution in key. If locations are given as T[1]-T[11] then how will they stored. I mean A has key 4 then it will be stored in T[5] or [4] and what is unsucessfull probe for each key?

---

That is what i am saying once you know value attached with A then you can easily find number of probes in searching A.But here i am unable to figure out what is value attached with A.

Answer 1

First of all do the normal hasihng table. Remember search will be succesfull only if you are hased to any one of the * record in table.

Therefore, No of succesfull probes=Total no of probes for each of the record / Total records in table=13/8=1.6

we can be hashed to any of the entry and still we can have a unsuccesfull search,

Therefore No of probes for unsuccesfull search=

Total no of probes from each hash value to make a unsuccesfull search / Total capacity of table

=(8+7+6+5+4+3+2+2+3)/11=3.6

Comments

please explain unsuccessful probe calculation sir

---

how unsuccessful probe calculated?

---

shed some light on unsuccessful search :(