Description
Question 1. (10 points) Recall the coin changing problem and the cashier’s algorithm we studied
in class. Suppose we are given coin denominations that are powers of some number c, i.e., the denominations are c
0
, c1
, . . . , ck
for some positive integers c > 1 and k ≥ 1. Prove that the cashier’s
algorithm will always yield an optimal solution when given such coin denominations. (You do not
need to restate cashier’s algorithm here and do not need to analyze its time complexity.)
Question 2. (10 points) Exercise 2 from Chapter 4, page 189 of the textbook.
Question 3. (10 points) Exercise 3 from Chapter 4, pages 189-190 of the textbook.
Question 4. (10 points) Exercise 6 from Chapter 4, page 191 of the textbook.
Question 5. (10 points) Given an edge-weighted digraph G = (V, E) with positive edge-lengths
and two nodes u, v ∈ V , provide a polynomial-time algorithm to determine if there is a unique
(i.e., only one) shortest path from u to v in G.