Time Left - 45:00 mins
GATE CS 2021 : Algorithm Revision Quiz 2 (App update required to attempt this test)
Attempt now to get your rank among 717 students!
Question 1
Which of the following is true?
I.
T(1) = 0
T(n) = O(n log n)
II.
T(n) = θ (log n)
Question 2
Given below are some recurrence relation and some asymptotic complexities:
Question 3
Find the complexity of the following algorithm.
Question 4
Give the correct matching for the following pairs when best cases are assumed for algorithms:
Question 5
The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
Question 6
Match the following :
A) Power of an element
B) Strassen's Matrix Multiplication
C) Merge Sort
D) Worst case of Job sequencing
1) O(n2.8)
2) O(logn)
3) O(nlogn)
4) O(n2)
A) Power of an element
B) Strassen's Matrix Multiplication
C) Merge Sort
D) Worst case of Job sequencing
1) O(n2.8)
2) O(logn)
3) O(nlogn)
4) O(n2)
Question 7
Consider a knapsack with capacity = 20 and fractions are allowed.
Consider three items I1 , I2 and I3 with following weight and profit.
Find the maximum profit possible using fractional knapsack ________.
Question 8
Which of the following represents most appropriate asymptotic solution for given recurrence relation:
T(n) = T()+log2(n)
Question 9
Consider the following message given below:
abbaabccdabcd
The number of bits required for Huffman encoding of the above message ________.
abbaabccdabcd
The number of bits required for Huffman encoding of the above message ________.
Question 10
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ___________.
Question 11
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?
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 12
Consider the following function:
Which of the following recursion formula depicts the running time of function, as a function of ‘n’?
Question 13
Which is the correct sequence of array after 2 merge operations in merge sort if the input is 10 , 2 , 5 , 3 , 7 , 13 , 1 , 6 ?
Question 14
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
Question 15
In a 0/1 Knapsack Problem, what is the amount of time taken to create the memory table and determine the optimal solution respectively, for K number of objects and T as the capacity of Knapsack?
- 717 attempts
- 0 upvotes
- 6 comments
Tags :
GATE & PSU CSAlgorithmsAug 10GATE & PSU CS