Computing change for a given coin system, Mathematics

Assignment Help:

This problem involves the question of computing change for a given coin system. A coin system is defined to be a sequence of coin values v1 < v2 < . . . < vn, such that v1 = 1. For example, in the U.S. coin system we have six coins with values h1, 5, 10, 25, 50, 100i. The question is what is the best way to make change for a given integer amount A.

(a) Let c ≥ 2 be an integer constant. Suppose that you have a coin system where there are n types of coins of integer values v1 < v2 < . . . < vn, such that v1 = 1 and, for 1 < i ≤ n, vi = c · vi-1. (For example, for c = 3 and n = 4, an example would be h1, 3, 9, 27i.) Describe an algorithm which given n, c, and an initial amount A, outputs an n-element vector that indicates the minimum number of coins in this system that sums up to this amount. (Hint: Use a greedy approach.)

(b) Given an initial amount A ≥ 0, let hm1, . . . ,mni be the number of coins output by your  algorithm.

Prove that the algorithm is correct. In particular, prove the following:

(i) For 1 ≤ i ≤ n, mi ≥ 0

(ii) Pn

i=1mi · vi = A

(iii) The number of coins used is as small as possible Prove that your algorithm is optimal (in the sense that of generating the minimum number of coins) for any such currency system.

(c) Give an example of a coin system (either occurring in history, or one of your own invention) for which the greedy algorithm may fail to produce the minimum number of coins for some amount.

Your coin system must have a 1-cent coin.


Related Discussions:- Computing change for a given coin system

Arden''s Theorem, Find the Regular Grammar for the following Regular Expres...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Determine the equation of the line, Example :  Determine the equation of th...

Example :  Determine the equation of the line which passes through the point (8, 2) and is, parallel to the line given by 10 y+ 3x = -2 Solution In both of parts we are goi

Obtain the equation of the diagonals, the sides of a quad  taken at random ...

the sides of a quad  taken at random are     x+3y-7=0              x-2y-5=0 3x+2y-7=0               7x-y+17=0  obtain the equation of the diagonals

Introduction to addition and subtraction, INTRODUCTION :  When a child of ...

INTRODUCTION :  When a child of seven isn't able to solve the sum 23+9, what could the reasons be? When she is asked to subtract 9 from 16, why does she write 9 - 16 = 13 ?

High self-esteem helps learning-how do children learn?, High Self-esteem He...

High Self-esteem Helps Learning :  Consider Ajay, a student of Class 2. He is constantly told by his irritated father, "How stupid you are! You don't even understand this! Even yo

Determine rank correlation coefficient , Determine Rank Correlation Coe...

Determine Rank Correlation Coefficient A group of 8 accountancy students are tested in Quantitative Techniques and Law II.  Their rankings in the two tests were as:

One integer is four times other what is the value of lesser, One integer is...

One integer is four times other. The sum of the integers is 5. What is the value of the lesser integer? Let x = the lesser integer and now let y = the greater integer. The ?rst

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd