Divide and Conquer Method · Algorithms · GATE CSE

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\limit...

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...

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...

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...

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one...

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...

The solution to the recurrence equation T(2k) = 3 T(2k-1) + 1, T (1) = 1, is:

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...

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...

A sorting technique is called stable if:

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...

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

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...

Merge sort uses

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 a...

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

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...

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k whil...

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...

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...

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...

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...

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...

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 ...

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Wh...

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...

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

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?

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...

The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals to

The recurrence relation that arises in relation with the complexity of binary search is:

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...

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 ...

Find a solution to the following recurrence equation T(n) = T(n - 1)+ n T(1) = 1