GATE CS 2019 : Algorithm MiniMock Quiz -1 for GATE & PSU CS Exams

Question 1

A recurrence relation is given. On solving this relation the value of

is...

Question 2

What is the least number of comparison operations required to find the minimum and maximum out of 50 numbers?

Question 3

Match the following recurrence relations with their time complexities.
List-I
A)

B)

C)

List-II
1. θ(n log n)
2. O(n log n)
3. θ(n)
4. O(n)
5. O(log₂n)
6.

(n log₂n)

Question 4

Consider the following recursive function of Tower of Hanoi.
T(n) = 2T(n-1) + 1
Find the number of function calls and moves respectively for moving 3 disks.

Question 5

Which among the following problem doesn’t follow the greedy algorithm approach?

Question 6

Consider the following adjacency matrix.

Which of the following is transitive closure of the directed graph defind by the above adjacency matrix.

Question 7

Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in unsuccessful search is 3 then find the expected number of probes in a successful search.

Question 8

The algorithm is given for performing a removal from a hash table that uses linear probing to resolve collisions where we do not use a special marker cto represent deleted elements. That is, we must rearrange the contents of the khash table so that it appears that the removed item was never inserted in the first gplace. Arrange the steps of the algorithm in the correct sequence.
1. incrementally step forward through the table
2. moving back one spot each item k
3. walk through the table until the first item for which the f(k) value differs is encountered.

Question 9

Ram wants to reduce the time complexity of heapsort to

. What is the number of elements required in order to achieve the above time complexity?

Question 10

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quick sort runs in Θ(n²) time
II. Bubble sort runs in Θ(n²) time
III. Merge sort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

Question 11

The worst case running time of Insertion sort, Merge sort and Quick sort, respectively, are:

Question 12

Consider the following function.
void f (int n)
{
int i, j, m;
for(i = 0; i < 100; i ++)
{
for( i = 0; j < n; j++)
{
for (m=0; m < i; m ++)
printf(“%d”, i + j + m);
}
}
}
What is the time complexity of the above function ‘f’ for any positive value of n?

Question 13

Consider the following induction proof that all sheep in a flock are the same colour:
Base case: One sheep. It is clearly the same colour as itself.
Induction step: A flock of n sheep. Take a sheep, a, out of the flock. The remaining n - 1 are all the same colour by induction. Now put sheep a back in the flock, and take out a different sheep, b. By induction, the n - 1 sheep (now with a in their group) are all the same colour. Therefore, a is the same colour as all the other sheep; hence, all the sheep in the flock are the same colour.
What is wrong with this proof?

Question 14

Consider the following polynomial equation

where a,b,c,d and e are not equal to zero. What would be the minimum number of multiplication required to calculate the polynomial

?

Question 15

Let us say you positive integers a and b are taken from the user and then they are fed to the following function:
void function(int a, int b){
while( a != b){
if( a > b )
a = a - b;
else
b = b - a;
}
printf(“%d”, b);
}
What does the above function compute?