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. Define Effective exchange rate? Suppose that we are interested in external competitiveness of a country, let's say Japan. To do this we could look at evolution of a particul

Q. Explain about Quantity theory of money? One of the main elements of the classical model is quantity theory of money. Quantity theory of money connects three important variab

Analyze how a model of the labor market can be used to explain wage and employment for healthcare workers.

Suppose that Michael and Dwight each have a $60 weekly entertainment budget. They pay the same prices for two goods, "an evening reading books" (an ERB) and "an evening of beer and

If Country A had four times the initial level of real GDP per capita of Country B and it was growing at 1.4 percent a year, while real GDP was growing at 2.3 percent in Country B,

Q. Show the components of GDP? The circular flow - simple version We have defined GDP, gross domestic product, as the market value of all finished service and goods produced

Explain the Economic functions of money - A unit of account In a monetary economy, all prices may be expressed in monetary units which everyone may relate to. Without money,

5. In this question you should assume that the Marginal Propensity to Consume out of permanent income is one [i.e., no bequest motive + perfect consumption smoothing: c1, = c2 = c

What is Inherent Limitation?

A company can lease an asset for the next five years by making lease payments that are equivalent to annual payments of $3,000 at year 0, $6,000 at year 1, $7,000 at year 2, $7,000