Give an instance of the making-change problem

Assignment Help Computer Engineering
Reference no: EM132139791

Question :

Suppose that the coins of the fictional country of Combinatoria come in the de- nominations, d1, d2, . . . , dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins whose values sum to n.

(a) Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm, which repeatedly chooses a highest-valued coin whose value is at most n until the sum of chosen coins equals n. (writeup only)

(b) Implement the algorithm for the coin changing problem. Take as input a file with a set of denominations. Interactively ask the user for the amount he wants to make change for and print the number of coins and the actual change.

Reference no: EM132139791

Questions Cloud

Fifty-seven percent of employees make judgements : Fifty-seven percent of employees make judgements about their co-workers based on the cleanliness of their desk.
Test scores on the law school admission test : What is the probability that the mean of 12 randomly selected scores is less than 161?
For which values of n does insertion sort beat merge sort : For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlgn steps.
Calculate the project initial investment costs : Calculate the project's initial investment costs, annual incremental operating cash flows, and terminal cash flows. What are project's NPV and IRR
Give an instance of the making-change problem : Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm.
What is the probability that at least : If you select 31 customers, what is the probability that at least 20 of them have looked at their score in the past six months?
Discuss about the computer security consulting services : Determine whether you would employ a hierarchical, a flat, or a matrix organizational structure, and explain why.
Show your structure before and after the deletion : A B+ tree in which the deletion of the value 42 leads to a redistribution. Show your structure before and after the deletion.
What is the cutoff score for the top : Students scoring in the top 18% get an A. What is the cutoff score for the top 18% in this example?

Reviews

Write a Review

Computer Engineering Questions & Answers

  Mathematics in computing

Binary search tree, and postorder and preorder traversal Determine the shortest path in Graph

  Ict governance

ICT is defined as the term of Information and communication technologies, it is diverse set of technical tools and resources used by the government agencies to communicate and produce, circulate, store, and manage all information.

  Implementation of memory management

Assignment covers the following eight topics and explore the implementation of memory management, processes and threads.

  Realize business and organizational data storage

Realize business and organizational data storage and fast access times are much more important than they have ever been. Compare and contrast magnetic tapes, magnetic disks, optical discs

  What is the protocol overhead

What are the advantages of using a compiled language over an interpreted one? Under what circumstances would you select to use an interpreted language?

  Implementation of memory management

Paper describes about memory management. How memory is used in executing programs and its critical support for applications.

  Define open and closed loop control systems

Define open and closed loop cotrol systems.Explain difference between time varying and time invariant control system wth suitable example.

  Prepare a proposal to deploy windows server

Prepare a proposal to deploy Windows Server onto an existing network based on the provided scenario.

  Security policy document project

Analyze security requirements and develop a security policy

  Write a procedure that produces independent stack objects

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g.

  Define a suitable functional unit

Define a suitable functional unit for a comparative study between two different types of paint.

  Calculate yield to maturity and bond prices

Calculate yield to maturity (YTM) and bond prices

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