# Question: Consider the problem of making change for n cents using

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.

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.

a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

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.

**View Solution:**## Answer to relevant Questions

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.Specifically, ...In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to ...Give a dynamic-programming solution to the 0–1 knapsack problem that runs in O (n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack.When an adjacency-matrix representation is used, most graph algorithms require time Ω (V2), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink-a vertex with ...State the type rules for the assignment (“: =”) and equality comparison (“=”) operators.Post your question