GATE CS : Algorithms Champion Quiz 4 for GATE & PSU CS Exams

Question 1

What is recurrence relation for the worst case of Quicksort and time complexity in the Worst case of Quick Sort respectively?

Question 2

Consider the polynomial

The minimum number of multiplications needed to evaluate p on an input x is:

Question 3

In a Min heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

Question 4

Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm?
P. Always finds a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

Question 5

Two alternative packages A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires 10nlog₁₀n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Question 6

Consider the following C code segment:
intIsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf(“Not Prime\n”); return 0;}
return 1;
}
Let T(n)denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

Question 7

The subset–sum problem is defined as follows. Given a set of n positive integers, S = {a₁, a₂, a₃ ………, a_n}, and a positive integer W, is there a subset of S whose elements sum to TV? A dynamic program for solving this problem uses a 2 – dimensional Boolean array, X, with n rows and W + 1 columns. X[i, j],1 ≤ i ≤ n, 0 ≤ j W, is TRUE if and only if there is a subset of {a₁, a₂, ………, a;} whose elements sum to).
Which of the following is valid for 2 ≤ i ≤ n and a1 ≤ j ≤ W?

Question 8

In the following C function, let n ≥ m.
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
How many recursive calls are made by this function?

Question 9

Consider the Quick sort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub–lists each of which contains at least one–fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Question 10

Consider the Quick sort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then