Algorithm Analysis Question 4a and 4b) Give an example of a coin changing proble

Question

Algorithm Analysis Question 4a and 4b)

Give an example of a coin changing problem for which the greedy algorithm does not work. Specify the denominations of coins and the amount. (b) Circle True or False in the following: (i) If a tree has n nodes then it has n -1 arcs.. True False (ii) The complexity of Prim's algorithm for a network of n nodes is Theta (n^3). True False (c) Consider the network shown in the figure below. Use Prim's algorithm (greedy algorithm) to obtain a minimum cost spanning tree.

Explanation / Answer

(a)

Let the coin denominations be 1,7,10. Let the amount be 14.

So in greedy method the answer will be 10,1,1,1,1.

The optimal solution is 7,7.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---