1
GATE CSE 2018
+2
-0.6
Assume that multiplying a matrix $${G_1}$$ of dimension $$p \times q$$ with another matrix $${G_2}$$ of dimension $$q \times r$$ requires $$pqr$$ scalar multiplications. Computing the product of $$n$$ matrices $${G_1}{G_2}{G_{3...}}{G_n}$$ can be done by parenthesizing in different ways. Define $${G_i}\,\,{G_{i + 1}}$$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $${G_1}{G_2}{G_3}{G_4}{G_5}{G_6}$$ using parenthesization $$\left( {{G_1}\left( {{G_2}{G_3}} \right)} \right)\left( {{G_4}\left( {{G_5}{G_6}} \right)} \right),\,\,{G_2}{G_3}$$ and $${G_5}{G_6}$$ are the only explicitly computed pairs.

Consider a matrix multiplication chain $${F_1}{F_2}{F_3}{F_4}{F_5},$$ where matrices $${F_1},{F_2},{F_3},{F_4}$$ and $${F_5}$$ are of dimensions $$2 \times 25,\,\,25 \times 3,\,\,3 \times 16,\,\,16 \times 1$$ and $$1 \times 1000,$$ respectively. In the parenthesization of $${F_1}{F_2}{F_3}{F_4}{F_5}$$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A
$${F_1}{F_2}$$ and $${F_3}{F_4}$$ only
B
$${F_2}{F_3}$$ only
C
$${F_3}{F_4}$$ only
D
$${F_1}{F_2}$$ and $${F_4}{F_5}$$ only
2
GATE CSE 2016 Set 2
Numerical
+2
-0
Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$$ and $$10 \times 5,\,$$ respectively. The minimum number of scalar multiplications required to find the product $${A_1}{A_2}{A_3}{A_4}$$ using the basic matrix multiplication method is ______________.
3
GATE CSE 2015 Set 2
+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

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