GATE CSE Dynamic Programming – Algorithms Practice Test

GATE CSE Dynamic Programming – Algorithms Practice Test | Set 1

Questions 81-85 of 100

0% completed (0/100 answered)

Question 81

MSQ · Multiple Correct 2 mark

In Longest Common Subsequence of strings X and Y, which operations are performed during table filling?

A If X[i] != Y[j], L[i][j] = max(L[i-1][j], L[i][j-1]) B If X[i] == Y[j], L[i][j] = 1 + L[i-1][j-1] C Table dimensions are (m+1) x (n+1) D Base cases L[i][0] = 0 and L[0][j] = 0

Question 82

MSQ · Multiple Correct 2 mark

Which statements regarding Floyd-Warshall Algorithm are CORRECT?

A It computes shortest paths between all pairs of vertices. B It works correctly with negative edge weights as long as no negative cycle exists. C It can detect negative weight cycles if d[i][i] < 0. D It runs in O($V^2)$ time.

Question 83

MSQ · Multiple Correct 2 mark

Which of the following problems can be solved using Dynamic Programming?

A Edit Distance Problem B Minimum Spanning Tree Problem C Rod Cutting Problem D Coin Change Problem

Question 84

MSQ · Multiple Correct 2 mark

Which of the following recurrences represent standard Dynamic Programming formulations?

A MCM: m[i,j] = min_{k} (m[i,k] + m[k+1,j] + p_{i-1}p_kp_j) B $0/1 Knapsack: K[i][w] = max(K[i-1][w], v_{i} + K[i-1][w - w_{i}])$ C $Quick Sort: T(n) = 2 T(n/2) + O(n)$ D LCS: L[i][j] = 1 + L[i-1][j-1] if X[i]==Y[j] else max(L[i-1][j], L[i][j-1])

Question 85

MSQ · Multiple Correct 2 mark

Which of the following statements regarding Bellman-Ford algorithm are CORRECT?

A It can handle graphs with negative edge weights. B It uses dynamic programming principles (relaxing edges V-1 times). C It runs in O(V * E) time. D It cannot detect negative weight cycles.