高级算法代写 | COIS 4050H: Advanced Algorithms Assignment 3

本次北美CS代写主要是算法相关,需要用到动态编程 dynamic Programming
COIS 4050H: Advanced Algorithms

Assignment 3: Money, Money, Money

(75 marks)
(due Friday, March 12, 2021 at 23:59)

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.

  1. (4 marks) Given P, define a recurrence relation for Rj which denotes the maximum

    return if the stock is sold on day j.

  2. Using this recurrence, implement and test a dynamic programming algorithm that:

    (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.

  1. (7 marks) Given P , define a recurrence relation for Lj which denotes the longest rising trend that begins on day j.
  2. Using this recurrence, implement and test a dynamic programming algorithm that:

    (a) (10 marks) Finds the longest rising trend. (b) (5 marks) Describes the optimal solution.

  3. (3 marks) State the order of complexity of your algorithm.

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.