Harvey Mudd College
Computer Science 60
Assignment 6, Due Monday, March 11, by 11:59pm

From Racket to Java...

You've already written quite a bit of Java code, but we'll dive into some of the real functionality of Java this week. This week you'll use or build several Java classes, i.e., custom data structures.

Submitting your code

Problems 1 should be completed individually; the other problems may be completed individually or in pairs. If you do work in a pair, please be sure both partners submit the file to their own submissions account; each should include a hash, e.g., #partnerlogin in the pair-programming textbox -- this will help the graders give the same grade to both.

Overall, you will submit 4 files for this week's three problems:

• Problem 1: Complex.java, an implementation of a complex-number class
• Problem 2: List.java, your implementation of a linked list.
• Problem 3: BST.java, an implementation of a binary search tree in Java, to which you'll add the ability to insert and delete.

Here are the starter files:

• Point.java, our Point class example
• Complex.java, a starting point for the Complex number class
• BSTNode.java, most of the BSTNode class
• List.java, the List starter code
• ListTest.java, JUnit test cases for List.java

Problem 1: Complex

This problem should be completed individually.

20 points

Java has eight built-in (primitive) types -- the most common are such as int, char, boolean, and double. It has thousands of class types in its libraries.

Yet one class type that Java does not have is Complex, representing the complex numbers commonly used by mathematicians, scientists, engineers, physicists, and Math 35 students. This problem asks you to implement a complex-number data structure (class), Complex.java. You should start with the provided files:

Complex.java     and     ComplexTest.java

The Point class example we developed in class will be a good reference. After all, 2d points and Complex numbers are not so different! The complete Point class is available here in Point.java.

Testing your code!    We have provided a small number of tests in ComplexTest.java. We recommend that you add additional test cases, but you will not be graded on these test cases in this assignment. Your ComplexTest.java file won't compile (it will have errors) until you add the public methods described below to your file Complex.java.

Complex number notes     Recall that a complex number is of the form a + bi where a and b are real numbers and i is an imaginary number. Addition of two complex numbers is defined by (a + bi) + (c + di) = (a+c) + (b+d)i. Similarly, to multiply two complex numbers, we simply compute (a + bi) * (c + di) = ac + adi + bci + bdii = (ac - bd) + (ad + bc) i since ii (i times i) is -1 by definition.

In your implementation, the numbers a and b in the complex number a + bi should be represented by doubles: these will be the two data members of your class. Please use the names real and imag (as already appear in the starter file) for these data members -- this will be far more readable/memorable than a and b!

Below are the public methods (functions) which your Complex class should contain. Be sure to use exactly these names and the specified kinds of arguments and return values. You may use any additional private methods of your own design, though such helper functions are not required.

• The class should have a constructor that takes two double arguments and sets the real and imaginary components of the complex number to these values. Here is the method signature (feel free to copy and paste):

      public Complex( double real_in, double imag_in )
      

• The class should have a second constructor that takes no arguments and simply sets the real and imaginary components of the complex number to both be 0.0. Here is the method signature:

      public Complex( )
      

• Please use this code as-is...
  
  The class should have a toString() method that converts complex numbers into strings for the sake of printing. We have provided this method (below and in the starter code) -- please use that, so that the style for complex-number printing is consistent! Here is the code again, for reference:

      // method: toString
      //     in: no inputs
      //    out: the String version of this Complex object
  
      public String toString()
      {
        String sign = "+";  // default sign is plus
        if (this.imag < 0.0) {
          sign = "-";       // if imag is negative, make it a minus
        }
        return "" + this.real + " " + sign + " " + Math.abs( this.imag ) + "i";
      }
      

• The class already has a method named equals -- please use that one! The reason we provide it is that we can then use tests that rely on it to compare Complex objects and any other Objects in Java! You'll see that it uses the instanceof operator to do this:

      // method: equals
      //     in: any object o
      //    out: true if o is Complex and its contents
      //         match this's contents
      public boolean equals(Object o)
      {
        if (o instanceof Complex)
        {
          Complex c = (Complex)o; // cast o to a Complex
          // now we can access c's imaginary and real parts...
          return c.imag == this.imag && c.real == this.real;
        }
        else
        {
          return false;
        }
      }
      

• The class should have a method named add that takes a Complex argument and returns the sum of this Complex number and the argument. Thus, the return value is a Complex number itself. You should be sure that neither of the summands have their values changed in any way. Here is the method signature:

      public Complex add( Complex c )
      

• The class should have a method called negate that takes no arguments and returns the negative of this Complex number. Thus, the return value is a Complex number itself, but the invoking object has not been changed. Here is the method signature:

      public Complex negate( )
      

• The class should have a method called conjugate that takes no arguments and returns the conjugate of this Complex number. The conjugate of the number a + bi is a - bi. Thus, the return value is a Complex number itself, but the invoking object has not been changed. Notice that this is slightly different than negation. Here is the method signature:

      public Complex conjugate( )
      

• The class should have a method called multiply that takes a Complex argument and returns the product of this    Complex number and the argument. Thus the return value is a Complex number itself and neither of the multiplicands have their values changed in any way. Here is the method signature:

      public Complex multiply( Complex c )
      

• The class should have a method called divide that takes a Complex argument and returns the quotient of this Complex number and the argument. You may assume that the second input is non-zero. Thus, the return value is a Complex number itself and neither of the multiplicands have their values changed in any way.

  To divide one complex number by another, first multiply both the numerator and denominator by the conjugate of the denominator. That ensures that the denominator is a real value! Then, you can simply divide both the real and imaginary components of the numerator by that value.

  Here is the method signature:

      public Complex divide( Complex c )
      

Problem 2: List

This problem may be done individually or in a pair. If you work in a pair, be sure to follow the CS department's pair programming practices throughout.

60 points

You will be writing the following methods, which are described in the start file List.java and can be tested using ListTest.java.

• add (6 points)
• reverse (6 points)
• makeFromArray (6 points)
• makeEquivalentArray (6 points)
• appendInPlace (6 points)
• split (6 points)
• removeFirst (6 points)
• merge (10 points)
• mergeSort (8 points)

Problem 3: BSTNode

Pair or individual

20 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.java and BSTNodeTest.java

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) 
  

  which should return a new tree identical to this tree, but such that the new_key (with new_value) are inserted in the new, returned tree in the appropriate spot. In particular, use the Racket implementation below as a guide:
  • 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)
    

  which should return a new tree identical to this invoking tree, except that the node whose key is key_to_go should be deleted, along with its value. Similar to the way you did this in Racket, your delete method should
  • 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)