CSE 373, Spring 2004: Assignment 1

Title: Testing Our Tools

Due Date: Friday, April 9 (turn in hardcopy at the beginning of class)

Work Mode: Individual

Consider the following Java code for representing linked lists of integers.
We will assume that negative integers are never inserted into these
lists.  (1) Either load this code into an Eclipse project (recommended,
if your computer is powerful enough to run Eclipse), or use the Java
J2SDK tools from the command line and first compile and then run the
program.  For more about Eclipse, see the class Syllabus page and the
Eclipse web site at www.eclipse.org.


/*
 * Created on Mar 27, 2004
 *
 * IntList
 * Starting code for comparing iteration and recursion.
 */

/**
 * @author Steve Tanimoto
 *
 */
public class IntList {

    // instance variables:
    private int cellVal;
    private IntList next;

    // accessor methods:
    public int getCellVal() { return cellVal; }
      IntList getNext() { return next; }
    void setCellVal(int n) { cellVal = n; }
    void setNext(IntList nxt) { next = nxt; }

    // constructor:
    public IntList(int n, IntList nxt) {
      cellVal = n;
      next = nxt;
    }

    // self-textification:
    public String toString() {
      String restString = "NIL";
      if (next != null) restString = next.toString();
      return "(" + cellVal + " . " + restString + ")";
    }

    // static methods:
    public static void main(String[] args) {
      IntList oneOdd = makeTest(0,2,4,1,6);
      IntList noOdds = makeTest(0,2,4,6,8);
      System.out.println("oneOdd = " + oneOdd.toString());
      System.out.println("noOdds = " + noOdds.toString());
    }

    static IntList makeTest(int n0, int n1, int n2, int n3, int n4) {
       IntList t = new IntList(n4, null);
       t = new IntList(n3, t);
       t = new IntList(n2, t);
       t = new IntList(n1, t);
       t = new IntList(n0, t);
       return t;
    }

    // additional instance methods, to be developed:				     
    public int firstOddIteratively() {
      return -1; // Replace this with your code.
    }

    public int firstOddRecursively() {
      return -1; // Replace this with your code.
    }
}

Note: There is nothing for you to turn in for exercise 1.

(2) Add to the class IntList by writing an iterative method for finding
and returning the first odd number in the list headed by the
current instance. If there are no odd numbers in the list, then
it should return -1. This method should have the name firstOddIteratively().
The prototype for this method is given in the starter code.

Now create another method that has similar functionality but that it works
recursively and has the name firstOddRecursively().

Add code to test both functions, using not only the given lists
oneOdd and noOdds, but also the lists
allOdd = (1,3,5,7,9)  and
twoOdd = (0,2,7,8,9).

In the paper you turn in, give a listing of (a) your definitions
for firstOddIteratively() and firstOddRecursively(); do not show
any of the other code unless it is something new that you have written to
support these functions; (b) a listing showing the eight tests
(the four different lists with each of your two methods).

(3) Prove by induction that firstOddRecursively does in fact return
the first odd number in the list, if there is any odd number.
Clearly label both the basis and the induction step of your proof.

(4) Let S1 = {0, 1, 2}, S2 = {a, b}, S3 = {c, d}
    a. Write out the elements of (S1 U S2) X S3
    b. Write out the elements of S2 X S2 X S3
    c. Write out the elements of S2 X (S2 X S3)
       
(5) Let f be a function consisting of the following ordered pairs: 
                 { (0, a), (1, a), (2, b), (3, c), (5, e)}
    a. What is the domain of f?
    b. What is the range of f?
    c. Is f a surjection? (Is every element of the range used?)
    d. Is f an injection? (Is no range element used more than once?).
    e. Is f a one-to-one correpondence?
    f. Let f' be the set of ordered pairs obtained from those in f by
       reversing their order. Is f' a function?
       
6. Let us define a "mid-list" to be a data structure that contains a
list, but whose elements are always inserted and removed in the
middle. If there are n elements in the list and we remove an
element, it's the element in position floor(n/2) that gets
removed. If we insert an element, the element is added right before
the element in position floor(n/2), if any. Assume that our
mid-list holds elements of type Integer.

    a. Give a formal description of the MID-INSERT operator for a mid-list.
    b. Give a formal description of the MID-REMOVE operator for a mid-list.

For each operator, consider it to be a function. Give the domain
and range of the function. Then describe how it maps a domain
element into a corresponding range element using a symbolic
notation.  It may be simpler to give separate cases for n even and
n odd rather than to try to show both even and odd cases in the same
expression.

Finally, explain using pseudocode how to implement these operations
using a pair of stacks, S0 and S1 to represent the left half and
right half of the mid-list, respectively.  Use N to represent the
number of elements currently in the mid-list and use E to represent
the new element being inserted by MID-INSERT.  Assume that E is of
a type called Element.