Harvey Mudd College
Computer Science 60
Assignment 3, Due Sunday, February 8, by 11:59 pm

Tyrannis Rex - and a short cup of Java

This homework applies some of Rex's functional programming principles to larger applications than previous assignments. In addition, it provides a first look at Java, where you will implement a Complex-number data structure. Next week we will implement and use Rex's fundamental data structure, the OpenList.

The Problems

Files for getting started

You'll probably want to develop your functions in a hw3 subdirectory within your cs60 directory. There will be three files to submit this week. They are

• part1.rex -- three individual problems to be completed in Rex, #1, #2, and #3.
• part2.rex -- two individual - or - pair-programming problems to be completed in Rex, #4 and #5
• Complex.java -- one individual - or - pair-programming problem to be completed in Java. This is problem #6, but should be submitted in a file named Complex.java. Be sure to grab the starter-file by that name as described below!

You can copy starter files for part1.rex, part2.rex, and Complex.java, as well as some helper files, from the directory /cs/cs60/hwfiles/a3/ A command-line tip: in many contexts from the command line the asterisk * means "everything." Thus, you could grab all three of those starter files, along with other helper files in the same location, with the command (see the caution below before running this, however!)

cp /cs/cs60/hwfiles/a3/* .

cp /cs/cs60/hwfiles/a3/part1.rex .
cp /cs/cs60/hwfiles/a3/part2.rex .
cp /cs/cs60/hwfiles/a3/miniDB.rex .
cp /cs/cs60/hwfiles/a3/unicalcDB.rex .
cp /cs/cs60/hwfiles/a3/Complex.java .
cp /cs/cs60/hwfiles/a3/Point.java .

Built-in functions (Rex)

You're welcome to use any of Rex's built-in functions for this week's assignment (with one minor exception, below). Also, you may copy functions from homeworks #1 or #2 or from class into this week's files to reuse them. Here is a list of some of the more common built-ins and some other useful ones:

list(e,f,...)   // makes a list from its inputs. [e,f,...] is often easier
cons(f,R)       // the same as [f|R]
append(L,M)     // concatenates two lists (inputs must be lists!)               
member(e,L)     // 0 if e is not in L; 1 if e is in L
reverse(L)      // reverses L
rmv1(e,L)       // not built-in; from class -- removes one e from L
removeAll(e,L)  // not built-in; from hw#1 -- removes all e's from L
length(L)       // returns the length of L         
max(x,y)        // returns the max of x and y -- does NOT take the max over a list
min(x,y)        // returns the min of x and y -- does NOT take the min over a list
sort(L)         // returns a sorted version of L
first(L)        // returns the first of L (similarly, second, third...)

map(f,L)        // applies f to each element of L. f takes one input.
reduce(f,e,L)   // "pushes" the binary operator f "through" L, starting at e
keep(p,L)       // retains those elements x in L that make p(x) true
drop(p,L)       // drops those elements x from L that make p(x) true
some(p,L)       // returns 1 iff there exists an x in L such that p(x) is true
all(p,L)        // returns 1 iff p(x) is true for all x in L

part1.rex    Individual problems, #1 through #3

As with the previous assignments, please submit definitions for these functions in a file named part1.rex. Each person should write these first five problems on their own. We encourage you to seek out help from us, from the grutors, or from other students as described in the syllabus.

Problem 1:    flatten

[10 points, individual]

test( flatten( [1,2,3] ),                             [1,2,3] );
test( flatten( [ 1,2,[3,4,[5],6,7,[[[8]]]], 9 ] ),    [1,2,3,4,5,6,7,8,9] );
test( flatten( [] ),                                  [] );

Although flatten is like a duper-smush, duperreverse might be a better starting point.

Problem 2:    makeChange

[10 points, individual]

Write a function makeChange( Coins, value ), which takes as input a list of positive integers (or coins) named Coins and an integer value. Then, makeChange should output a sorted list of the distinct, sorted combinations of "coins," taken from Coins that sum to value. Thus, the output will be a sorted list of sorted sublists. Each sublist should sum to value and should consist of a distinct collection of integers from Coins. Recall that Rex has built-in functions sort and remove_duplicates, which is like uniq. Here are some examples of makeChange (with a helper function that makes sure things are sorted and duplicates removed...):

// this makes sure things are sorted & without duplicates
srd( LoL ) = sort(remove_duplicates( map( sort, LoL ) ));
test( srd( makeChange( [5,10,10,10,25],  30 ) ), [[5, 25], [10, 10, 10]] );
test( srd( makeChange( [5,10,10,10,25],  35 ) ), [[5,10,10,10],[10, 25]] );
test( srd( makeChange( [5,5,10,10,10,25],  30 ) ), [[5,5,10,10], [5, 25], [10, 10, 10]] );
test( srd( makeChange( [5,5,10,10,10,25],  35 ) ), [[5,5,25], [5,10,10,10], [10, 25]] );

Warning: if your code is failing the tests, but seems to be doing everything correctly, check again that your output is sorted and without duplicates!

Problem 3:    Unicalc! (part 1)

[20 points, individual]

This problem asks you to write the first half of a Rex "unit-calculator" application. The second half is problem #4.

Looking ahead...

These next few lines provide context by describing the final unit calculator. Afterwards, there are a number of individual functions to write...

The complete Unicalc application will be able to convert any unit quantity to any compatible quantity by using a database (really, just an association list) of known conversions. Incompatible conversions will result in a set of extra units "left over."

For example, the following call is asking "how would you convert from 1 mph (mile per hour) to 1 meter per second?" The third input argument to convert, named db is a "database" of unit conversions. This "database" is simply an association list of the sort you used in hw#1's wordScore function.

rex > convert( [1.0, ["mile"], ["hour"]],  [1.0, ["meter"], ["second"]], db );
[0.447032, [], []]

Here is an example with some units left over, because it's not possible to convert miles-per-hour to feet:

rex > convert( [1.0, ["mile"], ["hour"]], [1.0, ["foot"], []], db );
[1.466666, [], ["second"]]

As these examples suggest, your convert function needs only to handle multiplicative conversions - it will not handle more complicated conversions, such as the one from Fahrenheit to Celsius.

... end of looking ahead

Now, on to the data structures and functions for this problem... .

Here are the key representations used in Unicalc:

• A Quantity list or "Quantity" is always a list of three elements representing some amount of a designated unit. Here are four example quantity lists:

         [1.0, ["mile"], ["hour"]]                 // represents 1 mile per hour
         [2.5, ["meter"], ["second", "second"]]    // represents 2.5 meters per second squared
         [60.0, [ ], ["second"]]                   // represents 60 hertz
         [3.14, [ ], [ ]]                          // represents about pi radians
         

  Thus, quantity list is a list of three elements: the first is the quantity itself (a floating point number), the second is a list of units in the numerator, and the third is the list of units in the denominator. Empty lists are required when no units are present.
  
  Note You may assume that the lists of units within the numerator and within the denominator, if any, are initially in alphabetical order. Your code needs to make sure this property is maintained!



• A Conversion Database is an association list of units' strings with Quantity lists that define them. Here is an example, with additional spaces added, taken from the helper file miniDB.rex:

  miniDB = [
             ["foot",    [12.0,       ["inch"],            []]         ],
             ["inch",    [2.54,       ["cm"],              []]         ],
             ["hertz",   [1.0,        [],                  ["second"]] ],
             ["mile",    [5280.0,     ["foot"],            []]         ],
             ["coulomb", [1.0,        ["ampere","second"], []]         ],
             ["cm",      [0.01,       ["meter"],           []]         ],
             ["day",     [24,         ["hour"],            []]         ],
             ["fortnight", [14,       ["day"],             []]         ],
             ["furlong", [0.125,      ["mile"],            []]         ],
             ["hour",    [60.0,       ["minute"],          []]         ],
             ["minute",  [60.0,       ["second"],          []]         ]
           ];
         

  Each line in the database is thus a list of two elements - the first element is a string that names some unit and the second element is a quantity List that is equivalent to that named unit.

  There are two databases provided for testing: one named unicalcDB in the file unicalcDB.rex and one named miniDB in the file miniDB.rex, above.

  Not every unit is defined in terms of others in the database. Some are intentionally left undefined. We'll call these undefined units basic units. In the above example, ampere, meter, and second are basic units.

  A database does not need to contain conversions for everything to everything; that would tend to make it very large and maintenance would be error-prone. Instead, all conversions done by Unicalc are derived from basic units in the database.

Individual functions to write

Your task is to write four functions (helper functions are welcome, too) that will be important in implementing this unit calculator:

• simplify
  
  The representation of a quantity is said to be simplified if there is no element common to its numerator and denominator lists. One way to convert a quantity list to an equivalent, simplified form is to "cancel" any pairs of elements common to its numerator and denominator. So, create a Rex function simplify( QL ) that takes in QL, a quantity list. Then, simplify should return an equivalent, fully simplified quantity list.

  Rex's pattern matching comes in handy here! For example, you could use the following syntax to start your simplify function:

  simplify( [q, N, D] ) => 
  

  Here, q is the numeric quantity; N is the numerator list of unit names; and D is the denominator list of unit names. In fact, you won't need any other cases, because simplify will only take in quantity lists!

  Also, keep in mind that the elements in both the numerator and denominator lists should be sorted:

  test( simplify( [42, ["kg", "meter", "second", "second"],
  		     ["kg", "kg", "second"]] ),
        [42, ["meter", "second"], ["kg"]] );
  
  test( simplify( [3.14, ["meter", "second"],
  		       ["meter", "second", "second"]] ),
        [3.14, [], ["second"]] );
  

  You might want to use the diff function we discussed in class as a helper function here!



• multiply and divide
  
  Construct Rex functions multiply( QL1, QL2 ) and divide( QL1, QL2 ) that multiply and divide two quantity lists, respectively, and then yield a simplified quantity list as a result. You should assume that the numeric element of a quantity list will never be 0. Some example runs include

    
  test( multiply( [2, ["meter"], ["second"]],  [3, ["kg"], ["second"]] ),
        [6, ["kg", "meter"], ["second", "second"]] );
  
  test( divide( [10, ["meter"], ["second"]],  [5, ["meter"], []] ),
        [2, [], ["second"]] );
  
  test( divide( [10, ["meter"], ["second"]],  [5, ["ampere"], ["hertz"]] ),
        [2, ["hertz", "meter"], ["ampere", "second"]] );
  

  Note that using the merge function covered in class (and whose code is available from the top-level assignments page) will make implementing these two functions simpler.

  Warning!: before dividing two numeric values for your divide function, it's a good idea to multiply the numerator value by the floating-point value 1.0. That way, the division will be floating-point, not integer! Thus, you might have

  divide( [q1, N1, D1], [q2, N2, D2] ) => [ q1*1.0/q2, ... ];
  

  This also provides a suggestion as to how to use pattern-matching on quantity lists: [ q, N, D ].



• conv-unit
  
  

  In the miniDB example of a unit database (above), there are three basic (irreduceable) units: "ampere", "meter", and "second", since they are not the left-hand-side of any of the association list's conversions. Indeed, these three units are, in fact, basic units in the international system (SI)

  Write a Rex function convUnit(unitname, DB) that takes as inputs a string unitname and a database association list. If unitname is defined in the database, then convUnit returns that unit's looked-up quantity list. On the other hand, if the unitname does not have a conversion in the database, then convUnit should return a standard quantity list representing the unit: [1.0, [unitname], []]. For example,

    
  test( convUnit( "hour", miniDB ),  [60.0, ["minute"], []] );
  test( convUnit( "meter", miniDB ),  [1.0, ["meter"], []] );
  

  Thus, convUnit "recognizes" basic, irreduceable units because they are the ones that can only be defined in terms of themselves, as in the latter "meter" example. Here, you'll want to use the Rex built-in function assoc to do most of the work. We used assoc in homework #1's wordScore problem: assoc(e,AL) looks up e in the association list AL. Note that if e is not found in the association list, then assoc( e, AL ) returns the empty list []. If the assoc function does find e, you'll want to use the built-in second function to extract the second element of the list returned.

part2.rex    Pair or individual problems, #4 and #5

You're welcome to work on the second half of this week's problems on your own, but we'd encourage you to do so with a partner, if you'd like. If you do work in a pair, be sure to work at the same physical place and to trade off at the keyboard/debugging roles, as described in the syllabus.

Whether you work on your own or with a partner, you should submit your definitions for these functions in a file named part2.rex.

Problem 4:    Unicalc! (part 2)

[20 points, individual or pair]

Since this problem continues the last one, you will want to copy your working unicalc functions simplify, multiply, divide, and convUnit into the file part2.rex.

There are three more functions that will complete the unit-calculator: normUnit, norm, and convert. The bulk of the work is done by norm and normUnit: these two functions each call the other, a technique known as mutual recursion. This is a powerful technique, but requires a clear understanding of both functions before writing either one. So, we'd suggest reading both of the next two descriptions and then implementing norm and normUnit.

As their names are meant to suggest, both norm and normUnit output a normalized quantity list equivalent to their respective inputs. A normalized quantity list is one in which the numerator and denominator lists contain only basic units. Put another way, in a normalized quantity list there are no more units with conversions in the database. For example,

normUnit( "hour", miniDB );  should output  [3600.0, ["second"], []]

norm( [2, ["mile"], ["hour"]], miniDB );  should output  [0.89408, ["meter"], ["second"]]

• normUnit
  
  The function normUnit( unitname, DB ) takes the same two types of input arguments as convUnit. Just as in convUnit, your normUnit function should return [1.0, [unitname], []] in the case that unitname is a basic, irreduceable unit -- note that this output is a normalized quantity list!
  
  If unitname is not a basic unit, then normUnit should return a normalized quantity list equivalent to the looked-up value of unitname in DB.
  
  You may find it easier to use convUnit as a guide to writing normUnit, rather than calling convUnit. That is up to you. Either way you'll need to call norm, below!


• norm
  
  Ths function does almost the same thing as norm-unit. The difference is in the form of the input: the function norm(QL, DB) takes as input any quantity list QL and a unicalc database DB. Then norm(QL, DB) outputs the normalized equivalent to the quantity list QL with respect to the database DB.

  Hints on norm and normUnit: note that norm does the same thing as norm-unit, only with a slightly different first input. Because of this, norm and norm-unit are naturally written as mutually recursive functions, i.e., each calls the other at one or more points. The key to writing mutually recursive functions is being sure you have a clear sense of what each function does at an abstract level -- that way, you can use either as appropriate.

  For normUnit, it will check if its first input can be looked up in the database that is its second input.

  You might consider the following three cases for norm:

  • If the input quantity list has an empty numerator and an empty denominator... no problem?
  • If the input quantity list has a non-empty numerator, but an empty denominator. The idea here would be to use multiply as well as mutual recursion.
  • Finally, if the input quantity list has a non-empty denominator, consider peeling off one of the denominator's elements and not worrying about the numerator! How should you combine that element and the other pieces of the input quantity list?

  Here are some examples of normUnit and norm in action. Be sure to try these tests after both are written!

  test( normUnit( "hour", miniDB ),  [3600.0, ["second"], []] );
  test( normUnit( "meter", miniDB ),  [1.0, ["meter"], []] );
  
  test( norm( [1.0, ["hour"], []], miniDB ),  [3600.0, ["second"], []] );
  test( norm( [42, ["meter"], []], miniDB ),  [42.0, ["meter"], []] );
  test( norm( [2, ["meter"], ["cm", "cm"]], miniDB ),  [20000.0, [], ["meter"]] );
  




• convert
  
  

  The conversion process from the quantity list QL1 to the quantity list QL2 can now be described as the result of normalizing QL1 by QL2, and then dividing the former by the latter... . Thus, convert( QL1, QL2, DB ) will be a short function to write!

  Try it out with a few examples:

  test( convert( [125, ["cm"], ["second"]], [1.0, ["meter"], ["second"]], miniDB ),
        [1.25, [], []] );
  
  test( convert( [125, ["cm"], ["second"]], [1.0, ["meter"], ["second","second"]], miniDB ),
        [1.25, ["second"], []] );
  
  test( convert( [125, ["cm"], ["second","second"]], [1.0, ["meter"], ["second"]], miniDB ),
        [1.25, [], ["second"]] );
  

On the precision of your answers...

Do not worry if your answer is slightly off from the above - for example, less than a few hundredths. For example, you might have an output of

[1.24999, [], []]

convert( [1.0, ["mile"], ["hour"]], [1.0, ["inch"], ["second"]], miniDB );
// Rex should answer the above convert close to [17.6, [], []]

convert( [1.0, ["mile"], ["hour"]], [1.0, ["foot"], ["second"]], miniDB );
// Rex should answer the above convert close to [1.46667, [], []]

convert( [1.0, ["mile"], ["hour"]], [1.0, ["foot"], []], miniDB );
// Rex should answer the above convert close to [1.46667, [], [second]]

If you made it to here, congratulations, you have completed Unicalc!

Problem 5:    shortestPath

[20 points, individual or pair]

The shortest-path problem asks how to most efficiently get from "point A" to "point B" in a graph -- it is thus a generalization of the reachable problem we considered in class.

Since many problems in computer science boil down to questions about graphs, the shortest-path problem has many applications: providing the best map-directions, minimizing the cost of manufacturing procedures, or finding the most efficient layout of components on a microprocessor board, as just a few examples.

For example, in the directed graph

G0 = [ ["A","B"], ["B","C"], ["C","D"], ["D","E"], ["B","E"] ];

For this problem, write shortestPath( a, b, G ) that returns a list of nodes visited along a shortest path from a to b in G. There may be more than one shortest path -- in that case returning any one of them would be OK. For example, provided G0 is defined as above:

test( shortestPath( "A", "E", G0 ),   ["A", "B", "E"] );
test( shortestPath( "E", "E", G0 ),   ["E"];
test( shortestPath( "E", "A", G0 ),   [] );

Note:    Half of the credit for this problem is awarded for being able to find shortest paths in acyclic graphs, i.e., graphs that do not contain cycles. The other hald of the credit is for handling test cases in which the input graph does contain cycles. Recall that the "use-it-or-lose-it" approach to reachable was able to handle graphs with cycles... .

Hints:    If you take the use-it-or-lose-it approach to this problem, you may want to start from the reach example of that approach that we looked at in class (the code is here). Warning! there are additional cases to consider than in the reach example. It is not enough simply to find the shortest path that "uses" the first edge and the shortest path that "loses" the first edge, and then choose the smaller of the two! The problem is that the "loseit" path or either half of the "useit" paths might not exist...! Thus, a solution will have several cases to check.

Tests:    Here are some additional tests, the first set with acyclic graphs and the second set on graphs with cycles:

// two acyclic graphs
G1 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","F"],
      ["A","Z"],["Z","F"]];

G2 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","F"],
      ["A","Z"],["Z","E"],["E","Y"],["Y","F"],["F","G"]];

// two graphs with cycles
G3 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","A"]];

G4 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","A"],
      ["X","Y"],["Y","Z"],["Z","B"],["E","X"]];

// serveral tests
test( shortestPath("Z", "A", G1),    [] );
test( shortestPath("A", "A", G1),    ["A"] );
test( shortestPath("A", "B", G1),    ["A","B"] );
test( shortestPath("A", "D", G1),    ["A","B","C","D"] );

test( shortestPath("A", "G", G2),    ["A","Z","E","F","G"] );

test( shortestPath("B", "A", G3),    ["B", "C", "D", "E", "A"] );

test( shortestPath("X", "A", G4),    ["X", "Y", "Z", "B", "C", "D", "E", "A"] );

Complex.java    Pair or individual problem, #6

You're welcome to work on this Java class, named Complex, on your own. Yet we'd encourage you to do so with a partner, especially if Java is new. If you do work in a pair, be sure to work at the same physical place and to trade off at the keyboard/debugging roles, as described in the syllabus.

Whether you work on your own or with a partner, you should submit your Complex class in a file named Complex.java. Be sure to grab the starting file from /cs/cs60/hwfiles/a3.

Problem 6:    Implementing Complex numbers with class!

[20 points, individual or pair]

This problem introduces the implementation of data structures in Java. In addition, it is a chance to either introduce yourself or review what Java looks like and how java code is structured. If you haven't used Java before, you may need to review a bit about the language. In particular, there are example Java programs as well as a very small starting point for your Complex.java file on the top-level assignments page. Also, there are on-line references and tutorials available from the references page.

Testing your code!    Just as in Rex, you should test each of your methods as you write it. To do this in Java, add lines to your Complex class's main method that test each of your methods. For this assignment, we will simply check visually that the answers are what they should be, so feel free to do the same. It's much easier to make small syntactic errors in Java than in Rex -- there is simply more code where errors can appear! To help with this, the starter file provides lots of tests in a comment in main. As you implement your Java methods, uncomment the appropriate tests and try them out!

Reminders on running Java    The command (typed at the command-line)

     
% javac Complex.java

     
% java Complex

Java has eight built-in 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 complex numbers commonly used by mathematicians, scientists, engineers, i.e., Math 11 students. Therefore, your task this week is to implement a complex number class. The class should be implemented in a file named Complex.java.

Getting started!    For this problem, you should use the Point.java and Complex.java files available from /cs/cs60/hwfiles/a3/ and from the top-level assignments page as a guide. After all, complex numbers are very similar to planar points... .

Here is a starting point for your Complex class. Using this will help us because it will standarize the names of the data members:

/*
 * Complex.java
 *   a complex number class
 *
 * Name:
 *
 * Comments to the graders:
 

 */

class Complex
{
    private double real;
    private double imag;

    // place your constructors here:



    // *** Please use this toString method to keep things consistent ***

    // 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 = "-";       //

      return "" + this.real + " " + sign + " " + Math.abs( this.imag ) + "i";
    }


    // place your other methods here:



    // main: the starting point for our testing code
    //  in: command-line arguments
    // out: nothing (it's void)

    public static void main(String[] args)
    {
        // a welcoming statement...
        System.out.println("Welcome to the Complex...");

        // feel free to uncomment these lines of code
        // to test as you go!

        /*
        Complex c0 = new Complex( 0.0, 0.0 );
        System.out.println("c0 should be 0.0 + 0.0i");
        System.out.println("c0 is        " + c0);

        Complex c1 = new Complex( 42.0, -60.0 );
        System.out.println("c1 should be 42.0 - 60.0i");
        System.out.println("c1 is        " + c1);
        */

        // you'll want to write more tests so that you
        // know your other functions are working...

        // Do not worry about the small floating-point
        // differences that necessarily arise when using
        // arithmetic on real hardware. 
        // For instance, 2.4999999999999 is OK for 2.5

        // a departing statement...
        System.out.println("where the Complex isn't!");
    }
}

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 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 that you like in order to build your public methods.

• 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...
  
  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 code above) -- 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 = "-";       //
  
        return "" + this.real + " " + sign + " " + Math.abs( this.imag ) + "i";
      }
      

• The class should have a method named equals that takes a Complex argument and determines if the two Complex numbers (this one and the argument) are structurally equal, i.e., whether they are the same complex number. The method should return a boolean which is true if the numbers are equal and false otherwise. Here is the method signature:

      public boolean equals( Complex c )
      

• 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 product 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. A website that explains this in more detail (and offers a calculator that divides complex numbers is available here .

  Here is the method signature:

      public Complex divide( Complex c )
      

A note about commenting your code: Please be sure to have the following three pieces of information as comments at the top of each file: The name of the java class (such as "Complex" in this case), your name, and any comments for the graders. In addition, have at least one line of information that explains what the class is used for. Then, for each method in the class, have at least one line of comments explaining what it does, as well as lines describing the inputs and outputs, if any. If the method does something complicated that might be confusing to someone reading the code, make sure to have explanatory comments within the method as well.

Please also keep your code neat and easy-to-read. Use "whitespace" (spaces and line-breaks) to make your code readable. In theory, you could write your entire program on one very long line. This would be very hard to read. As a good rule-of-thumb, a line should never be longer than 80 characters long. Almost all editors will give you a window that is 80 characters wide. Try to make sure that your lines don't wrap around from one line to the next. A few points in each assignment are allocated for these style, formatting, and design criteria.

Totally optional [and fun!] extra credit...

[worth up to +20 points; individual or pair]

This week's extra credit problem is the first part of the implementation of the OpenList data structure that functional languages (like Rex) use in order to manipulate data safely. The data structure itself is recursive, because each OpenList contains a reference to another OpenList!

As in the past, this week's extra credit will appear in next week's assignment as a required problem... so, if you make progress on it this week, it will help with next week's hw, too.

Because the problem description is lengthy (it is Java, after all!) the OpenList extra credit is available from this link.

Submitting your work

Be sure to submit your part1.rex, part2.rex, and Complex.java files at the CS 60 submission site under "Week 3." If you worked on the extra credit, submit your OpenList.java file there, as well.

Submitting pair programs:    Partners who have created one file together should each submit that file, under their own names. You may have to close the browser and then re-open it, in order to log in as the other person.

A link to hw#1's directions for moving files from machine to machine and for using the submission site.

Problems with submission? Drop me an email at dodds - AT - cs.hmc.edu.