Question

In: Advanced Math

ALGORITHMS AND ANALYSIS: Show with a counterexample that the greedy approach does not always yield an...

ALGORITHMS AND ANALYSIS:

Show with a counterexample that the greedy approach does not always yield an optimal solution for the Change problem when the coins are U.S. coins and we do not have at least one of each type of coin.

Solutions

Expert Solution

A set which forms a matroid can be used to solve the coin changing problem by using greedy approach. In brief, a matroid is an ordered pair M = (S,l) satisfying the following conditions:

  1. S is a finite nonempty set
  2. l is a nonempty family of subsets of S, called the independent subsets,such that if B->l and A is a subset of B, then A -> l
  3. If A-> l, B-> l and |A| < |B|, then there is some element x-> B-A such that A U {x} ->l

In our question of coin changing, S is a set of all the coins in decreasing order value We need to achieve a value of V by minimum number of coins in S

In our case, l is an independent set containing all the subsets such that the following holds for each subset: the summation of the values in them is <=V

If our set is a matroid, then our answer is the maximal set A in l, in which no x can be further added

To check, we see if the properties of matroid hold in the set S = {25,15,1} where V = 30 Now, there are two subsets in l: A = {25} and B= {15,15} Since |A| < |B|, then there is some element x-> B-A such that A U {x} ->l (According 3) So, {25,15} should belong to l, but its a contradiction since 25+15>30

So, S is not a matroid and hence greedy approach won't work on it.

if the answer is helpful dont forget to give Thumsup


Related Solutions

Maximum-weight independent set. (a) Prove that the two greedy algorithms(i.e., Greedy and Greedy 2) are equivalent....
Maximum-weight independent set. (a) Prove that the two greedy algorithms(i.e., Greedy and Greedy 2) are equivalent. That is, they return the same output for a given input. (b) Prove that Greedy 2 returns an optimal solution to the maximum weight independent set problem by application of lemmata.
Maximum-weight independent set. (a) Prove that the two greedy algorithms, optimal substructure and activity selection are...
Maximum-weight independent set. (a) Prove that the two greedy algorithms, optimal substructure and activity selection are equivalent. That is, they return the same output for a given input. (b) Prove that Greedy 2 returns an optimal solution to the maximum weight independent set problem by application of lemmata.
True or False (proof or counterexample): In any Nash equilibrium, a player is always indifferent between...
True or False (proof or counterexample): In any Nash equilibrium, a player is always indifferent between playing any of her pure strategies.
What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in...
What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in an optimal substructure.
R exercise implement a greedy nearest-neighbour approach to find a suitable route for visiting all houses...
R exercise implement a greedy nearest-neighbour approach to find a suitable route for visiting all houses (pairs of coordinates generated). The route should be as short as possible. Starting at house 1, visit the house nearest to house 1 first. Then, each time move on to the nearest house not yet visited and, after visiting all houses, return to house 1. Suppose house 1 is at point (0,1) . Write a function called gp which will take the matrix of...
Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory,...
Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory, Algorithms, and Systems.)
I always rate! Show Excel work, please You have been asked to perform scenario analysis, sensitivity...
I always rate! Show Excel work, please You have been asked to perform scenario analysis, sensitivity analysis, and break even analysis for producing a new golf ball. These new golf balls will sell from $2 a piece. In the best case scenario you think you will sell 750,000 balls, in the most likely case you will sell 500,000 balls and in the worst case you will sell 300,00 balls. Your variable cost is 35% and you have $300,000 in fixed...
Describe the Qualitative approach to Risk Assessment. Why does this approach, which does not rely on...
Describe the Qualitative approach to Risk Assessment. Why does this approach, which does not rely on numerical data, work?
How does the life time analysis differ from the basic customer profitability approach(500 words)
How does the life time analysis differ from the basic customer profitability approach(500 words)
Can you explain this further,"  DuPont analysis is an equity evaluation approach..." In your opinion, what does...
Can you explain this further,"  DuPont analysis is an equity evaluation approach..." In your opinion, what does that mean.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT