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

Negotiations between customers, In 1999 Mercedes-Benz USA adopted a new pri...

In 1999 Mercedes-Benz USA adopted a new pricing policy, which it called NFP (negotiation-free process), that sought to eliminate price negotiations between customers and new-car de

Effect of a large federal deficit on interest rates, Explain, using the bes...

Explain, using the best framework you can think of (based on our class discussion), the effect of a large federal deficit on interest rates.

Trade, What is the difference between heckscher_olin theory and comparative...

What is the difference between heckscher_olin theory and comparative theory

#title.homework help, 1) Why does the adoption of Keynesian economics come ...

1) Why does the adoption of Keynesian economics come out of the Great Depression? 1) Why does the adoption of Keynesian economics come out of the Great Depression? 2) What will ha

Production function and growth, Q. Production function and Growth? From...

Q. Production function and Growth? From the simple production function Y = f(L, K), we can classify three sources of growth:  An increase in L. An increase in K.

What are economic growth and the growth rate, What are economic growth and ...

What are economic growth and the growth rate? Economic grow: It rise in a country is real level of national output like measured through Gross Domestic Product (GDP). Wh

Consumer Price Index, What is the formula for consumer price index?

What is the formula for consumer price index?

Process to calculate gross domestic product, process to calculate gross dom...

process to calculate gross domestic product We just include finished goods and services - which is, anything that is sold directly to consumer. Electric power sold to a steel m

How can we define the real wage as nominal wage, How can we define the real...

How can we define the real wage as nominal wage We define real wage as nominal wage divided by a price index (typically CPI). In the illustration above, your real wage was 20 i

Model Questions Required, 1) Assume that the production function for New Ze...

1) Assume that the production function for New Zealand is given by Y = AK0.57L0.43, where Y is real GDP (in 2000 constant dollars), K is real capital stock, L is labour. The parame

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