Question

The following submission rules apply:

·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.

o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.

o Solutions must be provided in plain text so that formatting is not lost.

·    All answers must be provided in this document.

·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.

Does the Principle of Optimality hold for coin changing? Discuss with various interpretations of the Combine function.

Answer 1

1. Optimal Substructure
   

To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written

as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

1. Overlapping Subproblems
   

Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.

import java.util.Arrays;

class CoinChange

{

    static long countWays(int S[], int m, int n)

    {

        long[] table = new long[n+1];

        Arrays.fill(table, 0);  

        table[0] = 1;

        for (int i=0; i<m; i++)

            for (int j=S[i]; j<=n; j++)

                table[j] += table[j-S[i]];

        return table[n];

    }

    public static void main(String args[])

    {

        int arr[] = {1, 2, 3};

        int m = arr.length;

        int n = 4;

        System.out.println(countWays(arr, m, n));

    }

}