Harvey Mudd College
Computer Science 60
Assignment 6, Due Thursday, October 24, 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 two files for this week's problems:

• Problem 1: Complex.java, an implementation of a complex-number class
• Problem 2: List.java, your implementation of a linked list.

Here are the starter files:

• Point.java, our Point class example
• Complex.java, a starting point for the Complex number 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. You should not modify any of the provided test cases.

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 methods 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)