Describe an algorithm which gives initial amount , Macroeconomics

Assignment Help:

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.


Related Discussions:- Describe an algorithm which gives initial amount

Determine elasticity of demand , Consider the consumption decisions of R.B....

Consider the consumption decisions of R.B. Turbo, a new student at T University. Ms. Turbo has only available $1,000 in monthly income to spend on food and housing. In te

Calculate competitive equilibrium quantity, Assume a competitive industry w...

Assume a competitive industry with two hospitals. The hospitals compete in price (such that P = MC ), face the inverse demand curve =10 - Q , and have a constant marginal cost of

Determine the inflation rate in germany between 1992-2010, Inflation in Ger...

Inflation in Germany Once we have monthly data on a price index we can calculate inflation. In most nations, the percentage change in price index during one month is small. So,

What do learn by study of the supply curve concepts, What do learn by study...

What do learn by study the supply curve concepts? a. The relationship in between quantity of inputs and output b. Why production is frequently subject to reducing  returns

New screening methods adopted price do you exect prevail, You are the manag...

You are the manager of an organization in America that distributes blood to hospitals in all 50 states and the District of Columbia. A recent report indicates that nearly 50 Americ

What has served as money?, As people went from barter societies to more adv...

As people went from barter societies to more advanced economies, money had to be invented. Several things successively served as money in the course of economic evolution. Arrowhea

Government can finance its budget deficit, A government can finance its bud...

A government can finance its budget deficit by doing all of the following except: A. borrowing from its central bank. B. printing money. C. selling bonds. D. buying bonds.

Mec, discuss mec

discuss mec

Define the multiplier and rate of inflation, 1 (a) List two concerns with i...

1 (a) List two concerns with inflation. (b) Suppose that we are in a condition of fully flexible prices, but production of nails will not go above 200 chairs/month. What price w

Explain fines imposed on violations, In 2001, Puerto Rico enacted a law tha...

In 2001, Puerto Rico enacted a law that requires specific labels on cement sold in Puerto Rico and imposes fines for any violations of these requirements. The law prohibits the sal

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd