Dynamic Programming In Data Structures - Study Mode

Show All Answers

[#106] 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 technique is used by line 7 of the above code?

(A) Greedy

(B) Recursion

(C) Memoization

(D) Overlapping subproblems

Correct Answer

(C) Memoization

[#107] The following sequence is a fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Which technique can be used to get the nth fibonacci term?

(A) Recursion

(B) Dynamic programming

(C) A single for loop

(D) Recursion, Dynamic Programming, For loops

Correct Answer

(D) Recursion, Dynamic Programming, For loops

[#108] You are given a rod of length 10 and the following prices. length price
1 2
2 5
3 6
4 9
5 9
6 17
7 17
8 18
9 20
10 22 Which of these pieces give the maximum price?

(A) {1,2,7}

(B) {10}

(C) {2,2,6}

(D) {1,4,5}

Correct Answer

(C) {2,2,6}

[#109] Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

(A) True

(B) False

Correct Answer

(A) True

[#110] You are given infinite coins of N 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. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

(A) O(N)

(B) O(S)

(C) O(N 2 )

(D) O(S*N)

Correct Answer

(D) O(S*N)