CS502 Fundamentals of Algorithms Assignment 3 Solution Fall 2013

Question Statement

Counting money problem is an optimization problem in which the Change (coins, paper notes) is to be count out for a certain amount of money (N) in minimum possible number of coins/bills.

Like 0/1 Knapsack problem in the Dynamic Programing solution for Making change, we also build a table C [k, N]. Columns in this table denote the amount ‘j’ starting from zero and increasing sequentially up to money N for which Change is to be count. Rows ‘i’ in table C denote available denominations d[i] (value of coin/note) starting from lowest value coin in the system and increasing in steps (of next denominations) up to ‘d[k]’ which is the largest note less than amount N.

At the start, all the values c[i, 0] in column zero are filled and then cells c[1, j] of first row (for lowest coin value d[1]) are fully filled. After that, rest of the rows are filled one by one, deciding among the ‘Using’ and ‘Not using’ of the coin/note of value d[i], for each cell. If value d[i] of coin/note ‘i’ is greater than corresponding ‘j’ value, then it is not taken in use and resultantly the optimum number for this cell (c[i, j]) is the value in c[i-1, j]. For other cells, decision (Using/Not using) is made by comparing the values of c[i-1, j] and (1+ c[i, j-d[i]]), filling c[i, j] with minimum of both the values. Finally the value in the last cell (c[k, N]) is the required optimum value of Change count for N.
Suppose you have to give Money-Change for the amount of Rs.18 with least possible number of coins/notes. Currently the denominations for Pakistan currency system in Rupees are coins of 1, 2, 5 and paper notes of 10, 20, 50, 100, 500, 1000, and 5000.

You are required to determine whether the Greedy-approach gives optimum value or not in this case by calculating the required number of total coins/bills through both the solution methods.

Part 1 – Using Dynamic Programming [10 marks]
Part 2 – Using Greedy algorithm [5 marks]

Important Note: You have to show all the values for dynamic programming solution in the rows and columns of a single table only. There is no need to make separate tables for intermediate steps.