Assignment No. 03
GRADED
Semester: Fall 2013
CS502-Fundamentals of Algorithms Total Marks: 15
Due Date: 20/1/2014
Lectures Covered: 23 to 26
Objective
To develop in-depth solution for Money Counting problem with the
example case of Pakistani currency system and to get hands-on experience
of Dynamic Programing as well as Greedy algorithm approaches.
Uploading instructions:
Please view the Assignment Submission Process document provided to you
by the Virtual University of Pakistan for uploading assignments.
·0 Your assignment must be in .doc format. (Any other formats like scan images, PDF, Zip, rar, bmp etc. will not be accepted).
·1 Save your assignment with your ID (e.g. bc020200786.doc).
·2 No assignment will be accepted through email.
Rules for Marking:
It should be clear that your assignment will not get any credit / marks if:
·0 The assignment is submitted after due date.
·1 The submitted assignment does not open or file is corrupted.
·2 Your assignment is copied from internet, handouts or from any other student
(Strict disciplinary action will be taken in this case).
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]
Fundamentals of Algorithms CS502 Solution
