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
Q. Relation between Money - wealth and income? Money isn't the same as wealth. An individual may be very wealthy however have no money (for instance by owning stocks and real e

What are the pros and cons of reducing dependence on outsourcing in order to fulfill social obligations toward stakeholders?

Subsidy programs are likely to have a number of secondary effects in addition to the direct effect on dairy prices. What impact do you suppose farm subsidies are likely to have on

THE GOALS OF MACROECONOMIC POLICY  Economic analysis attempts to explain why problems arise in the economy and how these problems can be dealt with. It is, therefore, indispens

Debate between New Classical and New Keynesian economics?

If income falls below its potential and the income tax rate is reduced, this will: A. raise the passive deficit but reduce the structural deficit. B. raise both the passive and str

Illustrate the problem for UK economic performance This is a foremost problem for UK economic performance and helps elucidate the persistent deficit on the current account of

a) Get the latest data for each of the following variables for France in 2011: 1. Nominal GDP 2. Real GDP (Y) 3. Consumption (C) 4. Investment (I) 5. Government purchases (G)

INTRODUCTION TO DEMAND ANALYSIS: It is generally seen that market demand curve is downward sloping. Market demand curve (or sometimes called Aggregate demand curve) is nothing

Each Home Depot store must decide how much paint to order each month. From historical records, they know that the amount of paint they sell during May is distributed as follows: th