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

Four matrices M₁, M₂, M₃ and M₄ 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₁ $$\times$$ M₂) $$\times$$ (M₃ $$\times$$ M₄)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M₁ $$\times$$ M₂) $$\times$$ M₃) $$\times$$ M₄), 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: