Divide and Conquer Method · Algorithms · GATE CSE

Start Practice

Marks 1

GATE CSE 2021 Set 2
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find th...
GATE CSE 2021 Set 2
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
GATE CSE 2021 Set 1
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element i...
GATE CSE 2019
Consider a sequence of 14 elements : A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum $$S\left( {i,j} \right) = \sum\limi...
GATE CSE 2014 Set 2
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n
GATE CSE 2014 Set 3
The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given value of X using only one tempora...
GATE CSE 2014 Set 3
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest u...
GATE CSE 2014 Set 1
Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P...
GATE CSE 2009
Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one...
GATE CSE 2003
The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be i...
GATE CSE 2002
The solution to the recurrence equation T(2k) = 3 T(2k-1) + 1, T (1) = 1, is:
GATE CSE 2001
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using ran...
GATE CSE 2000
Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with su...
GATE CSE 1999
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order...
GATE CSE 1999
A sorting technique is called stable if:
GATE CSE 1995
Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive pr...
GATE CSE 1995
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of
GATE CSE 1995
Merge sort uses

Marks 2

GATE CSE 2019
Consider the following statements : I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is ...
GATE CSE 2014 Set 1
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do fo...
GATE CSE 2014 Set 1
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________
GATE CSE 2013
Consider the following function: int unknown(int n) { int i, j, k = 0; for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2...
GATE CSE 2013
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k whil...
GATE CSE 2012
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computat...
GATE CSE 2009
The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3...
GATE CSE 2009
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time com...
GATE CSE 2008
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which cont...
GATE CSE 2007
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the ...
GATE CSE 2006
Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Wh...
GATE CSE 2006
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 selec...
GATE CSE 2005
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?
GATE CSE 1997
Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$ Which of the following statements is true?
GATE CSE 1996
The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals to
GATE CSE 1996
Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1...
GATE CSE 1994
The recurrence relation that arises in relation with the complexity of binary search is:
GATE CSE 1992
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an...
GATE CSE 1987
Find a solution to the following recurrence equation T(n) = T(n - 1)+ n T(1) = 1
GATE CSE 1987
Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 ...
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12