Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment 3: Money, Money, Money
(75 marks)
Question 1: Maximum Subarray (20 marks)
Given an array P[0..n] where P[i] represents the price of a stock on day i, find: max P[j] − P[i].
0≤i<j ≤n
Using divide-and-conquer, the maximum subarray problem was solved in O(nlogn) time.
Now, the same problem can be solved even more quickly using dynamic programming.
return if the stock is sold on day j.
(a) (12 marks) Finds the optimal return on investment in O(n) time.
(b) (4 marks) Describes the investment strategy. If there is no way to make money
over the n days then the program should write an appropriate message.
Question 2: Rising Trends (25 marks)
Given an array P[1..n] where Pi represents the price of a stock on day i, find the length of the longest rising trend. A rising trend is a subsequence of days, beginning on day 1 and not necessarily contiguous, where the price of the stock strictly increases.
(a) (10 marks) Finds the longest rising trend. (b) (5 marks) Describes the optimal solution.
Question 3: Investments (30 marks)
Suppose that interest rates are summarized in a table I where each element Iij (0 ≤ i < j ≤ n) represents the annual interest rate for an investment beginning in year i and ending in year j. To realize these returns, however, an investment cannot be sold before its maturity.
For example, suppose that I0,1 = 0.10, I1,2 = 0.20 and I0,2 = 0.12. The optimal solution yields an overall return of 0.32 (or 32%) for an investment that is held for one year at 0.10 and reinvested in the second year at 0.20. This is superior than holding onto an investment for two years at 0.12 per year and yielding an overall return of only 0.2544 (or 25.44%).
1. (7 marks) Assuming that interest is compounded annually, define a recurrence relation Rij which denotes the maximum return for an investment strategy that begins in year i and ends in year j, j > i.
2. Using this recurrence, implement and test a dynamic programming algorithm that:
(a) (12 marks) Finds the optimal return on investment. (b) (8 marks) Describes the investment strategy.
3. (3 marks) State the order of complexity of your algorithm.