Dynamic Programming In Data Structures - Study Mode

Show All Answers

[#101] What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term? 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]

(A) O(1)

(B) O(n)

(C) O(n 2 )

(D) Exponential

Correct Answer

(B) O(n)

[#102] Consider the following assembly line problem: time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4 What is the minimum time required to build the car chassis?

(A) 40

(B) 41

(C) 42

(D) 43

Correct Answer

(D) 43

[#103] You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?

(A) n*n*n...f times

(B) f*f*f...n times

(C) n*n*n...n times

(D) f*f*f...f times

Correct Answer

(B) f*f*f...n times

[#104] Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

(A) 10*20

(B) 20*30

(C) 10*30

(D) 10*20*30

Correct Answer

(D) 10*20*30

[#105] If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called . . . . . . . .

(A) Dynamic programming

(B) Greedy

(C) Divide and conquer

(D) Recursion

Correct Answer

(C) Divide and conquer