Problem 4: Making Change: Given coins of denominations (value) 1 = v1 < v2< … <

Question

Problem 4: Making Change: Given coins of denominations (value) 1 = v1 < v2< … < vn, we wish to make change for an amount A using as few coins as possible. Assume that vi’s and A are integers. Since v1= 1 there will always be a solution.
Formally, an algorithm for this problem should take as input:
An array V where V[i] is the value of the coin of the ith denomination.
A value A which is the amount of change we are asked to make
The algorithm should return an array C where C[i] is the number of coins of value V[i] to return as change and m the minimum number of coins it took. You must return exact change so

Problem 6: Making Change Experimental Running time
a) Collect experimental running time data for your algorithm in Problem 4. Explain in detail how you collected the running times.
b) On three separate graphs plot the running time as a function of A, running time as a function of n and running time as a function of nA. Fit trend lines to the data. How do these results compare to your theoretical running time? (Note: n is the number of denominations in the denomination set and A is the amount to make change)

**I have posted Problem 4 for context, but really need help with Problem 5 and Problem 6 please.

Explanation / Answer

Answer:

Problem 4 is solved as per the guidelines, please repost problem 5.

a)

M(j) = the minimum number of coins required to make change for an amount of money j

                         M(j) = min{M(j vi )} + 1

The smallest number of coins required to make j , is the smallest number required to make j vi , plus one.

Algorithm Minimum-Change(C,v)

   //all of vi and C are positive integers.

   Input: n types of coin denominations of values v1 < v2 < ... < vn

Output: The minimum number of coins required to make change for an amount of money j

       M[0]ß0

        {M[j] where i<0}

    for jß1 to C do

          Min

          for iß1 to |V| do

              if M[j-v[i]] +1< min then

                    minßM[j-v[i]] +1

              end if

           end for

                  return M[C]

   end for

b)

The theoretical running time of the above algorithm is O(n * A)

Please provide your valuable feedback.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.