CS 60, Assignment 13

Computer Science 60
Principles of Computer Science
Spring 2011

Assignment 13: The "Ultimate" Assignment: Algorithms!

Due Sunday, May 1 at 11:59 PM

First, a Few Notes on the Point "Buy Back" Plan for Midterm 2

As discussed in class, you have the option of re-doing any or all of the problems on the second midterm and submitting them for up to 1/4 of the points you missed. In other words, we will grade your revised solutions, determine the difference between your new score and your old score, multiply that difference by 0.25 and add that many points to your exam grade. Here are a few details:

You are welcome to talk to any of the grutors or professors about the exam, but please do not discuss it with other students in the class.
Coding problems should be submitted as functional code.
All problems should be submitted via the submission system, under HW15. You should use the following names:

Problem 1: m2pr1.pl
Problem 2: Employee.java
Problem 3: m2pr3.rkt
Problem 4: m2pr4.txt

The deadline for submission is SUNDAY, MAY 1, 11:59PM

Now, 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 starter code for these problems, 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, and the example code from this week.

While looking on the web for Java syntax is encouraged, 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. [20 Points, may be done in a pair or individually]

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 Change, Inc. that will make change in any given currency system using the smallest number of coins/bills. This software will be embedded in cash registers and used to inform tellers how to make change optimally - or will simply automate the dispensing of change via robotic change-makers.

As a simplifying assumption, 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 may also assume that the coins in the currency system are always given to use from lowest to highest value. In addition, you may assume that you have "unlimited" quantities of each coin/bill, so that you may use any combination - including repeats - in making change for a given quantity.

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 (for now). Your first task, therefore, is to quickly test the viability of a purely recursive approach. To that end, write a Racket function called change that takes two inputs: A list of coins in the currency system (always from smallest to largest and always with its smallest coin being a "penny" with value 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).

Approach: Here, you should employ the use-it-or-lose-it technique. That is, handle the base cases first. Then, consider the results of using (recursively) each of the possible coins in the list... you'll want the minimum of all of these!

Here are two sample inputs and outputs - note that the result depends on the "currency system" being used:

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

Once you have written and tested your code, check to see if it performs fast enough to handle large quantities. 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)), you might try larger and larger values to determine how long it takes to make change for different amounts in the range of a few dollars. Use your watch to time your program, but feel free to control-C (or hit the "stop sign") to cancel your function if it runs for over a minute. (The hope is that the optimal change will be computed in under a second, because customers are likely to get frustrated otherwise).

Note: Recall that Racket has built-in value called +inf.0 that is larger than any integer. In addition, in order to convert from floating-point (inexact) values to integer (exact) values, Racket has a built-in function inexact->exact, e.g.,

Racket> (inexact->exact 42.0)
42

Submit your code in a file named change.rkt.

Part 2: More Change (40 Points, pair or individual)

After the run-time results from the all-recursive change-counter, 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. This time, you should use Java now rather than Racket: Java's arrays will be useful for this re-implementation.

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, which is the number of coins and/or bills in the system. The next lines will contain the values of Each coin/bill in that system, 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.

A place to start for file-handling?! Feel free to adapt the code below to handle the file: Scanner and nextInt are pretty much all you'll need here (and a for loop!) Alternatively, there is a starting-point for file-handling in the Floyd-Warshall problem: you could adapt that to this problem, too. Note that you'll need a file that starts with an integer (followed by a space) in the same directory as FileReadStarter.java in order to try this out! For example, US.txt is a reasonable one.

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

class FileReadStarter
{
  public static void main( String[] args )
  {
    // get keyboard input Object
    Scanner kbd = new Scanner(System.in);
    // get input from keyboard
    System.out.print( "Enter a filename: " );
    String filename = kbd.nextLine();
    // trim off any whitespace
    filename = filename.trim();
    System.out.println("Now trying to open " + filename);
    
    // get file input Object via the file:
    Scanner file = null;
    try { // in case the file's not there
      file = new Scanner(new File(filename));
    } catch (FileNotFoundException e) {
      System.out.println("File " + filename + " not found.");
      System.out.println( e );
    }
    // get integer at the start of the file:
    int value = file.nextInt();
    System.out.println("Read the value " + value);
  }
}

Here is some sample input and output, indicating what will happen when you run your program. Note that you may print the 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
Minimum: 5 coins
Coins: 25 10 5 1 1

% java change
How much change would you like? 99
Minimum: 8 coins
Coins: 50 25 10 10 1 1 1 1

Test your program on some fairly large amounts of change (up to about 1000) 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 1 second. You don't need to be exact here, but just get a rough sense of the how much change can be made in that span. (If this is not a HUGELY dramatic improvement over your recursive solution from Part 1, check your code again!)

Submit your program in change.java.

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

You've been hired away from Change, Inc. to work for Giiigle, the wildly successful search engine and maker of the famous GiiigleSpam program. GiiigleSpam allows users to estimate the shortest distance (perhaps measured as time or as length) between any pair of cities (nodes) in a map (graph).

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

Try it first... A set of .class files is provided in the fw.zip folder. To run them from (for example) Dr. Java, these steps have worked:

Open the ReadFWMap.java file (not really needed, but this puts Dr. Java "in the right directory")
Go to the "Interactions Pane" at the bottom of Dr. Java
at the prompt, type > java FloydWarshall
Then, the program should start. I've tried it with map0.txt -- be sure to keep in mind that the cities are indexed _starting from 1_ instead of the usual zero-indexing.

This is nice because it means you can use the 0 index for other purposes, such as the original graph's adjacency matrix. But be sure to make the arrays you use large enough!

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 should begin 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 integers. The integer in row s and (column) position t 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. Note, too, 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, due to traffic, magic, or other unusual road conditions.
Since different OSes use different combinations of characaters for new lines, we've pasted the contents of all three map files at the bottom of this page. If our provided files don't work on your system, feel free to copy-and-paste the text from below into a new file (using Dr. Java or another text editor).
As a starting point for file-handling, check out the source code ReadFWMap.java in the fw folder. In fact, you might alter a copy of that file into your own FloydWarshall.java file (and class).

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 such that you should be able to infer what they are by just looking at them for a few minutes. Try runing the provided 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.)
- As you'll recall from our discussion of the Floyd-Warshall algorithm, vertices should be numbered from 1 upwards rather than from 0. Here's 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 and print the actual shortest paths when the user makes a query? In order to do this, you might keep a second table that holds in cell (s,t) the immediately previous intermediate vertex traversed when going from s to t. This entry could start as s for all entries (s,t) for which there is a valid direct edge. Then, the entries of this table could be updated appropriately as the Floyd-Warshall algorithm progresses! Once the algorithm finishes and you need a path from s to t, you can use this table to get the vertex immediately before t on that path. Then, you can use the table again to get the vertex immediately before that one - and so on!

Please submit your solution in a file called FloydWarshall.java.

Extra credit: CS 60 end-of-semester survey (individual) [+10 points]

This anonymous survey provides the CS department with feedback on the curriculum and results of CS 60 that is quite different from the official course evaluation forms. In order to improve CS 60 (and the CS curriculum more generally), we would greatly appreciate it if you'd take this short online survey (likely less than 10 minutes). As an incentive, if you take the survey and submit a file named survey.txt that says I took the survey, it will be worth +10 points on this week's hwk.

Here is the link to the survey:

The CS 60 end-of-semester survey monkey survey

Thank you to everyone who helps provide this feedback!

Appendix - the map files to copy-and-paste

Since different OSes have different new-line characters, we'll paste all of the map files here, so that you can copy-and-paste them into new files on your system (in case the provided ones don't work...):

map0.txt

map1.txt

30
0 1 I I I I I I I I I I I I I I I I I I I I I I I I I I I I
I 0 1 I I I I I I I I I I I I I I I I I I I I I I I I I I I
I I 0 1 I I I I I I I I I I I I I I I I I I I I I I I I I I
I I I 0 1 I I I I I I I I I I I I I I I I I I I I I I I I I
I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I I I I
I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I I I 
I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I I 
I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I 
I I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I 
I I I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I 
I I I I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I 
I I I I I I I I I I I 0 1 I I I I I I I I I I I I I I I I I 
I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I I I I 
I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I I I 
I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I I 
I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I 
I I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I 
I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I 
I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I 
I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I I 
I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I 
I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I 
I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I 
I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I 
I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I 
I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I 
I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I 
I I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I
I I I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1
1 I I I I I I I I I I I I I I I I I I I I I I I I I I I I 0

map2.txt

30
0 12 I 16 I I I I I I I 100 I 119 I I I I I I 42 I I I I I 51 I I I
I 0 1 I I I I I I I 99 I 201 I I I I I I I 41 I I I I I I 16 I 119
51 I 0 1 I 9 I I 25 I I 76 I I I 45 I I 38 31 I I I I I I I I I I
I I 26 0 1 I 26 I I I 29 I I 30 I 87 I I I I I I I 41 I I I I I I
I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I I I I
30 I 17 I I 0 1 I I 42 I I 42 I I 41 I I I I I I I I I I I I I I 
I 31 I 33 I I 0 1 I I I I I I 41 I I I I I I I I I I I I I I I 
I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I I 
I I I I I I I I 0 1 I I I I I I I I I I I I I I I I I I I I 
I I I I I 28 I I I 0 1 I I I I I I I I I 26 I I I I I I I I I 
I I I I I I I I I I 0 1 I I I I 17 I I I I I I I I I I I I I 
I I I I I I I I 36 I I 0 1 I I I I I I I I I I I I I I I I I 
I I I I I 39 I I I I I I 0 1 I I I I I 79 I I I I I I I I I I 
I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I I I 
I I I I I I I 54 I I I I I I 0 1 I I I I I I I I I I I I I I 
I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I I I 
I I I 23 I I I I I 34 I I I I I I 0 1 I I I I 52 I I I I I I I 
I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I I I I 
I I I I I 19 I I I I I I I I I I I I 0 1 I I I I I I I I I I 
I I I I I I I 17 I I I I I I I I I I I 0 1 I I I I I I I I I 
I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I I 
I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I I 
I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I I 
I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I I 
I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I I 
I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I I 
I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I I 
I I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1 I
I I I I I I I I I I I I I I I I I I I I I I I I I I I I 0 1
1 I I I I I I I I I I I I I I I I I I I I I I I I I I I I 0

Computer Science 60 Principles of Computer Science Spring 2011