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

Conditional probability - rules of probability, Conditional probability - R...

Conditional probability - Rules of Probability This is the probability associated with combinations of events but given that some prior result has already been achieved with o

Characteristics and limitations of moving average, Characteristics and Limi...

Characteristics and Limitations of moving average Characteristics of moving average 1) The more the number of periods in the moving average, the greater the smoothing

Find the probability density function, 1. The lifetime T (in days) of an el...

1. The lifetime T (in days) of an electrical component has reliability function given by: R(t) = e -0.01t for time t > 0. An electrical system consists of four such components. Th

Find a minimum cost spanning arborescence rooted, Find a minimum cost spann...

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class.  Please show your work, and also give a final diagram w

Calculate combinations and permutations, a. Cassie has seven skirts, five b...

a. Cassie has seven skirts, five blouses, and ten pairs of shoes. How many possible outfits can she wear? b. Cassie decides that four of her skirts should not be worn to school.

The definite integral- area under a curve, The Definite Integ...

The Definite Integral Area under a Curve If there exists an irregularly shaped curve, y = f(x) then there is no formula to find out

Geometry, all basic knowledge related to geometry

all basic knowledge related to geometry

Fundamental theorem of calculus, Fundamental Theorem of Calculus, Part II ...

Fundamental Theorem of Calculus, Part II Assume f ( x ) is a continuous function on [a,b] and also assume that F ( x ) is any anti- derivative for f ( x ) . Then,

Conclusion of egroff''s theorem and lusin''s theorem, (1) Show that the con...

(1) Show that the conclusion of Egroff's theorem can fail if the measure of the domain E is not finite. (2) Extend the Lusin's Theorem to the case when the measure of the domain E

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