COSC 311 Algorithms Mini 5 Solutions

COSC 311: A LGORITHMS M INI 5 Solutions 1. Making Change. Consider the following non-standard coin denominations: 1¢ 4¢ 7¢ 12¢ Suppose we are making change for 33¢. (a) What set of coins will the greedy algorithm output? Solution: The greedy algorithm will always choose the biggest “step” that does not violate the goal - in this problem, that means choosing the largest coin that does not put our running sum over the limit of 33¢. So, the first choice our algorithm would make would be to choose 12¢, making our sum = 12¢. Then we’ll choose 12¢ again, making our sum = 24¢. We’ll try to choose 12¢ again, but this would put our sum = 36¢ > 33¢, and thus we’ll reject this option. So, instead we’ll try choosing 7¢, putting us at sum = 31¢. We notice that we now cannot choose 12¢, 7¢, or 4¢, for all of these options will put us over sum = 33¢. So our only option now is to choose two 1¢ coins to get our sum = 12 + 12 + 7 + 1 + 1 = 33¢. Overall, using the greedy algorithm, we get the solution that we have to use 5 coins to give change for 33¢. (b) Is this optimal? If not, what is the optimal way to make change for 33¢ using this set of coins? Solution: It is not difficult to see that with these denominations, we can reach 33¢ in only 4 coins: 12 + 7 + 7 + 7. This means that our greedy algorithm did not give us the optimal solution. 2. Solution structure. What does it mean for a problem to have the optimal substructure property? Solution: A problem is said to have the optimal substructure property if the optimal solution to our original problem contains within it optimal solutions to subproblems. In other words: Suppose we take an optimal solution to the problem and break it up into multiple pieces. Each piece of the solution is itself a solution to some subproblem. And the piece of the solution must be an optimal solution to its corresponding subproblem. In still other words: Suppose we come up with some “good” way of splitting up our problem into subproblems, and then we find the solutions to those “good” subproblems; if we then combine these solutions, we should get an optimal solution to the original problem. Consider the problem we have in part 1, where we are trying to make change for 33¢. As we’ve seen, an optimal solution is 12¢, 7¢, 7¢, 7¢, which uses 4 coins. Now let’s take that optimal solution and split it up into two pieces. One way of doing this is to put 12¢ and 7¢ in one pile (which 1 has total value 19¢) and 7¢ and 7¢ in another pile (which has total value 14¢). The optimal substructure property says that there cannot be a way to make change for 19¢ that uses fewer than two coins. If there were, we could replace the first pile with fewer than two coins, which would give us a solution to our original problem of making change for 33¢ using fewer than four coins. But this is not possible since four coins was optimal. This tells us that the optimal substructure property is satisfied. (In this case, the greedy algorithm is not optimal because the greedy choice property is violated: for example, when making change for 14¢ there is no optimal solution that involves a 12¢ coin, even though 12¢ is the greedy choice.) 3. Shortest Paths. Here’s a graph: Fill in the table to show the execution of Dijkstra’s algorithm on this graph to find the shortest path from node s to all other nodes. Each row should show T (the partial spanning tree), and U , the set of nodes that are unvisited (including the best distance found so far from s to all nodes in U ). The first row shows, as an example, what T and U look like after only s has been visited. After iteration T (partial solution) ({nodes}, {edges}) U (unvisited nodes) (node,dist,parent) 1 ({s}, ∅) (t, 4, s), (u, ∞, ∅), (v, 1, s), (w, ∞, ∅), (x, ∞, ∅) 2 ({s, v}, {(s, v)}) (t, 2, v), (u, ∞, ∅), (w, 6, v), (x, ∞, ∅) 3 ({s, v, t}, {(s, v), (v, t)}) (u, 3, t), (w, 6, v), (x, ∞, ∅) 4 ({s, v, t, u}, {(s, v), (v, t), (t, u)}) ({s, v, t, u, x}, {(s, v), (v, t), (t, u), (u, x)}) ({s, v, t, u, x, w}, {(s, v), (v, t), (t, u), (u, x), (u, w)}) (w, 5, u), (x, 4, u) 5 6 2 (w, 5, u) (empty)