Algorithms MCQ - Algorithm Design Techniques

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

A
All elements of L should be initialized to 0 for the values of l(i,j) to be properly computed
B
The values of l(i, j) may be computed in a row major order or column major order of L [M, N]
C
The values of l(i, j) cannot be computed in either row major order or column major order of L[M, N]
D
L [p, q] needs to be computed before L [r, s] if either p < r or q < s

The value can be computed Either in row major or column major order. We can Swap the two 100 ps without effecting the output.

52 The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W; determine whether there is a subset of S whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

We can’t solve in polynomial time if input is encoded in binary.

Linked Answers Questions 5 and 6

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁ , a₂ , a₃ , …….., a_n } and a positive integer W is there a subset S whose elements sum of 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.

53 Which of the following is valid for 2 < i < n and ai ≥ j ≥ W?

X [i, j] = X[i–1, j] ∨ X[i-1, j–a_i] x [i, j] is true if any one is true.
or x[i – 1, j – a_i] is true

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

If we get the entry x[n, w] as true then there is a subset of {a₁, a₂ ...... a_n} that has sum a_s.W.

55 We wish to find the length of the longest common subsequence (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?

Largest common subsequence is dynamic programming approach