To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand, messy, unorganized, etc., may not receive full marks. Mark values for each question are contained in the [square brackets].
- Recall the problem presented in Assignment 1 where given a list L of n ordered integers you’re tasked with removing m of them such that the distance between the closest two remaining integers is maximized. See Assignment 1 for further clarification and examples. As it turns out there is no (known) greedy algorithm to solve this problem. However, there is a dynamic programming solution. Devise a dynamic programming solution which deter- mines the maximum distance between the closest two points after removing m Note, it doesn’t need to return the resulting list itself.
Hint 1: Your sub-problems should be of the form S(i, j), where S(i, j) returns the maximum distance of the closest two numbers when only considering removing j of the first i numbers in L. As an example if L = [3, 4, 6, 8, 9, 12, 13, 15], then S(4, 1) = 2, since
the closest two values of Lt = [3, 4, 6, 8] are 6 and 8 after removing 4 (note, 8-6 = 2).
Hint 2: For the sub-problem S(i, j), assuming j < i − 2, you know there’s always an optimal solution which leaves the values L and L[i] in the list.
Give a mathematical definition of S(i, j) including all its base cases. 
- You’re an entry level employee managing a financial portfolio. Because you’re a total novice, your boss limits the portfolio to a single stock, and moreover, each day you’re only allowed to make one of three choices: do nothing, purchase exactly one share, or sell all shares you currently own. You are scheduled to manage the portfolio for n days, and for each day i the price of the stock is estimated to be pi. Assume these estimations are perfect. On any given day i the value of your portfolio equals
(#shares you own)pi−(amount spent to buy shares)+(amount made from selling past shares).
- Devise a dynamic programming algorithm to determine the maximum value your portfolio can achieve on day n. Make sure to:
- Clearly state your sub-problems in plain English
- Formally define your sub-problems mathematically
State how one would arrive at the final answer from your sub-problems 
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:dmxyzl003