Consider the coin changing problem: Given coin denominations, devise a method to pay an amount to a customer using the fewest possible number of coins.

When we studied greedy algorithm, we saw that the greedy cashier's strategy (i.e., at each iteration we add a coin of the largest denomination that does not take us past the amount to be paid) produces an optimal solution IF the coin denominations are those of the US coins (i.e., 1, 5, 10, 25, and 100 cents). However, for other denominations, this greedy cashier's strategy might not be optimal. We saw an example in which if the coin denominations are {1, 10, 21, 34, 70, 100}, and the amount to be paid is 140 cents then the greedy cashier strategy will produce {100, 34, 1, 1, 1, 1, 1, 1} for a total of 8 coins, when the optimal answer is {70, 70} with a total of 2 coins.

In this problem you are asked to provide a dynamic programming solution to the coin changing problem that always produces an optimal solution (i.e., minimum number of coins) regardless of the coin denominations.

Input:

• An array denominations[1..n] containing the n coin denominations d₁,...,d_n that you can use (for example, [1, 10, 21, 34, 70, 100], in this case n=6). You can assume that this array is already sorted in increasing order (with no repetitions, of course). You can also assume that you have an unlimited number of coins of each denomination.
• The amount M that you need to pay (in the example above, M = 140 cents).

Output:

• The optimal (minimum) number of coins needed to make change for M (in the example above where M=140, the optimal number of coins is 2).
• The number of coins of each denomination used in the optimal solution (in the example above where M=140, the optimal answer is 2 coins of 70 cents. Note that in this example only one denomination was used, but in the general case more denominations might be used). In case that more than one optimal solution exists, output just one of them.

Solve this problem following the steps below.

1. (25 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail how you plan to divide this problem into subproblems (8 points), in what order you plan to solve the subproblems (5 points) so that the solutions to smaller subproblems are available to larger subproblems, and how you plan to use the solutions of these subproblems to produce a solution to the original problem (4 points). At each stage argue decisively that your solution is correct (8 points).

   Hint: Consider using a 2-dimensional array OPT[1..n][0..M], where OPT[i,j] = the minimum number of coins that are needed to make change for j cents using only the first i coin denominations d₁,...,d_i, where 1 ≤ i ≤ n, and 0 ≤ j ≤ M (both i and j are integer numbers).

   Find a recurrence relation that expresses the solution of OPT[i,j] in terms of the solutions of slightly "smaller" problems (i.e., other cells in the matrix OPT whose values can be calculated before). Include suitable boundary conditions for the recurrence relation. Based on this, determine in what order you'll calculate the values of the cells in OPT. Explain.

2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

3. (13 Points) Time Complexity. Determine the asymptotic running time of your dynamic programming algorithm above, as a function of the input array size n and M. Give the simplest possible big Theta expression for the running time.

The goal of this problem is to design a dynamic programming algorithm that, given two arrays, determines the length of their longest shared subarray. Note carefully that gaps are not allowed. That is, a subarray qualifies only if it matches some set of consecutive elements of each of the two input arrays. For example, suppose that the input arrays are

[15, 6, -17, 5, -5, 20, 43, 5, 33] and
[-47, 5, -5, 20, 5, 33, 43]. 

• Length of the longest shared subarray: 3.
• Longest shared subarray: [5, -5, 20].

The input-output description of this problem is:

Input: Two arrays A[1..n] and B[1..m] , A of length n, and B of length m.

Output: Your pseudo-code should print the following output:

1. The length L of the longest shared subsequence (i.e., subarray) of arrays A and B, and
2. The longest (length = L) shared subsequence/subarray (or one of them, if more than one of such shared subsequences of length L exists).

Solve this problem following the steps below.

1. Design of your Dynamic Programming Solution. Design a dynamic programming solution to this problem by following the steps below:

   1. (13 Points) Define a hierarchy of subproblems P(i,j), for 1 ≤ i ≤ n, and 1 ≤ j ≤ m, for the above task, defined in terms of suitable subarrays of the input arrays, that will allow a dynamic programming solution of the target task. State clearly what inputs and outputs are required for each subproblem, P(i,j). Argue decisively that your solution is correct.

   2. (12 Points) Find a recurrence relation that expresses the solution of P(i,j) in terms of the solutions of slightly smaller problems in the hierarchy. Include suitable boundary conditions for the recurrence relation. Explain. Argue decisively that your solution is correct.

2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

3. (13 Points) Time Complexity. Determine the asymptotic running time of your dynamic programming algorithm above, as a function of the input array sizes n and m. Give the simplest possible big Theta expression for the running time.