Data Structures and Algorithms - 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.
You must be logged in to post a comment.
- Option : B
- Explanation : We can’t solve in polynomial time if input is encoded in binary.
You must be logged in to post a comment.
You must be logged in to post a comment.
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
You must be logged in to post a comment.
You must be logged in to post a comment.
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.
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : C
- Explanation : Largest common subsequence is dynamic
programming approach
You must be logged in to post a comment.
You must be logged in to post a comment.
You must be logged in to post a comment.