Dynamic Programming In Data Structures - Study Mode

Show All Answers

[#51] Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?

(A) 18000

(B) 12000

(C) 24000

(D) 32000

Correct Answer

(A) 18000

[#52] Find the longest increasing subsequence for the given sequence: {10, -10, 12, 9, 10, 15, 13, 14}

(A) {10, 12, 15}

(B) {10, 12, 13, 14}

(C) {-10, 12, 13, 14}

(D) {-10, 9, 10, 13, 14}

Correct Answer

(D) {-10, 9, 10, 13, 14}

[#53] What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term? int fibo(int n)
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1

for i: 2 to n
fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]

return fibo_terms[n]

(A) O(1)

(B) O(n)

(C) O(n 2 )

(D) Exponential

Correct Answer

(B) O(n)

[#54] Longest palindromic subsequence is an example of . . . . . . . .

(A) Greedy algorithm

(B) 2D dynamic programming

(C) 1D dynamic programming

(D) Divide and conquer

Correct Answer

(B) 2D dynamic programming

[#55] In which of the following cases the minimum no of insertions to form palindrome is maximum?

(A) String of length one

(B) String with all same characters

(C) Palindromic string

(D) Non palindromic string

Correct Answer

(D) Non palindromic string