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
For inequalities we contain a similar notation.  Based on the complexity of the inequality the solution set might be a single number or it might be a range of numbers. If it is jus

Find the GCF of 70 and 112

Probability - Applications of integrals In this final application of integrals that we'll be looking at we are going to look at probability.  Previous to actually getting into

Theorem a → • b → = ||a → || ||b → || cos• Proof Let us give a modified version of the diagram above. The three vectors above make the triangle AOB and note tha

creative assignment about sets

what is the benefit for stakeholders or disadvantage in a monoply

Correlation coefficient - These are numerical measures of the correlations existing between the independent and the dependent variables - These are better measures of corre

Mike sells on the average 15 newspapers per week (Monday – Friday). Find the probability that 2.1 In a given week he will sell all the newspapers

Find out the volume of the solid obtained by rotating the region bounded by y = x 2 - 4x + 5 , x = 1 , x = 4 , and the x-axis about the x-axis. Solution : The firstly thing t

A farmer grows apples on her 400-acre farm and must cope with occasional infestations of worms. If she refrains from using pesticides, she can get a premium for "organically grown"