Computer Science 15-111 (Sections A & B), Spring 2007

Homework #7

  Due:  Mon 02-Apr-2007 at the start of class
(in-class and online submission).

 

Submit a printed copy of your assignment as you enter class.  Also, for your online submission (which must be the same as your printed submission), place your programs in hw7.zip.  Include the written work in a file hw7.doc (not hw7.txt) in the top level of the zip file.  Remember to just submit your .java files, and not your .class files, random .jpg files, or miscellaneous Eclipse or other IDE-related files.

 

This is a TRUE PAIR-PROGRAMMING ASSIGNMENT.  Pairs are optional, but if you work in pairs, then you submit only one set of solutions, and you each receive the same grades (you may not work in pairs on only part of the assignment – it’s all or nothing).  Be sure to include BOTH NAMES at the top of ALL FILES!

Also, you may not work with the same partner you worked with in a previous assignment – find new partners.  Besides these changes, the rules for “Pair Programmign Lite” apply – see the online course syllabus for details.

Reminder:  Style counts!  Write your code according to our Style Guide!

 

  1. Do the following questions from “Java by Dissection”:
    Ch 12 Review Questions, #3, 4, 7, 9, 10, 11.
    Be sure to do the Review Questions, and not the “Exercises”.

  2. MyLinkedList and MyLinkedListIterator
    Implement a singly-linked list implementation of the Java List interface.  Call your class MyLinkedList, and place it and all the supporting classes in a single file called MyLinkedList.java.  This class should expose an Iterator and a ListIterator called MyLinkedListIterator.  You should start from Hw7InitialCode.java, which you should rename to MyLinkedList.java.  That file contains the API you must implement, and indicates which methods you can leave unsupported.  It also contains the test framework that you should use for this assignment  (see question #3).  Note that your implementation must use MyNode (as defined in the file), and it must expose the public methods getHead() and getTail() – this allows for automated grading (again, see question #3).

  3. MyLinkedListTester
    Using the test framework included in MyLinkedList.java, include a suite of tests for MyLinkedList and MyLinkedListIterator.  You should test every boundary case for every method.  Be sure to test each possible outcome of each conditional, and be sure to make each possible exception be thrown.  As we discussed in class, your tests should be split into two – ListTester, which includes tests which work over any Java List implementation (LinkedList, ArrayList, MyLinkedList), and MyLinkedListTester, which includes test that are particularly to your implementation.

  4. Sparse Polynomials as Linked Lists
    Do Chapter 12 Exercise #34 from “Java by Dissection”, placing all your work in a single file, Polynomial.java.  Expose the following methods in your Polynomial class, as mentioned in the problem in the book:
      public Polynomial add(Polynomial p);  // return this + p
      public Polynomial subtract(Polynomial p); // return this – p
      public Polynomial multiply(Polynomial p); // return this * p
      public Polynomial copy();  // return a copy of this polynomial
    Also, add these constructors:
      public Polynomial(Monomial m); // return a polynomial containing the value
                                         // represented by this Monomial.  Note that
                                     // if this Monomial represents the value zero,
                                     // the Polynomial will contain no Monomials!
    Also, add these methods, as they are straightforward and make the code more interesting and/or useable:
      public int evaluate(int x); // returns this polynomial evaluated at x
      public boolean equals(Object x);     // returns true if x is a Polynomial
                                       // matching this one term-for-term
      public String toString();  //  does this cleanly, as in:  “5x^17 - 3x^3”

    Note that your toString() method must work as follows:
    1. Do not have a leading “+” sign for the first monomial, nor any leading or trailing spaces.
    2. Between each monomial, include a single space, a plus or minus sign, and another single space
    3. Do not include a “+” sign in front of a negative number.  That is, you cannot generate the string “2x^3 + -3x^2”, but instead should generate “2x^3 - 3x^2”.
    4. Do not include a coefficient of 1.  So, instead of “1x^2”, you should generate “x^2”.
    5. Do not include a coefficient of 0.  This should never happen, though, as noted below.
    6. Do not include an exponent of 1.  So instead of “3x^1”, you should generate “3x”.
    7. Do not include an exponent of 0.  So instead of “3x^0”, you should generate “3”.
    8. The empty Polynomial should be represented as “0”.
      
    Use the following simple class for a Monomial:
      class Monomial {
           public int coefficient;
           public int exponent;
      }
    This class should expose two constructors:
      public Monomial();
      public Monomial(int coefficient, int exponent);

    For simplicity, if the coefficient is 0, have your constructor set the exponent to 0 regardless of its provided value – thus, the value 0 is uniquely represented as 0x0 (and not, say, 0x1),

    Note that, for simplicity, we are restricting our coefficients and our exponents to be integers, and you should further assume that exponents are non-negative (greater than or equal to zero).  A Polynomial, then, is a linked list of monomials.  Keep your Polynomial linked list sorted by exponent, with the largest exponents occurring first.  Also, you may have not have the same exponent occurring twice.  Instead, you should combine them into a single monomial, whose coefficient is their sum. And you may not have a coefficient equal to zero – in this case, you must remove this monomial from your polynomial.

    In addition, your Polynomial class must expose this public method:
       public List getMonomialList();
    This returns, as a Java List, the linked list of Monomial objects sorted as noted above, which will be useful for automatic grading purposes.  Then, your Polynomial class must expose these static methods:
      public static void useJavaLinkedList();
      public static void useMyLinkedList();
      public static void useJavaArrayList();
    A call to one of these static methods determines what kind of List will be used to back ensuing Polynomial objects that are created (until another call to one of these static methods).  Except for your constructor, which must use this information to choose the appropriate backing data structure, the rest of your code should use the type List (as opposed to LinkedList, ArrayList, or MyLinkedList), so that it works over each kind of List without modification.

    Finally:  write a suite of tests, using the test framework provided above, to test every aspect of your Polynomial.  You will be graded in part on how complete (yet concise!) your test suite is.

  5. Sparse Matrix Addition and Multiplication Using Linked Lists.
    Do Chapter 12 Exercise #32 and 33 from “Java by Dissection”, placing all your work in a single file, SparseMatrix.java.  Note that you do not have to use a class SMElement, despite the text mentioning this.  Also, you should have a single implementation both for addition and multiplication, so your sparse matrix must include linked lists for both the rows and columns (that is, you’ll use the approach described in #33 to solve the problem in #32 as well).  You should assume that all the values in the matrix are integers, and you should not worry about overflow. Expose the following methods in your SparseMatrix class, as mentioned in the problem in the book:
      public SparseMatrix add(SparseMatrix sm);  // return this + sm
      public SparseMatrix multiply(SparseMatrix sm);     // return this x sm
    You should also expose these accessors and mutators:
      public int get(int row, int col);  // return this[row][col]
      public void set(int row, int col, int val);      // this[row][col] = val
      public int getRows();      // returns the # of rows in this matrix
      public int getCols();  // returns the # of cols in this matrix
    Note that the accessors and mutators should work roughly as though this were NOT a sparse matrix (even though it is).  However, you should be able to set any row,col, and the matrix will “expand” as necessary to accommodate the element.  So, consider the following code:
      SparseMatrix sm = new SparseMatrix();
      sm.set(10,20,3);
      out.println(sm.getRows());   // prints 11  (rows 0 to 10)
      out.println(sm.getCols());   // prints 21  (cols 0 to 20)
      out.println(sm.get(10,20));  // prints 3
      out.println(sm.get(5,5));    // prints 0   (default value)
    Note that there is only one element in the matrix, but it acts as though it is a complete 11x21 matrix, mostly full of 0’s.

    Finally:  write a suite of tests, using the test framework provided above, to test every aspect of your SparseMatrix.  You will be graded in part on how complete (yet concise!) your test suite is.

  6. Enabling Collections.sort
    As written above, unfortunately MyLinkedList will not work with Collections.sort.  That is, the following code (which is commented-out in MyLinkedList.java) will not work:

    // This will not work with MyLinkedList unless
    // you add more functionality to your MyLinkedListIterator...
    public void testCollectionsFramework1() {
          List list = newList();
          list.add(new Integer(3));
          list.add(new Integer(1));
          list.add(new Integer(2));
          Collections.sort(list);
          assert(list.get(0).equals(new Integer(1)));
          assert(list.get(1).equals(new Integer(2)));
          assert(list.get(2).equals(new Integer(3)));
    }

    The problem:  Collections.sort() expects your MyLinkedListIterator to include some additional functionality (such as set()).  Add the required functionality to MyLinkedListIterator to get this test code working.

  7. BONUS [3 pts]:  Using AbstractSequentialList
    It is important for you to understand how to implement the Java List interface from scratch.  But you should also know that Java provides abstract classes that do most of this for you, so defining a new collection class is not nearly so much work.  To see this, create another singly-linked list class, MyBetterLinkedList, which extends AbstractSequentialList (which is the class that, not coincidentally, LinkedList extends).  In this special case, you may copy-and-paste code from your MyLinkedList class, if that helps.  As the online API for AbstractSequentialList notes:  “To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods.”  Now isn’t that easier?  J