2023年11月25日

算法代写 | CSC 373 Assignment 2

算法代写CS373的主要任务是通过常见算法（贪心算法、MST、BST）等算法解决题目中给定的模拟case，语言可以选择C/C++/JAVA/PYTHON等。

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

  1. 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[1] and L[i] in the list.

Give a mathematical definition of S(i, j) including all its base cases. [15]

  1. 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 [15]