Assignment 8: BSTNode and Dynamic Programming    [100 Points]
Due Tuesday, April 8th by 11:59pm

But which problems can be solved quickly? That question is a famous open conjecture, known as the P vs. NP conjecture. At the moment, that question is beyond our understanding. But even though we can't fully characterize which problems are amenable to speedups and which ones simply must take a long time, here you'll implement a few of the speedupable ones as a entry point... .

Partners:  This week's problems may be done singly or with pair programming.

Problem 1: a Java binary search tree: BSTNode

30 points

At this point you've written code for Binary Search Trees (BSTs) in two different languages: Racket & Prolog. Here, you'll add our third language by writing a binary-search-tree data structure (class) in Java named BSTNode. For this problem, you should start with the starter BSTNode class and set of JUnit tests in BSTNodeTest.java:

• BSTNode.java
• BSTNodeTest.java

• hw8src.zip

BSTNode has much of its basic functionality already provided. This provides several examples of static vs nonstatic methods -- and lets this problem focus on the most algorithmically interesting facets of binary search trees!

This class is an "open" data structure (a bit unsual for Java) -- meaning that all methods will create new data or reuse old data. Either way, no existing BSTNode objects will be modified or altered. Because no data are ever altered -- new data are created when needed -- structures can be shared without worrying that changes to one will change another. After all, there are no changes!

This is the spirit of data structured in Racket and Prolog - one of the points here is to show that Java can support such constructively-handled structures as well as the more traditional, destructively-handled approach that we used in the List class. Both Racket and Prolog use such constructively-handled data structures.

Methods to write

For this problem you should add these methods to the BSTNode class:

• static BSTNode left(BSTNode N) - a static version of the existing left method
• BSTNode right() - a nonstatic version of the existing right method
• static String min(BSTNode N) - a static version of the existing min method
• Object find(String input_key) - a nonstatic version of the existing find method
• static BSTNode remove_min(BSTNode N) - a static version of the existing remove_min method



• BSTNode insert(String new_key, Object new_value)
  a nonstatic version of inserting into a BST
• static BSTNode insert(String new_key, Object new_value, BSTNode old_tree)
  a static version of insert
• BSTNode delete(String key_to_go)
  a nonstatic version of deleting from a BST
• static BSTNode delete(String key_to_go, BSTNode N)
  a static version of delete

You are welcome to delegate the work of the static methods to existing nonstatic ones, and vice-versa. For insert and delete, however, you'll need to implement at least one of the two! As a guide, here are our earlier 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)

Problem 2: Change, Inc.

40 points
(Racket ~ 10; Java ~ 30)

• Here is the Change.java starter file...
• Here is the ChangeTest.java starter file...
• Here is an implementation of Knapsack.java solving the Knapsack rpoblem from class...

You have been hired by Change, Inc., a pioneer in the business of making change. The firm's motto, "Making positive change throughout the world!" isn't quite true because, strictly speaking, the change is only non-negative and not always strictly positive. The PR folks at Change, Inc. aren't worried about this nuance, however.

Your job is to write software 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 Change, Inc. 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 it 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 amount!

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.

Your first task, then, is to test the viability of a purely recursive approach. To that end, Dr. Lai has requested a Racket function that find the shortest-length list of "coins" that sum to a provided target value.

Racket: min-change and make-ones

In a file named change.rkt file, you should write a function named min-change( target, coin-type-list ) that takes two inputs: first, a target value for which to make change and second, coin-type-list, a list of coins/bill denominations in the currency system listed from smallest to largest. The function should return the shortest-length list of denominations (coins) required to make change for the target value. If there are multiple shortest-length lists, any one of them is OK. You should, however, return the list in ascending-sorted order - feel free to use sort to do this... .

Because this is using recursion, you can assume that no target amount 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.

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:

• In our solution, 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.


• In case you need it, 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., (inexact->exact 42.0) returns 42.

Submit your code in a file named change.rkt.

Java: the Change class and a dynamic programming solution

After the run-time results emerge from Racket's purely recursive change-computer, Dr. Lai is "reallocated" to a different project - and is 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.

Your file should be called Change.java and your class should be named Change. The Change class should have at least these data members and methods:

• private int[] coinTypeList
  
  This data member should hold the array of available coin denominations, which will be input to the constructor. The first element of the array will be 1 (your code does not have to explicitly check for this).



• public Change(int[] coinTypeList_input)
  
  This constructor should set the data member coinTypeList to coinTypeList_input.



• public int minCoins(int amt)
  
  This method should return the integer which is the smallest number of coins required (in the coin-denomination system of this.coinTypeList) to make change for the target amount, amt.



• public int[] makeChange(int amt)
  
  This method should return an int[] cointaining a short-as-possible array of coin values that add up to amt. The returned array should be sorted in ascending order. Note that you can use Arrays.sort( A ) in order to sort an array A, though you'll need to import java.util.Arrays at the top of the file. If there are multiple shortest ways to create amt, any one of those is OK. We will test your code only on unambiguous cases.
  
  

Though you're welcome to build it from scratch, if you'd like, a starter file for the Change class is provided. Either way, do use the JUnit tests in ChangeTest.java:

• Change.java
• ChangeTest.java

• You will want at least one helper function - to actually run the dynamic-programming algorithm for determining the minimum number of coins for each value up to and including amt. Note that this will require an array of length amt+1 (you need that +1!) I found it useful in the same helper function to also create an array that holds the "last coin used" or "previous coin unsed" when making the minimum-length change for each amount from 0 to amt, inclusive.


• How should those arrays be returned?   Keep in mind that in Java you don't have to return them! Instead, you may create a new data member (also called an instance variable) to hold the results of computing those two arrays described above and in class on Th. For instance, I called them

    private int[] minCoinsTable;
    private int[] prevCoinTable;
  

  and started them both at null. The helper function then created these two integer arrays, filled them out, and assigned them to this.minCoinsTable and this.prevCoinTable, respectively. But these specifics are up to you -- feel free to use this approach or another one.
• Should those two arrays be computed with each call? It is totally OK to recompute those two arrays with each call to makeChange and/or minCoins. It's also possible to "remember" (in another instance variable) the last amount computed and only call the helper computation if the new amount is larger - but this is totally optional. DP is fast enough that it'll be OK to continually recompute!
• This is a short function to help with printing arrays easily:

  /**
   * printArray, a helper for printing 1d int arrays
   * @param A, the 1d int array to be printed
   */
   public static void printArray( int[] A ) {
        // we use the helper function Arrays.toString:
        System.out.println( Arrays.toString( A ) );
   }
  

• Be sure to test with the JUnit tests, as well! (It's not required to write extra tests this week... .)

Submit your program in Change.java

Part 3: The Floyd-Warshall all-pairs shortest-paths algorithm

Here are the starter files:

• FW.java
• FWTest.java
• FW_EC_Test.java FW tests if you try the extra-credit...

You've been hired away from Change, Inc. to work for Google for the new stealth-mode version of their mapping service, named GoogleSpam. GoogleSpam intends to turn users' mapS experience completely on its head! Specifically, GoogleSpam has collected all of the spam-locations on the planet and will allow its users to estimate the shortest distance among any pair of possible spam-locations (nodes) in their map (graph).

You've been asked to implement the main "smarts" of GoogleSpam, i.e., the Floyd-Warshall all-pairs-shortest-paths algorithm. It takes in a graph as an adjacency matrix, computes the shortest paths between every pair of vertices, and then allows queries - in the form of Java API calls (methods) - for the shortest distance between nodes. (Challenge: to also produce the shortest path between any two nodes - see the extra-credit... .)

The graphs In the FWTest.java file, you will see a number of different maps, named map0, map1, up to map4. Each contains an adjacency matrix that indicates the edge weights from each node to each node. 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. Be careful, however, Java does not actually compute with -1 as if it were infinity -- you'll need to write conditionals that do the correct thing!

You should create a class named FW (or use the one from the starter file) for your Floyd-Warshall implementation. It should have at least these data members and methods:

• private int[][] graph;, where graph[src][dst] will be the distance from src to dst



• public FW(int[][] graph_input)
  
  This is the constructor which should set this.graph to graph_input.



• public int minDistance(int src, int dst)
  
  This is the accessor method - it should return the minimum distance from src to dst in the graph this.graph using FW. This means you'll want to have computed the full FW table beforehand... .



• Extra    public int[] path(int src, int dst)
  
  This optional, extra-credit method should return an int[] whose first element is src, whose final element is dst, and whose intermediate elements trace the shortest-distance-path from src to dst. Note that shortest-distance does not necessarily mean the shortest number of hops, since the roads are different lengths! See the bottom of this page for a bit more on the extra-credit... .

In the same spirit as the change problem, you will want a helper function that actually runs the Floyd-Warshall algorithm and builds up the table of shortest-distances!

Overview of the FW algorithm...
We hinted at the FW algorithm in class, but more explanation is certainly warranted! Here are the key points to consider:

• You will probably want a helper function that (1) creates a three-dimensional array of ints to hold the FW dynamic programming table and (2) fills in that table with the appropriate shortest-distance values.



• In order to make a 3d array, you can use a line of code such as this:

  int[][][] fwtable = new int[numlayers][numsrcnodes][numdstnodes];
  

  where numlayers is the number of 2d "layers" or "slices", numsrcnodes is the number of source nodes, and numdstnodes is the number of destination nodes. The value of numlayers is 1+numsrcnodes (the same as 1+numdstnodes). It will always be the case that numsrcnodes == numdstnodes. They're distinct simply to emphasize that you access an element in the 3d array via

  fwtable[ layer ][ src ][ dst ]   // min distance from src to dst using intermediate nodes from 0 to (layer-1)
  



• In the line of code above, the comment is very important, so we'll emphasize it here... . The fwtable consists of a set of 2d layers:
  • fwtable[0][src][dst], the zeroth layer, should be a copy of the original graph!
  • fwtable[1][src][dst], the one-th layer, should hold the minimum distances from each src to dst using the intermediate node number 0.
  • fwtable[2][src][dst], the two-th layer, should hold the minimum distances from each src to dst using the intermediate node number 1 (plus 0 from before...).
  • fwtable[3][src][dst], the three-th layer, should hold the minimum distances from each src to dst using the intermediate node number 2 (plus 0 and 1 from before...).
  • Each layer can be computed simply by "reaching back" into the previous layer -- no further!
  • The final layer, fwtable[N-1][src][dst] (where N is the number of layers, which is the same as one plus the number of nodes) will hold all of the minimum distances from any src node to any dst node! Pretty amazing!


• The last thing to consider is how to fill in each cell in each layer...? Well, layer 0 is just the original graph. Then, for k > 0, the minimum distance at layer k from src to dst, which is fwtable[k][src][dst], is either
  • [loseit for node k-1]    the same as the minimum distance on the layer below, k-1 from the same src to dst, or
  • [useit for node k-1]    the sum of (mindist from src to k-1 in layer k-1) plus (mindist from k-1 to dst in layer k-1).
  ... whichever of those two values is smaller!



• That's the whole algorithm!

Submit your FW.java file in the usual way... .

Part 4: Collision Detection

10 points

For this part you should create from scratch files named:

• Rectangle.java
• RectangleTest.java

Rectangle objects should be able to report their area, perimeter, and whether or not they overlap with another Rectangle object. Rectangle objects can be created by providing a Rectangle constructor a height and width or by providing a Rectangle constructor a height, width, and x and y coordinates of the bottom left corner of the rectangle. If I don't provide the x and y coordinates, the Rectangle's bottom left corner should be at (0, 0). You can assume that the top and bottom edges of the rectangles are parallel to the x-axis.

You must right tests for each of your methods using test driven development:

1. Write a "stub" of your method in Rectangle.java (write the method name, input, output and make it compile)
2. Write tests for this method in RectangleTest.java using JUnit (these tests should fail)
3. Write code in Rectangle.java so that all of your tests pass
4. If you realized while writing Rectangle.java that you didn't test all parts, add tests to RectangleTest.java

Beyond the requirements above, you should make all design decisions. Your assignment will be evaluated based upon the adequacy of your tests, your use of Java conventions (variable names starting with lowercase letters), your use of good variable names, and clarity of code.



Extra credit possibilities

Floyd-Warshall paths

This assignment's totally optional - and challenging! - extra credit is worth up to +10 points. For this, you should extend your FW class so that it can produce the shortest paths themselves, not only the lengths of the shortest paths, as described above.

Here is a JUnit test file for the extra-credit:

• FW_EC_Test.java

This requires implementing one more method:

public int[] path(int src, int dst)

To make this work, however, you'll need to keep track of the "parent node" or "previous node" for each of the (src,dst) pairs whose shortest path-distances you've computed. To do this, you'll want to create a 2d array and, each time an intermediate vertex does get used from src to dst, record that intermediate vertex's value in the 2d array, indexed at the src row and the dst column. By the end of the algorithm, that array contains all of the information you need to extract all of the shortest paths... !

The challenge - beyond computing the table - is determining how to extract paths from it. As a hint, remember that the table contains an intermediate node somewhere on the path from src to dst - that reduces finding the rest of the full path to two smaller problems - both of which can be solved using the same table!

Good luck!