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.

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 M

If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:

_{1}, M_{2}, M_{3}and M_{4}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 ((M_{1}$$\times$$ M_{2}) $$\times$$ (M_{3}$$\times$$ M_{4})), the total number of multiplications is pqr + rst + prt. When multiplied as (((M_{1}$$\times$$ M_{2}) $$\times$$ M_{3}) $$\times$$ M_{4}), 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:

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:

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?

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)?

Questions Asked from Dynamic Programming (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages