Algorithms - Algorithm Design Techniques
- 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
- Option : B
- Explanation : The value can be computed Either in row major or column major order. We can Swap the two 100 ps without effecting the output.
Linked Answers Questions 5 and 6
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 , a2 , a3 , …….., an } 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 {a1 , a2 ………., ai } whose elements sum to j.
53. Which of the following is valid for 2 < i < n and ai ≥ j ≥ W?
- Option : B
- Explanation : X [i, j] = X[i–1, j] ∨ X[i-1, j–ai] x [i, j] is true if any one is true. or x[i – 1, j – ai] is true
54. Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
- Option : C
- Explanation : If we get the entry x[n, w] as true then there is a subset of {a1, a2 ...... an} that has sum as.W.
