Computing change for a given coin system, Mathematics

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.


Related Discussions:- Computing change for a given coin system

What is the smaller probable value of this number, The sum of the square of...

The sum of the square of a number and 12 times the number is -27. What is the smaller probable value of this number? Let x = the number.  The statement that is "The sum of the

Tower of hanoi problem, a) Write  a summary  on  Tower  of  Hanoi  Probl...

a) Write  a summary  on  Tower  of  Hanoi  Problem.  How  can  it  be solved using  recursion ?                  b) Amit goes to a grocery shop and purchases grocery for Rs. 23.

Metric space, Assume that (X, d) is a metric space and let (x1, : : : , x n...

Assume that (X, d) is a metric space and let (x1, : : : , x n ) be a nite set of pointsof X. Elustrate , using only the de nition of open, that the set X\(x1, : : : , x n ) obtain

Pair of straight lines, how to solve the problems? methods to solve the que...

how to solve the problems? methods to solve the question of joint lines

How do you traverse a binary tree, How do you traverse a Binary Tree?  Desc...

How do you traverse a Binary Tree?  Describe Preorder, Inorder and Postorder traversals with example.     Ans: Traversal of tree means tree searching for a aim. The aim may be

Sketch the plot first-order integrated rate, Show that the first-order inte...

Show that the first-order integrated rate expression can be written as [A] t = [A] 0 e -n(in)t where n represents the number of elapsed halftimes. Sketch the plot of [A] 1

About matrix?, Explain sparse matrix and Dense matrix?

Explain sparse matrix and Dense matrix?

Find out the slope of equations, Example:  find out the slope of equations ...

Example:  find out the slope of equations and sketch the graph of the line.                         2 y - 6x = -2 Solution To get the slope we'll first put this in slope

Homogeneous system , Provided a homogeneous system of equations (2), we wil...

Provided a homogeneous system of equations (2), we will have one of the two probabilities for the number of solutions. 1.   Accurately one solution, the trivial solution 2.

Large samples, LARGE SAMPLES These are samples that have a sample size ...

LARGE SAMPLES These are samples that have a sample size greater than 30(that is n>30) (a)   Estimation of population mean Here we suppose that if we take a large sample

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