Time Left - 10:00 mins

GATE 2020 : Algorithms Quiz 3 (App update required to attempt this test)

Attempt now to get your rank among 696 students!

Question 1

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Question 2

Suppose that we have an array of n data records to sort and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:
1) The algorithm runs in O(n) time.
2) The algorithm is stable.
3) The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
Now match the following :

Question 3

The following problems are solved using Dynamic Programming/Greedy Algorithms. Match these problems to their respective time complexity :

Question 4

The following problems are solved using Divide and Conquer. Match these problems to their respective recurrence relation :

Question 5

You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array ?

Question 6

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.

696 attempts
2 upvotes
4 comments

Tags :

GATE & PSU CS Algorithms

Aug 13GATE & PSU CS