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 _________.
A
5
B
6
C
7
D
8
       Algorithms       Searching       Gate 2017 set-01
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(log2 31) = 4.954196310386876 ⇒ here we are using ceiling so it becomes 5
Question 2
A
It will run into an infinite loop when x is not in listA.
B
It is an implementation of binary search.
C
It will always find the maximum element in listA.
D
It will return −1 even when x is present in listA.
       Algorithms       Searching       Gate 2014 Set -03
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.
Question 3
 
A
n
B
n-1
C
2n
D
       Algorithms        Searching       Gate-2002
Question 3 Explanation: 
Question 4
Which one of the following statements is false?
A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find converted 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.
       Algorithms       Searching       Gate-1994
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.