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

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 ______________.

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.

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