CSC 344
Homework 5

Assigned Apr. 25, due May 4

• Solve problems 8.12 and 8.21 in the textbook.

• Find and analyze an algorithm to determine whether a directed graph is strongly connected (i.e. it's possible to get from any vertex to any other vertex). Hint: it's easy to do this in O(n(n+m)) time; for full credit, do it in O(n+m) time.

• Extra credit: Implement a greedy algorithm for making change with as few coins as possible, using your favorite programming language.

  The input is a positive integer (the amount of change to be made) and a list (or array) of positive integers specifying the values of the coins available. You may produce output in either of two forms (your choice, but tell me which one you're doing):

  • a list (or array) of coin values, possibly repeating, that add up to the specified amount of change, or
  • a list (or array) the same size as the array of coin values specifying how many of each coin to use.
  You may assume that the coin values are given in decreasing order, and that the last one is 1 (which, by the way, guarantees that there is a solution).
  For example, to make 63 cents' change with quarters, dimes, nickels, and pennies, one might call (in Scheme, using the first output form)

  (make-change 63 (list 25 10 5 1))
  

  and get the answer (list 25 25 10 1 1 1).
  Or in Java, using the second output form,

   int[] coins = {25,10,5,1};
   int[] answer = makeChange(63,coins);
   // answer should now be the 4-element array {2,1,0,3} indicating 
   // 2 quarters, 1 dime, 0 nickels, and 3 pennies.
  

• Extra credit: Implement Dijkstra's algorithm for finding shortest paths in a weighted, undirected graph, using your favorite programming language.

  The input is an edge-weighted graph (in either adjacency-matrix or adjacency-list form; your choice) and a vertex of the graph. The output is an array or list specifying the minimum distances to all the vertices in the graph.
  For example, in Java, you might choose to represent the graph as an n-by-n, two-dimensional array of doubles, representing the absence of an edge by the predefined value Double.POSITIVE_INFINITY; the "source vertex" parameter would be an int, and the result would be a one-dimensional array of doubles.

• Extra extra credit: The greedy algorithm for making change, implemented above, doesn't always produce correct answers. For example, if asked to make 30 cents' change with quarters, dimes, and pennies, the above greedy algorithm chooses 1 quarter and 5 pennies, even though 3 dimes would do the job with fewer coins. Design, implement, and analyze an algorithm that really solves the problem, producing optimal solutions in all cases. The input and output are exactly the same as above.