Computing change for a given coin system, Mathematics

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.

Posted Date: 3/23/2013 1:41:28 AM | Location : United States

Related Discussions:- Computing change for a given coin system, Assignment Help, Ask Question on Computing change for a given coin system, Get Answer, Expert's Help, Computing change for a given coin system Discussions

Write discussion on Computing change for a given coin system
Your posts are moderated
Related Questions
Joe took out a car loan for $12,000. He paid $4,800 in interest at a rate of 8% per year. How many years will it take him to pay off the loan? Using the easy interest formula I

Who discovered unitary method? ?

a) The distance d that can be seen from horizon to horizon from an airplane varies directly as the square root of the altitude h of the airplane. If d = 213 km for h = 3950

#What is an easy way to find the area of any figure

Parametric Curve - Parametric Equations & Polar Coordinates Here now, let us take a look at just how we could probably get two tangents lines at a point.  This was surely not

An elliptical galaxy has gravitational boundaries defiend by 9x 2 +16y 2 +144z 2 =144. A black hole at the center of the galaxy is interacting with dark matter producing a radiatio

approximate the following problem as a mixed integer program. maximize z=e-x1+x1+(x2+1)2 subject to x12+x2 =0

A reliability system consists of 15 independent components. The probability that a component works is 0.9 for each. The system works if at least 11 of the components work. Fi

Poisson Mathematical Properties 1. The expected or mean value = np = λ Whereas; n = Sample Size p = Probability of success 2. The variance = np = ? 3. Standard dev