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
Balls are arranged in rows to form an equilateral triangle .The first row consists of one ball, the second two balls and so on.   If 669 more balls are added, then all the balls ca

Q. Scaling and translation for equations? Ans. If you have an equation in the form y= f(x) (if you're not familiar with functions, that just means having "y" on the left s

Decision Trees And Bayes Theory This makes an application of Bayes' Theorem to resolve typical decision problems. It is examined a lot so it is significant to clearly understan

Q. Draw Grouped Frequency Tables? Ans. Grouped frequency tables are often used when there are many different values. In these tables, the values are grouped into classes

an insurance salesman sells policies to 5 men, all of identical age in good health. the probability that a man of this particular age will be alive 20 years hence is 2/3.Find the p

principal=2000 rate=5% time=2 years find compound interest

how i found largest cluster in percolation

i dont get these questions they are hard for me

Describe the distribution of sample means shapefor samples of n=36 selected from a population with a mean of μ=100 and a standard deviation of o=12.  , expected value, and standard