Computer Science 60
Principles of Computer Science
Assignment 8: DP and BSTNode [100 Points]
Due Tuesday November 5th at 11:59pm
This week's homework is a combination of several ideas we've
been examining in CS 60. This assignment includes some
programming review (in Prolog and Racket) that
includes both the use-it-or-lose-it technique and dynamic
programming, an approach that speeds up such implementations
-- sometimes remarkably so!
Partners:
This week's problems may be done singly or with pair programming.
Problem 1: Change, Inc.
30 points
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.
The currency system might have very odd denominations - for example,
Gringotts, a potential customer, uses currency whose values are
1, 29, and 493 knuts, respectively - so the software should not
impose limits on what denominations it can handle.
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.
You may assume that you have "unlimited" quantities of
each coin/bill, and that you may use any combination - including repeats -
in making change for a given quantity.
Also, you may assume that 1 is always present in the list of denominations -- this
ensures that it's always possible to make change for any (nonnegative) target!
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 - at least for the moment.
Thus, first
task, therefore, is to test the viability of a purely recursive approach.
To that end,
Dr. Lai has requested both a Prolog predicate and a Racket function that
find the shortest-length list of "coins" that sum to a provided target value.
In the end, you'll create three implementations, one in each of Racket, Prolog, and Java.
The first two will use recursion (and will remind you about those languages, we hope!)
The Java implementation will use dynamic programming -- and run much more efficiently!
-
Racket:
In the change.rkt file, you
should write a function named min-change
that takes two inputs: first, a target value for which to make change and, second,
a list of coins/bill denominations in the currency system
listed from smallest to largest.
The function should return the shortest-length list of coins (really denominations)
required to make change for the target value. If there
are more than one shortest-length lists, any one of them is OK.
Because this is using recursion, you can assume that no target will ever be greater than
42 -- the nice thing about this is that you can return a list of 42 1s
in order to indicate a "bad" result (one that's no worse than any valid result).
This will help for some of the base cases.
Approach: Here, you should employ the use-it-or-lose-it technique!
Here are two sample inputs and outputs - note that the result depends on the "currency system" being used. Also,
the order in which the coins are listed in the end result does not matter -- any reordering would be OK here:
Racket> (min-change 42 '(1 5 10 25 50))
(1 1 5 10 25)
Racket> (min-change 42 '(1 5 21 35))
(21 21)
Racket> (min-change 1 '(1 5 21 35))
(1)
Racket> (min-change 0 '(1 5 21 35))
()
Hints and Reminders:
- In our solutions, we found it useful to create a helper function named (make-ones
n) that returned a list of n 1s. Here's how it would
run:
(make-ones 7)
(1 1 1 1 1 1 1)
-
The reason make-ones is useful is that (make-ones 42)
can be the return value from any "invalid" min-change call, e.g., when the
target is negative or there are no denominations at all! This works because
we're limiting the target value to 42 or less.
Submit this code in the file named change.rkt
-
Prolog:
Worried that only one implementation will constrain his business, Dr. Lai
wants to keep as many options open as possible -- in particular, he is pro-Prolog, and would like
a Prolog predicate
min_change( Target, Denoms, ResultingChange
)
that will bind a
minimum-length result to the variable ResultingChange, given bindings to Target (a
nonnegative integer) and Denoms, a list of the available denominations.
Write a version of this min_change predicate in the file
change.pl. Recall that
you will want to decompose this problem into arbitrary change-making and then will
need some additional checks to ensure a result is one of minimum-length.
Hints/reminders:
- the input Target will be zero or positive - you will want to
check this constraint each time, to stop Prolog from recursing with
negative values of Target!
- Because constraints like Target > 0 will
ensure that Prolog never recurses with a negative value for Target,
you won't need to have an artificially large list to bind for base cases, as had to be used in the
Racket version.
- a good place to start is to make a change predicate that computes
all possible lists of values, taken from Denoms, that sum to Target.
This simpler predicate would not impose that the result be the shortest such list.
Since "creating all possibilities" is what Prolog does best, this is a reasonable first step.
- once your change predicate works, then you could add other predicates
that will help ensure that min_change only finds a shortest change list.
This is similar to the Prolog quiz's longestPath question.
- remember that is is used for arithmetic, not =
- five rules are all you'll need total:
- three rules for the basic change-making (with no "shortest" constraint)
- two rules to enforce the "shortest" constraint on top of that
Run small tests!
Prolog is even less efficient than Racket, so don't try to run tests that are too large.
Here are some of the tests that ran in enough time for us - though the one with
a target of 18 took about 5-10 seconds. It's also OK to have multiple answers of the
same (minimum) length - even multiple identical answers, as Prolog likes to do:
?- min_change( 6, [1,5], MC ).
MC = [1, 5] ;
false.
?- min_change( 8, [1,5], MC ).
MC = [1, 1, 1, 5] ;
false.
?- min_change( 8, [1,3,5], MC ).
MC = [3, 5] ;
false.
?- min_change( 18, [1,5,9,10,12], MC ).
MC = [9, 9] ;
false.
?- min_change( 0, [1,5,42], MC ).
MC = [] ;
false.
Submit this code within change.pl
-
Java:
After the run-time results emerge from these all-recursive min-change-counters,
Dr. Lai is fired and replaced by the brilliant Dr. Dee Nomination. Dr. D,
as she's called, suggests that dynamic programming is likely to solve
the problem much more efficiently. Your next task, therefore, is to re-implement the
recursive algorithm that you developed in the previous parts using dynamic
programming. This time, you should use Java rather than Racket:
Java's arrays or ArrayLists - your choice - will be useful for this re-implementation.
Your program should be called Change.java. When run, it should
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 line will contain the values of each coin/bill in that system,
from 1 upwards. 1 will always be included (this ensures that
there is always an answer). Here is an example of currency amounts (admittedly
fictional, but computationally interesting) -- these are in the plain-text file ch1.txt:
6
1 5 9 10 12 20
Your program should print out a minimum-length list of denominations that
sum up to the target value. The design of the internals of the program
are up to you, with the knapsack example
to help provide pieces and/or ideas.
For this assignment you'll need to be able to read in data from a file.
When you run the provided code in Change.java you'll get this error:
To fix this error, follow the following steps:
- Copy and past the file coins1.txt into your Eclipse project.
- Click Run -> Run Configurations (Click on the "Arguments" tab)
- Set the working directory by clicking "Other" (shown as step #1)
and then selecting the folder in which you have put coins1.txt.
- When you've done this you should see the new working directory selected
Here is an example of
some possible output for the coins1.txt input file.
We include the debugging printout of our DP table and "last coin"
table for the first run, in case it's helpful. Note - that the green text is text
that the user types in (by click in the console and typing those characters).
Here are the same runs as they would appear if run at the command line.
> java Change
Enter a filename: coins1.txt
Now trying to open coins1.txt
Read the number of coins = 6
How much change would you like? 18
OK, searching for change for 18
Minimum # of coins = 2
The coins are 9 9
The DP table was
[0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 2, 1, 2, 2, 2, 3, 2, 2]
The "Last Coin" table was
[0, 1, 1, 1, 1, 5, 1, 1, 1, 9, 10, 1, 12, 1, 5, 5, 1, 5, 9]
> java Change
Enter a filename: coins1.txt
Now trying to open coins1.txt
Read the number of coins = 6
How much change would you like? 42
OK, searching for change for 42
Minimum # of coins = 3
The coins are 10 12 20
> java Change
Enter a filename: coins1.txt
Now trying to open coins1.txt
Read the number of coins = 6
How much change would you like? 99
OK, searching for change for 99
Minimum # of coins = 6
The coins are 9 10 20 20 20 20
Test your Java program on some fairly large amounts of change (up to about 1000)
in at least two different currency systems. This version should be a
HUGELY dramatic improvement -- in terms of how fast it computes --
over your recursive solutions in Racket and Prolog.
Submit this program in Change.java
Part 2: The Floyd-Warshall all-pairs shortest-paths algorithm
40 points
You've been hired away from Change, Inc. to work for Google and their
new stealth-mode version of their mapping service, named GoogleCpam, and
which they claim will "completely
reverse" the maps experience!
GoogleSpam allows users to
estimate the shortest distance among
any pair of possible spam-locaitons (nodes) in a map (graph).
In particular, you've been asked to implement the main "smarts" of
GoogleSpam, i.e., the Floyd-Warshall all-pairs-shortest-paths algorithm. It reads
in a graph from a file as an adjacency matrix, computes
the shortest paths between every pair of vertices, and then allows a user to make queries against those
results.
map files In the hw8.zip archive, there are a number of
different map files, named map0.txt, map1.txt, up to map4.txt.
Each contains an adjacency matrix that indicates the
edge weights from each node to each node. There are zeros in the top row and top column
of each file because all of the cities are indexed from 1, not from 0.
The extra zeros are padding so that you can read all of the data from the file directly
into your data structure and still start indexing the cities/vertices from 1.
Note that, within the map files, no edge from one vertex to another
is represented as -1. This is typically represented as some sort of "infinity"
value, and the starter code has a data member INF for that purpose. INF
is equal to Integer.Max_VALUE. Be careful, however, Java will allow to add or otherwise
use INF as an int, and will simply wrap. Thus, INF + INF yields -2!
(You'll need conditionals to make sure to avoid this.)
The cities are indexed from 1, not from 0!
Although 1-indexing is not the norm in computer science, it's very useful here, because
it means that the 0-index slice of the Floyd-Warshall table can be
the original adjacency matrix. Then the 1-index slice of the Floyd-Warshall table
can hold all of the shortest paths using the first vertex (with index 1) as possible
intermediate node. The 2-index slice of the FW table can then hold all of the shortest
paths using also the next vertex (with index 2) as a possible intermediate node, and so on...
Notice that this means that the nth slice of the FW table will hold all of the shortest-path lengths
when the algorithm is complete. Note, too, that you will have to make each dimension of size n+1,
where n is the number of cities, in order to support indexing from 1 to n!
Here is a brief overview/picture of the included map files:
- map0.txt contains the following data:
3
0 0 0 0
0 0 1 -1
0 -1 0 1
0 1 -1 0
- map1.txt contains the following data:
4
0 0 0 0 0
0 0 4 2 -1
0 -1 0 1 -1
0 -1 -1 0 8
0 16 -1 -1 0
- map2.txt contains the following data:
4
0 0 0 0 0
0 0 14 -1 -1
0 -1 0 14 50
0 -1 -1 0 14
0 10 -1 -1 0
- map3.txt contains the following data:
30
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1
0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
- map4.txt contains another 30-vertex graph:
30
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 12 -1 16 -1 -1 -1 -1 -1 -1 -1 100 -1 119 -1 -1 -1 -1 -1 -1 42 -1 -1 -1 -1 -1 51 -1 -1 -1
0 -1 0 1 -1 -1 -1 -1 -1 -1 -1 99 -1 201 -1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1 16 -1 119
0 51 -1 0 1 -1 9 -1 -1 25 -1 -1 76 -1 -1 -1 45 -1 -1 38 31 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 26 0 1 -1 26 -1 -1 -1 29 -1 -1 30 -1 87 -1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 30 -1 17 -1 -1 0 1 -1 -1 42 -1 -1 42 -1 -1 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 31 -1 33 -1 -1 0 1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 28 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 26 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 36 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 39 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 79 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 54 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 23 -1 -1 -1 -1 -1 34 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 52 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1
0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
starter file
The file fw.java contains a little bit of
starter code that reads in the first integer from a map file.
It also shows how to print a 3d array and has a bit of code to get
source and destination vertices from the user via keyboard.
Example results
Here is an example of the completed FW table and, underneath, a few example queries
for each of the five maps. In these examples, the paths are printed, but
that is the extra-credit portion of this problem -- we'd suggest
first getting the shortest-path-distances working, then (if you'd like)
returning to work on the paths.
Because some are large, these example results are linked on separate pages:
Warnings/Reminders
Since different OSes use different combinations of characaters to indicate newlines, the
above examples include all of the data of each map.
If our mapfiles are not working,
you can create your own by pasting the number of cities and then the adjacency matrix
into a new file using a text editor.
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. The algorithm builds a series of tables of
path lengths from every src to every dst.
The kth "slice" of the table thus represents "the shortest path-length from
all src vertices to all dst vertices going
through intermediate vertics numbered from 1 to k.
By starting at 1, the zeroth table then goes through no
intermediate vertices at all, which means it's simply the
original graph. By starting vertex-counting at 1, we avoid having
a special case for the original graph.
Watch out for infinities! INF can be added like any other integer, and it "wraps around"
the maximum value an integer can hold, causing surprising results such as INF + INF == -2 !
You'll need special cases to handle infinity appropriately.
Extra-credit
For up to +10 points of extra credit, you should also keep track of an array of "parent pointers" and
then print out the path from src to dst for each query the user makes.
These examples have been included in the sample runs above.
How you implement the "parent" table and other details is entirely up to you!
Submit your solution in the file
called fw.java
Part 3: BSTNodes...(30 points)
At this point you've written code for Binary
Search Trees (BSTs) in two different languages: Racket & Prolog.
Here, we provide a binary-search-tree data structure (class) in Java
named BSTNode. For this problem, you should start with
this almost-complete BSTNode class and BSTNodeTest class
BSTNode has much of its basic functionality already provided. This
provides both
an additional example of how Java creates data structures and it's
to allow you to focus on the most algorithmically interesting facets of
binary search trees!
However, in this class, we're doing something unsual for Java.
We have based the class BSTNode off of Racket trees. Recall that in Racket
we never changed any lists, we only made new lists. So in this BSTNode class
we will do the same thing - and NEVER change any BST!
In this problem you will add the methods insert and delete
for the class BSTNode.
-
To that end, first fill in the body of the provided method whose signature is
public BSTNode insert(String new_key, Object new_value)
- if this is the empty tree, i.e., emptyNode, then you will
want insert to return a new object of type BSTNode with only
the new_key and new_value pair.
- if the new_key is already in this, then insert
should return the original tree (this) or a copy of the original tree.
- otherwise, a new tree should be returned, with new_key and new_value
appropriately placed amidst all of the original data in the old tree.
-
Then, create the body of the provided method whose signature is
public BSTNode delete(String key_to_go)
- not do anything if this is the empty tree, emptyNode
- remove key_to_go and its value from the appropriate subtree, in the case that
key_to_go does not match the root of this
- return the empty tree if key_to_go is the root of this and
it's the only node in the BST
- if this has only one non-empty
subtree and has key_to_go at its root, then delete should return
that non-empty subtree
- finally, if this has key_to_go as its root key and it has two
non-empty subtrees, then it should promote the smallest key larger than key_to_go
(and its corresponding value) to the root from wherever it's found in the right
subtree.
- See the Racket implementation below as a less verbose guide to all of these cases!
The BSTNode class is designed to work in the same way as our Racket implementations
of binary search trees. Each object of type BSTNode can be considered
both a full BST and, at the same time, can be considered a single node within a (BST.
This is just like OpenList, where each object of type OpenList
is a single node within a Racket-like linked list. The other similarity is the design
decision that BSTNodes cannot be modified. Therefore, when you write the methods
insert and delete, you should not change the instance variables, i.e., the
data members, of any of the BSTNodes in the original tree structure.
For reference, here is a Racket implementation of insert and delete:
#lang racket
(define BT1 '( 42
(20 (7 (1 () ()) (8 () ()))
(31 () (41 () ())))
(100 (60 () ())
()) ) )
(define (make-bst key left right) (list key left right))
(define get-key first)
(define get-left second)
(define get-right third)
(define (leaf? BST) (and (null? (get-left BST)) (null? (get-right BST))))
(define (empty? BST) (null? BST))
;; here is a Racket implementation of insert:
(define (insert new_key oldBST)
(cond ((empty? oldBST)
(make-bst new_key '() '()))
((equal? (get-key oldBST) new_key)
oldBST)
((< (get-key oldBST) new_key)
(make-bst
(get-key oldBST)
(get-left oldBST)
(insert new_key (get-right oldBST))))
(else
(make-bst
(get-key oldBST)
(insert new_key (get-left oldBST))
(get-right oldBST)))))
(define start (make-bst 42 '() '()))
(define v2 (insert 100 (insert 20 start)))
(define v3 (insert 7 (insert 31 (insert 60 v2))))
(define v4 (insert 1 (insert 8 (insert 41 v3))))
;; a test for several inserts...
(equal? BT1 v4)
;; here is a Racket implementation of find-min.
;; This function presumes that BST is NOT EMPTY!
(define (find-min BST)
(if (null? (get-left BST))
(get-key BST) ;; return the root if the L is empty
(find-min (get-left BST)))) ;; else descend on the left...
;; here is a Racket implementation of delete:
(define (delete key_to_go oldBST)
(if (null? oldBST)
'() ;; return the empty tree
(let* (
(root (get-key oldBST))
(L (get-left oldBST))
(R (get-right oldBST))
)
(if (< key_to_go root)
(make-bst root (delete key_to_go L) R)
(if (> key_to_go root)
(make-bst root L (delete key_to_go R))
;; must be the case that key_to_go == root here!
(if (null? L)
R ;; whether or not R is empty, it's what we want
(if (null? R)
L ;; if R is empty, we want L
;; otherwise, we grab the min of the right and make it the root
(make-bst (find-min R) L (delete (find-min R) R)) )))))))
;; tests for delete...
(define BT1_no42 '( 60
(20 (7 (1 () ()) (8 () ()))
(31 () (41 () ())))
(100 ()
()) ) )
(define BT1_no100 '( 42
(20 (7 (1 () ()) (8 () ()))
(31 () (41 () ())))
(60 () ())))
(define BT1_no8 '( 42
(20 (7 (1 () ()) ())
(31 () (41 () ())))
(100 (60 () ())
()) ) )
(equal? (delete 42 BT1) BT1_no42)
(equal? (delete 100 BT1) BT1_no100)
(equal? (delete 8 BT1) BT1_no8)
Extra credit possibilities
Floyd-Warshall paths
This assignment's first totally optional - but challenging! - extra credit
is worth up to +10 points for an extension of the Floyd-Warshall algorithm
so that you can print the shortest paths themselves, not only the
lengths of the shortest paths in your implementation of that problem.
You can simply include those paths -- as the example outputs show --
with the rest of your FW implementation. If you do this extra credit, please
note this in the comments at the top of your fw.java file.