Homework 6
1 Minimum Spinning Tree
Finish question 1 on https://www.educoder.net/classrooms/9025/shixun_homework/.
2 Coin changing
Consider the problem of making change for n cents using the fewest number of coins. Assume
that each coin’s value is an integer. We recommend to read the chapter 6 of book ”Introduction
to Algorithms”(3rd Edition).
• a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels and
pennies. Please give the pseudocode, and 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 c
0
; c
1
; · · · ; c
k
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.
3 Due
1. Due is Nov. 1st, 23:59.
2. Question 2 is a writing assignment, submit a PDF on the canvas.
1
