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
Describe the meaning of word -Investment When we use the word investment, we generally mean "gross investment". Essentially, gross investment comprises all finished goods which

Can the government always reduce the budget deficit by simply increasing taxes? Why or why not? Please explain your answer using the Laffer curve. In addition, use research and sho

applicability of the lewis model in developing countries

To determine whether high blood pressure affected whether a person had a stroke, a sample of 300 people who had had strokes are examined. In the sample, 37% had high blood pressure

Q. Explain about IS-LM-model? The key difference between the IS-LM model and the cross model is that nominal interest rate is exogenous in cross model on the other handit is en


The demand for money schedule shows that the quality of money that people want to hold

A vital question is whether the equilibrium we have identified in labor market (with a high unemployment rate) can remain in long run. Will there not be adjustments which will take

For retirement planning, you decided to deposit $1,000 per month and increase your deposit by $100 per month. How much will you have at the end of 10 years if the bank pays 3% annu

One alternative way to calculate the total change in money supply when the Fed injects money into the economy or takes away money from the economy is the amount of money injected o