NPTEL Design and Analysis of Algorithms Week 7 Assignment Answers 2024
1. Let S[1..n] denote the stock price of the company over the n quarters for which the growth potential is to be calculated. For 1 ≤ j ≤ n, let GP(j) denote the growth potential for the prefix of stock prices S[1..j] ending at S[j].
Which of the following is a correct recursive formulation of GP(j)?
- GP(1)=1
- For j ∈ 2,3,…,n, GP(j) = 1 + max { GP(k) | 1 ≤ k < j, S[k] < S[j] }
- GP(1)=1
- For j ∈ 2,3,…,n, GP(j) = 1 + max { GP(k) | 1 ≤ k < j, S[k] > S[j] }
- GP(1)=1
- For j ∈ 2,3,…,n, GP(j) = 1 + S[j-1] if S[j-1] < S[j] and GP(j) = 1, otherwise.
- GP(1)=1
- For j ∈ 2,3,…,n, GP(j) = 1 + S[j-1] if S[j-1] > S[j] and GP(j) = 1, otherwise.
Answer :- For Answers Click Here
2. What is the size of the memo table for this problem?
- n-1
- n
- n+1
- n2
Answer :-
3. What is a good order to compute the values of GP(i) using dynamic programming?
- From GP(n) to GP(1)
- From GP(1) to GP(n)
- Either from GP(n) to GP(1) or from GP(1) to GP(n)
- None of these
Answer :- For Answers Click Here
4. How much time will it take to compute GP(i), i ∈ 1,2,…,n, using standard dynamic programming?
- O(n)
- O(n log n)
- O(n2)
- O(n2 log n)
Answer :-
5. Suppose the stock price of a company over 30 quarters is as follows: [6, 91, 27, 61, 67, 12, 91, 58, 44, 70, 98, 84, 34, 21, 63, 41, 15, 65, 92, 28, 28, 54, 5, 51, 48, 33, 46, 98, 68, 71]. What would be its growth potential according to the magazine’s definition?
Answer :- For Answers Click Here
