CSE 373, Autumn 2004: Assignment 1

Objectives

When and How

The Exercises

1. Math Background:
   1. Consider the set S = {0, 1, 2}. Give 2^S, the power set of S.
      2^S = { ...
      }
   2. Determine which of the following properties hold for the binary relation B over the set S, where S = {a, b, c}, and B = {(a, a), (a, b), (b, b), (b, c), (a, c)}.
      reflexive
      symmetric
      antisymmetric
      transitive
      partial order
      total order
      function
      surjection
      injection
      invertible function
      partial function
       
      For each of the properties above that fails to hold, give a minimal set of deletions and additions of ordered pairs that achieves the property. For example, for symmetry, we must make three changes: either remove (a,b) or add (b,a); either remove (a,c) or add (c,a); either remove (b,c) or add (c,a).
   3. Let's use the symbol X to denote cartesian product. Write out the elements of S X W X W, where S = {a, b, c} and W = {0, 1}.
      Now write out the elements of (S X W) X W.
      Is it true that | S X W X W - (S X W) X W | = 0 ?
      Why or why not?
2. Write a Java program that features a recursive method that takes two linked lists A and B of objects and returns a list in which the elements of A and B have been interleaved.
   You may use the following starter code.

   public class Interleave {
   
   public static void main(String[] args) {
      Node listA = Node.makeList5(0,4,8,12,16);
      Node listB = Node.makeList5(1,5,9,13,17);
      Node listC = Node.interleave(listA, listB);
      Node.printList(listC);
      }
   }
   
   class Node {
      Object data;
      Node next;
   
      static Node addToFront(Object newData, Node oldList) {
         Node n = new Node();
         n.data = newData;
         n.next = oldList;
         return n;
      }
      Node addIntToFront(int i) {
         return addToFront(new Integer(i),this);
      }
      static Node makeList5(int a,int b,int c,int d, int e) {
         Node n = new Node();
         n.data = new Integer(e);
         n.next = null;
         n = n.addIntToFront(d);
         n = n.addIntToFront(c);
         n = n.addIntToFront(b);
         n = n.addIntToFront(a);
         System.out.println("The result of makeList5 is ");
         Node.printList(n);
         return n;
      }
      static Node interleave(Node listA, Node listB) {
         System.out.println("Entering interleave... ");
       // put your code here.
      }
   
      static void printList(Node list) {
         if (list == null) { System.out.println(); }
         else {
            System.out.println(list.data + "; ");
            printList(list.next);
         }
      }
   }
   

   Test your program with a Java compiler and runtime system. (For this assignment you are free to use the Java system of your choice. Future assignments will require the use of Eclipse. If you already know how to use Eclipse, you are welcome to use it now.) Turn in a printout of your code and of your test run's output.