Time Left - 30:00 mins

# GATE CS 2021 : Algorithm Rapid Mini Mock-1 (App update required to attempt this test)

Attempt now to get your rank among 662 students!

Question 1

In Quick Sort when the level alternate between good and bad splits, what will be the worst case time complexity for this algorithm?

Good split means the sorting of data elements after partition takes minimum time and Bad split means the sorting of data elements after partition takes maximum time.

Question 2

Find the complexity T(n) for the following recurrence relation.

T(n) = T(n/5) + T(n/6) + T(n/8) + c

i) O(nlog53) ii) Ω(nlog53) iii) O(nlog83) iv) Ω(nlog83) v) O(nlog63)

Question 3

Which of the following procedure is suitable to find the longest path from a given vertex to any other given vertex in a directed acyclic graph (weighted) with few negative edge weights.

Question 4

Consider the travelling salesman problem applied over a network of cites having 6 cites depicted though a graph. If we use dynamic programming approach, then the number of unique subproblems are _______.

Question 5

Which of following is true for greedy strategy?

Question 6

Consider the following data for job sequencing with deadline problem for 9 jobs (n = 9):

Which of the following is correct job sequence for minimizing the penalty?

Question 7

Find the number of spanning trees for the following graph : _______

Question 8

Match the pairs in the following question:

Match- II

A- Quick Sort

B- Dijkstra’s Algorithm

C- Floyd Warshall Algorithm

D- Connected Components

Match -II

1- Dynamic Programming

2- Greedy Method

3- Depth First Search

4- Divide and Conquer

Question 9

Find the complexity of the following algorithm.

Question 10

Consider a hash table with 10 slots in which 6 slots are filled already. Now two more keys needs to be inserted one after the other. What is the probability that during the insertion of these two keys , the first key doesn’t suffer from collision but the second key suffers from a single collision __________.

Question 11

Consider the hashing function h(k)=k mod 7. The number of collisions with linear probing for the insertion of the following keys 29, 36, 16, 30.

Question 12

Consider an array consisting of the following elements in unsorted order (placed randomly), but 60 as first element.
60, 80, 15, 95, 7, 12, 35, 90, 55
Quick sort partition algorithm is applied by choosing first element as pivot element. How many total number of arrangements of array integers is possible preserving the effect of first pass of partition algorithm.
• 662 attempts