## Searching

Question 1 |

Let *A* be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index *i* such that *A[i]* is 1 by probing the minimum number of locations in A. The *worst case* number of probes performed by an *optimal* algorithm is _________.

5 | |

6 | |

7 | |

8 |

Question 1 Explanation:

→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.

→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.

So number of probes = ceil(log

⇒ here we are using ceiling so it becomes 5

→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.

So number of probes = ceil(log

_{2}31) = 4.954196310386876⇒ here we are using ceiling so it becomes 5

Question 2 |

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
= n-1; do {
k = (i+j)/2;
if (x <= listA[k]) j = k-1;
if (listA[k] <= x) i = k+1;
}while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?

It will run into an infinite loop when x is not in listA. | |

It is an implementation of binary search. | |

It will always find the maximum element in listA. | |

It will return −1 even when x is present in listA. |

Question 2 Explanation:

From the above code, we can identify

k = (i+j)/2;

where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.

So it is an implementation of Binary search.

k = (i+j)/2;

where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.

So it is an implementation of Binary search.

Question 4 |

Which one of the following statements is false?

Optimal binary search tree construction can be performed efficiently using dynamic programming. | |

Breadth-first search cannot be used to find converted components of a graph. | |

Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed. | |

Depth-first search can be used to find connected components of a graph. |

Question 4 Explanation:

In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.

There are 4 questions to complete.