Related InterviewSolutions

• We use dynamic programming approach when(A) We need an optimal solution(B) The solution has optimal substructure(C) The given problem can be reduced to the 3-SAT problem(D) It’s faster than Greedy
• In the above question, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?(A) X[1, W](B) X[n ,0](C) X[n, W](D) X[n -1, n]
• The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} 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 {a1 ,a2 ,…,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?(A) X[i, j] = X[i – 1, j] ∨ X[i, j -ai](B) X[i, j] = X[i – 1, j] ∨ X[i – 1, j – ai](C) X[i, j] = X[i – 1, j] ∧ X[i, j – ai](D) X[i, j] = X[i – 1, j] ∧ X[i -1, j – ai]
• Which of the following standard algorithms is not Dynamic Programming based.(A) Bellman–Ford Algorithm for single source shortest path(B) Floyd Warshall Algorithm for all pairs shortest paths(C) 0-1 Knapsack problem(D) Prim’s Minimum Spanning Tree
• 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(A) 248000(B) 44000(C) 19000(D) 25000