Design greedy algorithm for making change after someone buys

Assignment Help Computer Engineering

Reference no: EM131841653

Problem

Design a greedy algorithm for making change after someone buys some candy costing x cents and the customer gives the clerk $1. Your algorithm should try to minimize the number of coins returned.

a. Show that your greedy algorithm returns the minimum number of coins if the coins have denominations $0.25, $0.10, $0.05, and $0.01.

b. Give a set of denominations for which your algorithm may not return the minimum number of coins. Include an example where your algorithm fails.

Reference no: EM131841653

Questions Cloud

Calculate what is the running time of your algorithm : Give an efficient algorithm for determining if a pattern P is a subsequence (not substring) of a text T. What is the running time of your algorithm?

Reflective paper on class-status-power-ethnicity : Choose ONE topic from the following: class, status, power, ethnicity, age or gender. You can use imagery/creative medium to reflect on their role

What should rutherford do now : What conclusions do you reach? Is there evidence of discrimination in promotion decisions?

Write a reflective paper highlighting using the format : Choose ONE topic from the following: class, status, power, ethnicity, age or gender. You can use imagery/creative medium to reflect on their role as health

Design greedy algorithm for making change after someone buys : Design a greedy algorithm for making change after someone buys some candy costing x cents and the customer gives the clerk $1.

Internal and external response to the bribery charges : How would you characterize Walmart's internal and external response to the bribery charges?

Calculate the number of jovian days in one jovian year : a). Calculate the number of jovian days in one jovian year b). Verify by calculation the magnitude of the synodic period of Pluto

How many books must be sold to break even : A book publisher has fixed costs of $360,000 and variable costs per book of $11.00. The book sells for $27.00 per copy.

Define the edit distance between two strings x and y : Define the edit distance between two strings X and Y of length n and m, respectively, to be the number of edits that it takes to change X into Y.

User Account

All Pages