Design Algorithm Analysis GATE CS and IT previous year questions with Answer
Ques 11 Gate 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 ∑jk=iA[k]. Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)
a is the correct answer.
Ques 12 Gate 2019
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.
a is the correct answer.
Ques 13 Gate 2019
There are n unsorted arrays: A1, A2, ....,An. Assume that n is odd. Each of A1, A2, ...., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1 ,A2, ....,An is ________ .
Ques 14 Gate 2017 Set-1
Consider the following table
| Algorithms | Design Paradigms |
|---|---|
| (P) Kruskal | (i) Divide and Conquer |
| (Q) Quicksort | (ii) Greedy |
| (R) Floyed Warshall | (iii) Dynamic Programming |
Match the algorithm to design paradigms they are based on:
Ques 15 Gate 2017 Set-1
Consider the following functions from positives integers to real numbers
10, √n, n, log2n, 100/n.
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Ques 16 Gate 2017 Set-1
Consider the following intermediate program in three address code
q = p * c
p = u * v
q = p+q
Which one of the following corresponds to a static single assignment from the above code?
Ques 17 Gate 2016 Set-2
Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1 A2A3A4 using the basic matrix multiplication method is______________.
a is the correct answer.
Ques 18 Gate 2016 Set-2
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is ________
a is the correct answer.
Ques 19 Gate 2016 Set-2
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.
An algorithm performs the following operations on the list in this order:
Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together
Ques 20 Gate 2016 Set-2
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on