ISRO CS 2019 : Algo Booster Quiz 1 (App update required to attempt this test) for GATE & PSU CS Exams

Question 1

Consider an array with "n" elements . All elements are integers and distinct in this array. In array , upto some place X , the elements are in increasing order and after that X , elements are in decreasing order.
Example array : Here X is 30

What is the time complexity to find X in the array :

Question 2

You are been provided with 2 matrices each of size m x m O=

and P=

, then find out the matrix multiplication of these two matrices and the time complexity for the matrices multiplication

Question 3

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

Question 4

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is

Question 5

Consider a binary skew heap tree. This skew heap is same as ordinary heap tree with just one change that skew heap tree doesn’t need to be balanced. Consider the following statements :
I. Insertion time in skew heap = O(logn)
II. Insertion time in skew heap = O(n)
III. Merging two skew heaps take less time than merging two ordinary heaps.
IV. Merging two skew heaps take more time than merging two ordinary heaps.

Question 6

Consider a hash table of size 10 in which linear probing is used to avoid collisions. The hash function used is HF(key)%10 . Now consider the following hash table after insertion of these keys : 42,23,34,52,46,33 not necessarily in same order.

Find the number of input sequences possible that results in same hash table as above.

Question 7

Consider the modified quicksort in which (n/10)^Th Element in the array is selected as pivot element for the first time and afterwards follows the normal procedure for selecting the pivot element. What is the worst-case time complexity of this quick sort to sort the given array?

Question 8

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Question 9

Load the keys 23, 13, 21, 14, 7, 8, and 15 in this order, in a hash table of size 7 using quadratic probing with

the hash function h(key) = key % 7.
[Note: The required probe sequences are given by:

How many collisions can occur in the hash table?

Question 10

Consider the following recurrence relation :

If the input n is not of the form 2^k , then what is the value of above recurrence relation.