高级算法代写 | 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.


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论