Describe an algorithm which gives initial amount , Macroeconomics

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







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
Related Questions
The NJ Bureau of Employment gathered the following sample information on the number of hours unemployed workers spent looking for work last week. Hours Spent Searching Number of Un

he questions posed are broad and open ended so be careful to allow yourself enough research and planning time. If you are completely on top of the material delivered in class, then

illustrate and discuss the implications of variou market structures (competitive and noncompetitive) for price determination

Debate between New Classical and New Keynesian economics?

What do I calculate with quantity of each good produced, to find the Real GDP?

Liberalisation and Changing Sources of FDI: European countries  had been major sources of FDI inflows  to India until 1990. However, their relative importance declined in the

What is the difference in changing the scope between a spiral approach and a waterfall approach? Ans) The scope of needs changes in Waterfall model is less than that in Spiral M

Minimum wage laws are common in many countries. The debate over minimum wage includes claims about the impact of this action on employment levels and wage levels. What impact does

Oil price shocks lead to large adverse supply shocks in the macroeconomy, infer Dornbusch et al (2008) who define an adverse supply shock as; ‘one that shifts the aggregate supply

Q. Show the analysis of cross model? We can divide our analysis of cross model into three sections:  Aggregate demand. Aggregate demand is a major component of cross mo