1
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Given below are some algorithms, and some algorithm design paradigms.

GROUP 1 GROUP 2
1. Dijkstra's Shortest Path i. Divide and Conquer
2. Floyd-Warshall algorithm to compute
all pairs shortest path
ii. Dynamic Programming
3. Binary search on a sorted array iii. Greedy design
4. Backtracking search on a graph iv. Depth-first search
v. Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow.

A
$$1 - i,\,\,2 - iii,\,\,3 - i,\,\,4 - v.$$
B
$$1 - iii,\,\,2 - iii,\,\,3 - i,\,\,4 - v.$$
C
$$1 - iii,\,\,2 - ii,\,\,3 - i,\,\,4 - iv.$$
D
$$1 - iii,\,\,2 - ii,\,\,3 - i,\,\,4 - v.$$
2
GATE CSE 2014 Set 2
Numerical
+2
-0
Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.
Your input ____
3
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
Four matrices M1, M2, M3 and M4 of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 $$\times$$ M2) $$\times$$ (M3 $$\times$$ M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 $$\times$$ M2) $$\times$$ M3) $$\times$$ M4), the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:
A
248000
B
44000
C
19000
D
25000
4
GATE CSE 2009
MCQ (Single Correct Answer)
+2
-0.6
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function I(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:
l(i,j)  = 0, if either i = 0 or j = 0
        = expr1, if i,j > 0 and X[i-1] = Y[j-1]
        = expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]
The value of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m+1 and N = n + 1, such that L[i, j] = l(i, j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?
A
All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed.
B
The values of l(i,j) may be computed in a row major order or column major order of L[M, N].
C
The values of l(i, j) cannot be computed in either row major order or column major order of L[M, N].
D
L[p, q] needs to be computed before L[r, s] if either p < r or q < s.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12