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
2.2 "Our business model works even if all internet software is free ....... We are still selling operating systems. What does Netscape''s business model look like? Not very good."

If a supply curve goes through the point P = $10 and Qs = 320, then a. $10 is the highest price that will induce firms to supply 320 units b. $10 is the lowest price that wil

If a nation were to experience an influx of foreign labor into the market for corn production, the production possibilities frontier for the nation would: a. shift inward due to

a health club sells 50 memberships when the monthly price is $60 and 70 memberships when the monthly price is $40. the price elasticity of demand for memberships at this health clu

Q. Explain the long-run Phillips curve? The long-run Phillips curve The augmented Phillips curve has an important consequence: the long-run Phillips curve must be vertical

You are considering three design alternatives for treating a pollutant in wastewater using a first-order process ( k = 1 min -1 ). The total flow is 10 million gallons per day (mg

I am in a college econ class that I may possibly fail. anyone able to explain how to find this answer? Assume that the following data characterize the hypothetical economy of Tran

If a social entrepreneur is relying on contributions, are there not risks in being accountable and using that money wisely?

A local movie theater wants to know how much popcorn they should stock for a given movie showing. Records from 94 movies reveal a mean of 57 boxes and a standard deviation of 17.8.

State in brief the Nominal wage level In macroeconomics, we are generally not interested in the wage for a specific individual though in the average wage for all employed indi