7 practice sets · Page 1 of 1
Which technique is used by line 7 of the above code?
Greedy
Recursion
Memoization
Overlapping subproblems
Correct Answer: C — Memoization
Explanation:
Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.
Which property is shown by line 7 of the above code?
Optimal substructure
Overlapping subproblems
Both overlapping subproblems and optimal substructure
Greedy substructure
Correct Answer: A — Optimal substructure
Explanation:
We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.
What is the space complexity of the recursive implementation used to find the nth fibonacci term?
O(1)
O(n)
O(n^{2})
O(n^{3})
Correct Answer: A — O(1)
Explanation:
The recursive implementation doesn't store any values and calculates every value from scratch. So, the space complexity is O(1).
Which property is shown by the above function calls?
Memoization
Optimal substructure
Overlapping subproblems
Greedy
Correct Answer: C — Overlapping subproblems
Explanation:
From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.
What is the time complexity of the recursive implementation used to find the nth fibonacci term?
O(1)
O(n^{2})
O(n!)
Exponential
Correct Answer: D — Exponential
Explanation:
The recurrence relation is given by (fibo(n) = fibo(n - 1) + fibo(n - 2)). So, the time complexity is given by:
(T(n) = T(n - 1) + T(n - 2))
Approximately,
T(n) = 2 * T(n - 1)
= 4 * T(n - 2)
= 8 * T(n - 3)
:
:
:
= 2^{k} * T(n - k)
This recurrence will stop when n - k = 0
i.e. n = k
Therefore, (T(n) = 2^{n} * O(0) = 2^{n})
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.
Which line would make the implementation complete?
fibo(n) + fibo(n)
fibo(n) + fibo(n - 1)
fibo(n - 1) + fibo(n + 1)
fibo(n - 1) + fibo(n - 2)
Correct Answer: D — fibo(n - 1) + fibo(n - 2)
Explanation:
Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).
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?
Recursion
Dynamic programming
A single for loop
Recursion, Dynamic Programming, For loops
Correct Answer: D — Recursion, Dynamic Programming, For loops
Explanation:
Each of the above mentioned methods can be used to find the nth fibonacci term.
