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.

   ---

   Solution:

   For each index pair (i,j) with 1 ≤ i ≤ n and 0 ≤ j ≤ M, define a subproblem consisting of finding the minimum number of coins that are needed to make change for j cents using only the first i coin denominations d₁,...,d_i. The final solution, that is the minimum number of coins needed to make change for M is the value stored in the index pair (n,M).

   Recurrence relation for the optimized (in this case, minimized) objective function. We need to fill in each cell OPT(i,j). Consider coins of denomination d_i. The minimum number of coins from the first i denominations 1,...,i that can be used to make change for j cents, either includes denomination i or it doesn't:

   • If it does NOT include denomination i, then the minimum number of coins from the first i denominations 1,...,i that can be used to make change for j cents must be equal to the minimum number of coins from the first i-1 denominations 1,...,i-1. In other words, OPT(i,j) = OPT(i-1,j).
   • If it does include denomination i, then the minimum number of coins from the first i denominations 1,...,i that can be used to make change for j cents must be equal to the minimum number of coins from the first i denominations 1,...,i that can be used to make change for j-d_i cents plus 1. In other words, OPT(i,j) = OPT(i,j-d_i) + 1.
     Note that i is kept the same in the right hand side of the equation above (that is, OPT(i, ...) = OPT(i, ...) + ...) because it is possible that the denomination d_i gets used more than once.

   The best of the two options above has to be the one that produces the fewer number of coins. In other words:

         OPT(i,j) = minimum(OPT(i-1,j), OPT(i,j-di) + 1).
   

   This gives us the recurrence we were looking for. However, when i=1 (i.e., i-1 = 0) and/or when j < d_i, then we need to be careful about calculating the recurrence above, because in those cases the recurrence refers to non existing cells in the 2-dimensional array OPT (namely OPT(0,j) and/or OPT(i, "negative value"). To deal with this, we add the following conditions to our recurrence.

   • If i=1 and j < d_i : In this case, OPT(i,j) should be ∞
   • If i=1 and j ≥ d_i : In this case, OPT(i,j) = OPT(i,j-d_i) + 1
   • If i > 1 and j < d_i : In this case, OPT(i,j) = OPT(i-1,j)

   Boundary conditions. We can fill in the values of OPT(i,j) along the edge consisting of points of the form (i,0), as we know that the minimum number of coins needed to make change for 0 cents is 0.

           OPT(i,0) = 0 for all 1 ≤ i ≤ n.
   

   Updated order for OPT(i,j). All values OPT(i,j) with 1 ≤ i ≤ n, 1 ≤ j ≤ m will be needed. We can update these values by scanning across rows (i from 1 to n) for each value of j, increasing j to j+1 afterwards so as to eventually scan column j=1 through column j=M. We just need to make sure that when we calculate OPT(i,j), other values OPT(i',j') with i' ≤ i and j' ≤ j have already been calculated.

   ---

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

   ---

   Solution:

     Coin Changing(denominations,M)
     Input:  {Array denominations[1...n] and M.}
     Output:  {It prints the minimum number of coins k that are
           needed to make change for M, and also how many coins of each
           denomination are included in this optimal solution with k coins.} 
     {
          Assume n is a global variable.
   
          /* Initialize the 0th row and the 0th column of matrix L */
          /* using the boundary conditions                         */
   
           For i:=0 to n {
              OPT[i,0] := 0
           }
           
          /* Fill in OPT using the recurrence identified above */
   
           For i:=1 to n {
              For j:=1 to M {
                 If (i==1) and (j < denominations[i]) Then 
                   OPT[i,j]:= ∞
                 Else If (i==1) Then
                   OPT[i,j]:= OPT[i,j-denominations[i]] + 1
                 Else If (j < denominations[i]) Then 
                   OPT[i,j]:= OPT[i-1,j] 
                 Else OPT[i,j] := minimum(OPT[i-1,j], OPT[i,j-denominations[i]] + 1)
              }
           }
   
           /* Print the optimal solution  */
    
           print("Min number of coint:", OPT[n,M])
   
           print("Coin denominations used in the optimal solution:")
   
           Print-Denominations-Optimal-Solution(OPT,denominations,n,M)
           
               
     }
   
     Print-Denominations-Optimal-Solution(OPT,denominations,i,j)
     {
          For k:= 1 to n 
              num-coins-denom[k]:= 0
             
          While j > 0 do {
             If OPT[i,j] == OPT[i-1,j] Then {
                i:= i-1
             Else If OPT[i,j] == OPT[i,j-denominations[i]] + 1) Then {
                    num-coins-denom[i] := num-coins-denom[i] + 1
                    j := j - denominations[i]
                  }
             }
          }
   
          For k:= 1 to n 
             If num-coins-denom[k] > 0 Then
               Print("Denomination: ", denomination[k], "# of coins:" num-coins-denom[k])
     }
   

   ---

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.

   ---

   Solution:

   Our algorithm consists of 2 parts:

   • Traversing our matrix OPT once cell by cell filling them in using the recurrence. This part takes Θ(n*M).
   • Traversing our matrix OPT, from the cell OPT[n,M] "backwards" until getting to a cell OPT[.,0]. In each step either a coin is added to the optimal answer, or a denomination is skept over. Hence, the time taken by this part is Θ(n + OPT[n,M]).

   Hence, the runtime of the whole algorithm is Θ(n*M).

   ---

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.

      ---

      Solution:

      For each index pair (i,j) with 1 ≤ i ≤ n and 1 ≤ j ≤ m, define a subproblem consisting of finding the length of the longest consecutive "suffix" subsequence of the subarrays A[1...i] and B[1...j], that is, a subsequence that ends at position i in A and at position j in B. The objective function measures the lengths of such subsequences. Define L(i,j) to be the maximum such length. In other words, L(i,j) is the length of the maximum shared subarray of A and B that ends exactly at A[i] and at B[j].

      ---

   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.

      ---

      Solution:

      Recurrence relation for the optimized (in this case, maximized) objective function. If A[i]=B[j], then the longest consecutive common subsequence that enters into L(i,j) will simply be the concatentation of the longest subsequence that enters into L(i-1,j-1) with the common element A[i]=B[j]; hence L(i,j) = L(i-1,j-1) + 1 in this case. If A[i] ≠ B[j], then there are no common consecutive subsequences that end at index i in A and at index j in B, so L(i,j)=0 in this case. Summarizing:

                |  1 + L(i-1,j-1),  if A[i] = B[j]
      L(i,j) =  |
                |  0,               if A[i] ≠ B[j]
      

      Boundary conditions. We can fill in the values of L(i,j) along the two edges consisting of points of the form (i,0) and (0,j):

              L(i,0) = 0 = L(0,j) for all 1 ≤ i ≤ n and 1 ≤ j ≤ m.
      

      Updated order for L(i,j). All values L(i,j) with 1 ≤ i ≤ n, 1 ≤ j ≤ m will be needed. We can update these values by scanning across rows (i from 1 to n) for each value of j, increasing j to j+1 afterwards so as to eventually scan column j=1 through column j=m. We just need to make sure that when we calculate L(i,j), the value L(i-1,j-1) has already been calculated.

      ---

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

   ---

   Solution:

     Longest Shared Subarray(A,B)
     Input:  {Arrays A[1...n] and B[1...m].}
     Output:  {It prints the maximum length k of a consecutive subarray
           A[s+1...s+k] = B[t+1...t+k] that is common to A and B,
           and the subarray A[s+1...s+k]}
     {
          /* Initialize the 0th row and the 0th column of matrix L */
          /* using the boundary conditions                         */
   
           For i:=0 to n {
              L[i,0] := 0
           }
           
           For j:=0 to m {
              L[0,j] := 0
           }
           
          /* Fill in L using the recurrence identified above in an     */
          /* order such that L[i-1,j-1] is calculated before L[i,j] is */
   
           For j:=1 to m {
              For i:=1 to n {
                 If A[i]==B[j] Then {
                   L[i,j]:= L[i-1,j-1] + 1
                 } Else {L[i,j] := 0}
              }
           }
   
          /* Find the maximum value in L. That's the length of the  */
          /* longest shared subarray of A and B.                    */ 
   
           max_length := 0
           max_i := 0
           max_j := 0
   
           For j:=1 to m {
              For i:=1 to n {
                 If L[i,j] > max_length {
                    max_length := L[i,j]
                    max_i := i
                    max_j := j
                 } 
              }
           }
   
           /* Print the longest shared subarray and its length    */
    
           print("Length of Longest Shared Subarray:", max_length)
   
           print("Longest Shared Subarray:")
           Print-Longest-Shared-Subarray(A,B,L,max_i,max_j)
           
               
     }
   
     Print-Longest-Shared-Subarray(A,B,L,mi,mj)
     {
          If L[mi,mj] != 0 {
             Print-Longest-Shared-Subarray(A,B,L,mi - 1,mj - 1)
             print(A[mi]) /* note that A[mi]==B[mj] in this case */   
          }
     }
   

   ---

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.

   ---

   Solution:

   Our algorithm consists of 3 parts:

   • Traversing our matrix L once cell by cell filling them in using the recurrence. This part takes Θ(n*m).
   • Traversing our matrix L once cell by cell looking for the maximum value stored in L. This part takes Θ(n*m).
   • Traversing our matrix L, from the cell containing the maximum value, L[max_i,max_j] "diagonally backwards" to L[max_i - 1,max_j - 1], L[max_i - 2,max_j - 2] until we reach a cell with value 0. This will take O(maximum(n,m)).

   Since clearly maximum(n,m) ≤ n*m, the runtime of the whole algorithm is Θ(n*m).

   ---