Question 1 |

Consider product of three matrices M_{1},M_{2} and M_{3} having w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as \left(M_{1} M_{2}\right) M_{3} than to compute M_{1}\left(M_{2} M_{3}\right) ?

Always take the same time | |

(1 / x+1 / z) \lt (1 / w+1 / y) | |

x \gt y | |

(w+x) \gt (y+z) |

Question 1 Explanation:

Question 2 |

Assume that multiplying a matrix G1 of dimension pxq with another matrix G2 of
dimension pxq requires pqr scalar multiplications. Computing the product of n matrices G1G2G3...Gn can be done by parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization (G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2x25, 25x3, 3x16, 16x1 and 1x1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

F1F2 and F3F4 only | |

F2F3 only | |

F3F4 only | |

F1F2 and F4F5 only |

Question 2 Explanation:

Question 3 |

Which of the following algorithms solves the all pair shortest path problem?

Prim's algorithm | |

Dijkstra's algorithm | |

Bellman ford algorithm | |

Floyd warshalls algorithm |

Question 3 Explanation:

Question 4 |

Let A1,A2,A3, and A4 be four matrices of dimensions 10x5, 5x20, 20x10, and 10x5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is __________.

1500 | |

5000 | |

1000 | |

2000 |

Question 4 Explanation:

Question 5 |

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Greedy paradigm | |

Divide-and-Conquerparadigm. | |

Dynamic Programing paradigm. | |

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. |

Question 5 Explanation:

Question 6 |

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with \infty, and hence there cannot be any entry to the right of, or below a \infty. The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a \infty). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _______.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a \infty). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _______.

4 | |

5 | |

6 | |

7 |

Question 6 Explanation:

Question 7 |

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

24 | |

23 | |

34 | |

33 |

Question 7 Explanation:

Question 8 |

Four matrices M1, M2, M3 and M4 are dimensions p x q, q x r, r x s and s x t
respectively can be multiplied in 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 scalar 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 minimum number of scalar
multiplications needed is

248000 | |

44000 | |

19000 | |

25000 |

Question 8 Explanation:

Question 9 |

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below.

Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array

Which of the following statements is TRUE?

Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array

Which of the following statements is TRUE?

The algorithm uses dynamic programming paradigm | |

The algorithm has a linear complexity and uses branch and bound paradigm | |

The algorithm has a non-linear polynomial complexity and uses branch and
bound paradigm | |

The algorithm uses divide and conquer paradigm. |

Question 9 Explanation:

Question 10 |

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 l(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 l(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 values 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)?

All elements L should be initialized to 0 for the values of l(i,j) to be properly computed. | |

The values of l(i,j) may be computed in a row major order or column major order of L(M,N). | |

The values of l(i,j) cannot be computed in either row major order or column
major order of L(M,N). | |

L[p,q] needs to be computed before L[r,s] if either p |

Question 10 Explanation:

There are 10 questions to complete.