Algorithms MCQ - Algorithm Design Techniques
If new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive a new record. the probability is 6/10 (as 10 is total possible number of locations).
We can verify that the 1st, 3rd, 5th, 7th ... probes check at location 5.
2nd, 6th, 10th ... probes check at location 8.
4nd, 8th, 12th ... probes check at location 4.
Rest of the address space will never be probed.
If there is only one record, then
Probability of collision = 1/100
If there are two records,
then Probability of collision = 2/100
and if there are 9 records,
then Probability of collision = 9/100.
∴ Required probability = 
= 0.45
= 0.45- A Optimal binary search tree construction can be performed efficiently using dynamic programming
- B Breadth-first search cannot be used to find connected components of a graph
- C Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed
- D Depth-first search can be used to find connected components of a graph
BFS and DFS both algorithm are used to find
connected component of graph in linear time.
