Dynamic Programming Solution

1.) (30 points) A “contiguous subsequence of a list S” is a subsequence made up of consecutive elements of S. For instance, if S = [2, 0.2, 4, 0.5, 2.2], then [0.2, 4, 0.5] is a contiguous subsequence of S, but [2, 0.5, 2.2] is not. Design a dynamic programming algorithm that takes input S, a list of positive real numbers, and returns the contiguous subsequence with the maximum product. For the example above, the answer would be [4, 0.5, 2.2] because it has the maximum product of 4.4.

(a.) Define the entries of your table in words, e.g. T [i] or T [i, j] is ...


(b.) State your base cases and the recurrence for entries of your table in terms of smaller sub-problems. Briefly explain in words why it is correct.






(c.) Write pseudocode for your algorithm to solve this problem.



(d.) Analyze the running time of your algorithm.


Solution:


2.) (30 points) You are consulting for a small investment company. They give you the price of Google’s shares over the last n days. Let S[1 . . . n] be the array of share prices, where S[1] is the price of the stock on the first day in this time period. During this window, the company wanted to buy a fixed number of shares on some day and sell all these shares on some later day (that is, only one purchase and one sale). The company wants to know when they should have bought and when they should have sold in order to maximize their profit. If there was no way to make money during the n days, you should report “Impossible”.

For example, if n = 3 and S = [9, 1, 5], then you should return “buy on day 2 and sell on day 3”

(a.) Define the entries of your table in words, e.g. T [i] or T [i, j] is ..



(b.) State your base cases and the recurrence for entries of your table in terms of smaller sub-problems. Briefly explain in words why it is correct.





(c.) Write pseudocode for your algorithm to solve this problem.

Solution:



(d.) Analyze the running time of your algorithm.


Solution:

3.) (40 points) You are given coins of denominations {x1, x2, ..., xn}, and there are exactly two coins of each denomination. Your task is to check if it is possible to make change for a value v. For example, if your denominations are {1, 2, 5}, you can make change for v = 15 using both coins of denominations 5 and 2 and one coin of denomination 1, but you cannot make change for v = 20. Design a Dynamic Programming algorithm to solve this problem.

(a.) Define the entries of your table in words, e.g. T [i] or T [i, j] is ...


Solution:



(b.) State your base cases and the recurrence for entries of your table in terms of smaller sub-problems. Briefly explain in words why it is correct.


Solution:




(c.) Write pseudocode for your algorithm to solve this problem.


Solution:




(d.) Analyze the running time of your algorithm.


Solution:

Given we are iterating a 2D array, we need to determine the dimensions, which is 2n x v. Thus we can say our runtime is O(2nv) = O(nv). We also have O(n) for doubling the array but this is overpowered by the term O(nv).



(e.) Suppose your coin denominations are {1, 4, 7}. Create and fill out the DP table you would use to determine if you can make change for v = 13.


Solution: