CS 60, Assignment 13

Computer Science 60
Principles of Computer Science
Fall 2009

Assignment 13: The "Ultimate" Assignment: Algorithms!
Due Thursday, December 10 at 11:59 PM

A Few Notes on This Assignment:

This assignment is all about algorithms, and dynamic programming in particular. As a "capstone" assignment for this course, we are not providing you with starter code but you are certainly welcome to look back at some of the code that you have written over this semester, the starter code that we've provided for previous assignments, as well as documentation on Java that you can find linked from the course website. In particular, you might want to refer to Assignment 6's starter code for examples of how to read from files. Remeber that the "import" statements at the top are important too. While looking on the web for Java syntax is fine, looking for solutions to these problems (although unlikely to be fruitful) is, of course, not permitted.

Naturally, a signficant part of your score on this problem will be for the design of your code. Make sure to break up the functionality of your Java programs into logical modules, each one with its own separate function. Give your functions and variables meaningful names and keep your code as simple and elegant as possible. Finally, make sure to have at least a few lines of comments for each function, explaining what it takes in as input and what it does.

Part 1: Change, Inc. [15 Points, Individual only]

You have been hired by Change, Inc., a pioneer in the business of making change. Our motto is "Making positive change throughout the world!". (Strictly speaking, the change is only "non-negative" since 0 change is possible, but this was a nuance that the PR folks chose to ignore.) Your job is to write software for making change in any given currency system using the least number of coins/bills. This software will be embedded in cash registers and used to inform tellers how to make change optimally. Throughout this problem, you should assume that every currency system will have a 1 unit coin (e.g. a penny), so that it is always possible to make change for any amount. You should also assume that the coins in the currency system are always given to use from lowest to highest value.

Your boss, Professor I. Lai, believes that a simple recursive algorithm for this problem will be fast enough for use in the company's cash registers. Although you are skeptical, Prof. Lai is the boss! Your first task, therefore, is to quickly test the viability of this approach. To that end, write a scheme function called change that takes two inputs: A list of coins in the currency system (always from smallest to largest and always including the coin type 1) followed by the amount of change to be made. The function simply returns the least number of coins required (but not the actual set of coins to disburse).

Here is some sample input and output:

scheme> (change '(1 5 10 25 50) 42)
5
scheme> (change '(1 5 21 35) 42)
2

You should not use pset (powerset) for this function. Instead you should implement it "from scratch". Note that unlike the last time you saw this problem, this time you can use each coin more than once. This makes it difficult to directly use pset anyway, so this restriction should help you, not hurt you. Of course, you're welcome to refer to pset or your old change program when writing this program for ideas on how to structure your function.

Once you have written and tested your code, check to see if it performs fast enough. In particular, using the U.S. coin system from pennies up to ten dollar bills (e.g. '(1, 5, 10, 25, 50, 100, 500, 1000)) check to see how long it takes to make change for amounts in the range of a few dollars. Use your watch to time your program, but feel free to control-C out of your function if it runs for over a minute. (The hope is that the optimal change will be computed in under 5 seconds, because customers are likely to get frustrated otherwise). Write short memo (a few sentences should suffice) to Professor Lai indicating your analysis of the feasibility of the recursive approach.

Note: Recall that scheme has built-in value called +inf.0 that is larger than any integer.

Submit your memo in a file named memo1.txt. Submit your code in a file named change.scm.

Part 2: More Change (50 Points, Individual only)

Dr. Lai has been replaced by the brilliant Dr. Dee Nomination. Dr. D (as she's called) suggests that dynamic programming is likely to solve the problem. Your next task, therefore, is to re-implement the recursive algorithm that you developed in Part 1 using dynamic programming. Of course, you should use Java now rather than rex, since Java has arrays and these will be very useful to you!

Your program should be called Change.java. When run, it will ask the user for the name of a file with the currency system. That file will have the following format: The first line contains a single number: the number of coins and/or bills in the system. Each coin/bill in that system is on a subsequent line by itself, from 1 upwards. Example files for the U.S. and Shmorbodia are given in the files US.txt and Shmorbodia.txt on the main assignment page.

Here is some sample input and output, indicating what will happen when you run your program. (Note that you print the actual coins to be given in any order, not necessarily largest denomination first.)

% java Change
Enter the name of a currency file:  US.txt
How much change would you like?  42
5 coins
1 25
1 10
1 5
2 1
Would you like to run again? yes
How much change would you like? 99
8 coins
1 50
1 25
2 10
4 1
Would you like to run again? no
Bye!

Test your program on some fairly large amounts of change in at least two different currency systems. Use your watch to time your program to get a sense of the scale of problems that can be solved in under 5 seconds. You don't need to be exact here, but just get a rough sense of the how much change can be made in about 5 seconds. (If this is not a HUGELY dramatic improvement over your recursive solution from Part 1, check your code again!) Write a short second memo, memo2.txt to your boss indicating your findings. A few sentences should suffice.

Submit your memo as memo2.txt and your program as Change.java. If you have additional helper code in other files, submit those files too.

Part 3: The Floyd-Warshall Algorithm! [60 Points, Individual or Pair]

You've been hired away from Change to work for Giiigle, the wildly successful search engine and maker of the famous GiiigleSpam program. GiiigleSpam allows users to find the shortest path between any pair of points (vertices) in a map (graph) (especially in reverse!).

In particular, you've been asked to implement the main "smarts" of GiiigleSpam, a program that will take as input a map (graph), computes the shortest path between every pair of points (vertices) in that map, and then allows users to make shortest path queries.

You should implement the Floyd-Warshall Algorithm for finding the shortest path between every pair of vertices in a graph. Your program should be written in Java. Here are the requirements for your program:

Your program should be called FloydWarshall.java. The compiled program will be invoked by typing java FloydWarshall.
The program begins by asking the user for the name of a file that contains an adjacency matrix representation of a graph. In particular, the file will always be in the following format: The first line of the file will contain a positive integer, n, indicating the number of vertices in the graph. This is followed by n lines of data, each of which contains n entries. The entry in row s and position t in that row indicates the length of the edge from vertex s to vertex t in the graph. If there is no edge from vertex s to vertex t then the length of this edge is "infinity" which is represented by the letter I. Notice that the length of the edge from vertex s to t may be different from the length of the edge from vertex t to s.
On the main hw page you can find a compiled version of our program and several sample maps. Take a look at the map files. The maps are pretty special, so you should be able to infer what they are by just looking at them for a few minutes. Try runing our program on these files. Notice that the program reads the file, runs the Floyd-Warshall algorithm once to compute the shortest paths between all pairs of vertices, and then enters a loop where it permits the user to make queries to find a shortest path between any pair of vertices.
Your program should work like this sample program. In particular, it should print out the matrix of shortest path lengths that it found as a result of running the Floyd-Warshall algorithm. Then, it should enter a loop where it queries the user for a source/destination pair and prints out instructions to get between vertices in addition to giving their path lengths.
Here are a few tips:
- At first, implement the program just to compute the lengths of the shortest paths between all vertices, not worrying about reconstructing (printing) the actual paths. Once you've got the program computing the matrix of shortest paths, you can go back and modify the program to print out the actual shortest paths. (More on reconstructing the shortest paths below.)
- Remember that all input (from the console or from a file) comes in as a string - you'll need to convert strings to integers in some cases.
- As you'll recall from our discussion of the Floyd-Warshall algorithm, vertices should be numbered from 1 upwards rather than from 0. Why? If there is a vertex numbered 0 then asking for a shortest path from vertex 5 to vertex 42 going through no vertex numbered higher than 0 allows that path to pass through the intermediate vertex 0. We don't really want that! We want the "0" case to be the simplest case that we can only use a single edge on the path.
- Finally, how will we reconstruct (print) the actual shortest paths when the user makes a query? Imagine that we have completely filled in our dynamic programming table. Consider cell (s, t, j) in your dynamic progrmamming table. This cell keeps the length of the shortest path from vertex s to vertex t such that the path does not pass through a vertex numbered higher than j. Imagine that you also stored - in that cell - some intermediate vertex on that shortest path. (You found that intermediate vertex while filling in the table!) That intermediate vertex might be j or it might be some other vertex (in particular, if vertex j is not used on that shortest path). Let's assume that intermediate vertex is k. Then we would know that we must print the shortest path from s to k followed by the shortest path from k to t. We can use recursion to obtain those two subpaths. "Recursion!?" we hear you cry, "That's always slow!" Not really! In this case, the recursion is not exploding exponentially, it's simply being used to quickly print out the path that is implicitly already stored away in the dynamic programming table. The total number of recursive calls for this process will be at most the number of vertices on the path, which is no more than n, and thus this recursion will be lightning fast! In other words, the recursion is not being used to compute the shortest path, it's just being used to print the shortest path that has already been computed in the table. Nice!

Please submit your solution in a file called FloydWarshall.java. If you have additional code in other files, please submit those too.