Dynamic Programming In Data Structures - Study Mode

Show All Answers

[#121] You are given infinite coins of denominations v1, v2, v3, ....., vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using . . . . . . . .

(A) Greedy algorithm

(B) Dynamic programming

(C) Divide and conquer

(D) Backtracking

Correct Answer

(B) Dynamic programming

[#122] You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?

(A) 15

(B) 16

(C) 17

(D) 4

Correct Answer

(D) 4

[#123] What is the time complexity of the Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?

(A) O(1)

(B) O(n+m)

(C) O(mn)

(D) O(nlogm)

Correct Answer

(C) O(mn)

[#124] Kadane's algorithm is used to find . . . . . . . .

(A) Longest increasing subsequence

(B) Longest palindrome subsequence

(C) Maximum sub-array sum

(D) Longest decreasing subsequence

Correct Answer

(C) Maximum sub-array sum

[#125] Consider the following code to find the nth fibonacci term using dynamic programming: 1. int fibo(int n)
2. int fibo_terms[100000] //arr to store the fibonacci numbers
3. fibo_terms[0] = 0
4. fibo_terms[1] = 1
5.
6. for i: 2 to n
7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.
9. return fibo_terms[n] Which property is shown by line 7 of the above code?

(A) Optimal substructure

(B) Overlapping subproblems

(C) Both overlapping subproblems and optimal substructure

(D) Greedy substructure

Correct Answer

(A) Optimal substructure