Midterm solutions
   -----------------

Question 1.

  (a) Binary search  - 4
      Circular queue - 3
      Unsorted array - 2
      Doubly-linked list - 2
      Priority queue - 1
      List           - 3


   (b) This means that m has default accessibility.  Only classes in the same
       package can access m.

       a class that is a subclass of C and is in package P             CAN
       a class that is a subclass of C and is in different package     CANNOT
       a class that is not a subclass of C and is in package P         CAN
       a class that is not a subclass of C and is in different package CANNOT

Question 2.

   (a)
class Queue extends Container {
     // end of the queue
     private ContainerNode tail;

     public Queue () {
       super.Container();
       tail = null;
     }

     public void insert (Object stuff) {
       if (head == null) {
         head = stuff;
         tail = stuff;
       }
       else {
         tail.next = stuff;
         tail = stuff;
       }
     }
    

     public Object remove () {
       // body of remove goes here
     }

     public boolean isEmpty () {
       return (head == null)
     }
}

  (b)  Queue()   adds to Container
       insert()  overrides Container
       remove()  completes Container
       isEmpty() adds to Container
    

  (c)  Cannot include Container as an instance variable because
       Container is an abstract class and therefore cannot be
       instantiated.


Question 3.

  (a)  Base case(s):  Prove that S(3), S(4)
       Let k be an arbitrary integer >= 3

  (b)  This proves absolutely nothing because the inductive step cannot
       be used to derive new facts:  it starts with k > 5, whereas
       the base case is S(5).


Question 4.
                        2              2
  Prove for all n > 1, n  + 1 < (n + 1)
   
  Proof by contradiction.
          2               2
  Assume n  + 1 >= (n + 1)
        2        2                        2
       n  + 1 = n  + 2n + 1 - 2n = (n + 1)  - 2n
                         2                2
       Therefore, (n + 1)  - 2n >= (n + 1)
                  - 2n >= 0

       Since n > 1, -2n < 0
       Contradiction.
                             2              2
  Therefore, for all n > 1, n  + 1 < (n + 1)


Question 5.

  (a)  Yes, this code is perfectly legal.

  (b)  new list will have nodes "this" and "luck" changed places

  (c)  Jibberish(x, y) takes a linked list in which neither
       x nor y is the first element, and x is not adjacent
       to y, and swaps nodes referenced by them.