Time Left - 40:00 mins

GATE 2019 -National Champion Test ( Algorithms)

Attempt now to get your rank among 806 students!

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(log2n)  
6. (n log2n)

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 Θ(n2) time
II. Bubble sort runs in Θ(n2) 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 keys that are hashed into the hash table in the order given using the hash function mod 11.
12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5.
Assume hash table has locations from 0 to 10. If hash table uses chaining to handle the collisions, how many locations are left without hashing any element into it?

Question 13

A store has 5 items  III3 I4 and I5 with profit values (5, 10, 15, 12, 10) respectively and weight values (5, 2, 3, 4, 1) respectively. A person enters the store with a bag of capacity 6.  Let the maximum profit achievable by the person using the greedy technique is P and Q = (sum of item numbers completely picked by him), then what is P-Q?
For item I1the item number is 1, for item I2 the item number is 2 and so on.

Question 14

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

Question 15

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
  • 806 attempts
  • 3 upvotes
  • 13 comments
May 4GATE & PSU CS