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.

Hint on problem 3: Suppose that the input is n=4, c=2, A=53 (meaning four coins, growing exponentially in 2, that is, {1, 2, 4, 8}, and 53 cents as the amount). The output would be (1,0,1,6), meaning:

The input consists of n, c, and the amount A. The output is a list of the numbers of coins of each denomination that sums to A.

Posted Date: 3/28/2013 6:19:14 AM | Location : United States

Ask an Expert

Related Discussions:- Describe an algorithm which gives initial amount , Assignment Help, Ask Question on Describe an algorithm which gives initial amount , Get Answer, Expert's Help, Describe an algorithm which gives initial amount Discussions

Write discussion on Describe an algorithm which gives initial amount
Your posts are moderated

Write your message here..

Related Questions

Expenditure methods, Expenditure method is also called Flow-of-Expenditure ... Expenditure method is also called Flow-of-Expenditure method, consumption and investment method, income Disposal method, etc. Expenditure method measures the final expenditure

Expected cost of building the boat, Half the members of a fishing tribe cat... Half the members of a fishing tribe catch four fish per day and half catch 10 fish per day. A group of 10 members could build a boat for another tribe in one day and receive a paym

Long-run framework, In the long-run framework, deficits reduce: A. investme... In the long-run framework, deficits reduce: A. investment. B. taxes. C. government consumption. D. subsidies.

Electrical company audit indicates that motor consumption, An electrical co... An electrical company audit indicates that motor consumption is 4x106 kWh per year. By upgrading to high efficiency motors a 10% savings can be made. The additional cost for the mo

Compare and contrast federal government expenditures, Compare and contrast ... Compare and contrast federal government expenditures, state and local government expenditures, and financing government expenditures. Suggest a total of three actions that should b

Price, The prices of fresh fruits have risen recently in the Jackson area. ... The prices of fresh fruits have risen recently in the Jackson area. Why would this have occurred? Explain.

Consumption and GDP, At first, it may seem obvious that consumption will re... At first, it may seem obvious that consumption will rely on Y. If GDP is doubled in real terms over a number of years, government consumption, private consumption and investment wi

Keynesian Model, according to the Keynesian model, the short-run aggregate ... according to the Keynesian model, the short-run aggregate supply curve is horizontal when: A: there are unemployed resources and prices do not fall when aggregate demands falls. B:

KEYNESIAN CROSS MODEL, In the keynesian cross model, assume the consuption ... In the keynesian cross model, assume the consuption function is given by C=200=.75(Y-T) and planned investment=100, government purchases and taxes are each of them 100. a) Draw a g

Summary of the cross model, Summary of the cross model The below list... Summary of the cross model The below list summarizes the cross model and associates it to classical model:  Labor Market: Real wages W/P is exogenous in cross model