Consider the following table

Match the algorithm to design paradigms they are based on:

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁,a₂,a₃,...,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i,j],1≤i≤n,0≤j≤W, is TRUE if and only if there is a subset of {a₁,a₂,...,a_i} whose elements sum to j.

Which of the following is valid for 2≤i≤n and a_i≤j≤W?

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁,a₂,a₃,...,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i,j],1≤i≤n,0≤j≤W, is TRUE if and only if there is a subset of {a₁,a₂,...,a_i} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

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:

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] 

Which one of the following options is correct?

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.

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

The weight of a sequence a₀, a₁, ..., a_n-1 of real numbers is defined as a₀+a₁/2+...+ a_n-1/2^n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a₀, a₁, ...,a_n-1 and Y the maximum possible weight of a subsequence of a₁, a₂, ..., a_n-1. Then X is equal to

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 L_i denote the length of the longest monotonically increasing sequence starting at index i in the array

Initialize Ln-1=1.
For all i such that 0≤i≤n-2

Finally the length of the longest monotonically increasing sequence is Max(L₀, L₁, ..., L_n-1).

Which of the following statements is TRUE?

Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), 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:

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

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