Computers and Technology, 30.06.2019 11:30 myla18jabbar

Consider the problem of making change for n cents using the fewest number of coins. assume that each coin's value is an integer. a. describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. prove that your algorithm yields an optimal solution. b. suppose that the available coins are in the denominations that are powers of c, i. e., the denominations are c0, c1, , ck for some integers c > 1 and k % 1. show that the greedy algorithm always yields an optimal solution. c. give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. your set should include a penny so that there is a solution for every value of n. d. give an o(nk)-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.

Answers: 1

Show answers

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 11:00, babbybronx

Lisa’s company, abc ltd., lost its biggest client and is now facing a financial crunch. most of her colleagues have resigned, but lisa decides to stay with the company and assist the management in overcoming the financial situation. which quality is lisa demonstrating? a. self-management b. cooperativeness c. responsibility d. loyalty

Answers: 2

continue

Computers and Technology, 23.06.2019 11:00, jolleyrancher78

What are the possible consequences of computer hacking? what is computer piracy? describe some examples. what are the effects of computer piracy? what are the possible consequences of computer piracy? what is intentional virus setting? describe some examples. what are the effects of intentional virus setting? what are the possible consequences of intentional virus setting? what is invasion of privacy? describe some examples. what are the effects of invasion of privacy? what are the possible consequences of invasion of privacy? what is an acceptable use policy and what is the purpose of the acceptable use policy what is intellectual property and how can you use it?

Answers: 1

continue

Computers and Technology, 24.06.2019 07:20, djs1002

Ingrid started speaking about her slide presentation. when she clicked to th"third slide, which had just a picture of an elephant, she forgot what she wassupposed to talk about. what could ingrid do to avoid this situation in thefuture? oa. print handouts for her audience. ob. add presenter's notes to each slide. oc. add a video to each slide. od. save her slide presentation to a flash drive

Answers: 2

continue

Computers and Technology, 24.06.2019 12:40, kanga06

Match the feature to the network architecture. expensive to set up useful for a small organization easy to track files has a central server inexpensive to set up difficult to track files useful for a large organization does not have a central server client- server network peer-to-peer network

Answers: 3

continue

You know the right answer?

Consider the problem of making change for n cents using the fewest number of coins. assume that each...