Data Structures and Algorithms MCQ - 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