This file contains answers to the questions posed in handout "CS2aa About Prelim 2"

Questions on correctness of programs

1. An assertion is a true-false statement that is placed within a program to indicate that it is (or should be) true at that place. A Hoare triple has the form shown on the question: {precondition} statement {postcondition}. It has the meaning: execution of statement begun in a state in which the precondition is true is guaranteed to terminate with the postcondition true.

2. The precondition is the postcondition with every occurrence of x replaced by 2*x*y:  2*x*y+y < 64.

3. See the handout on correctness.

4. The first four algorithms are given in the handout on correctness. Here's (e)
The algorithm stores a^b in z, for b>= 0

    // {b >= 0}
    int x= a; int y= b;
    // {invariant: y>=0 and z*x^y = a^b }
    // {bound function: log y }
    while (y >= 0) {
        if (y%2 == 0) {x= x*x; y= y/2; }
        else                 { z= z*x; y= y-1; }
    }
    // {postcondition: z= a^b }

5.
(a)  i= h+1; x= 0;
      while (i  != k) {
          if (b[i] != b[i-1])  x= x+1;
          i= i+1;
      }

(b) j= k; x= 0;
     while (h != j) {
         j= j-1;
         if (b[j] = 0) x= x+1;
     }

(c) b= 1;
     while (2*b <= n) {
         b= 2*b;
     }

(d) p= b;
     while (p != null  &&  !p.element.equals(v))
        {  p= p.next; }

(e) p= h; q:= p; t= n;
    while (q != t) {
        if (b[q] is red) { Swap b[p] and b[q]; p= p+1; q= q+1; }
      else if (b[q] is white) { q= q+1; }
      else {  Swap b[q] and b[t]; t= t-1;}
      }

(f) Precondition: true
     Postcondition: 1 <= n <= 1000 and
                             pi is the sum of the first n terms of the sum  and
                             x = term n  and  abs(x) < 0.00001.
     Invariant:         1 <= n <= 1000 and
                             pi is the sum of the first n terms of the sum  and
                             x = term n
     Bound function: 1000 - n

     int n= 1;
     double pi= 4;
    double x= 1;
     while (n != 1000 && Math.abs(x) >= 0.00001) {
         n= n+1;
         x= 4/(2*n-1);
         if (n%2 == 0) x= -x;
         pi= pi + x;
     }

 (g) We did this one in some recitation handout.
 
 

Questions on older material (classes, subclasses, interfaces, exceptions)

1. A name m is overloaded if two methods with different signatures have name m; overloading can also occur if a variable and a method have the same name. Overriding refers to redefining a method is a subclass that is defined in a superclass.
 

2. We don't have an answer yet.
 
 
 

        1 2 3 * 4 - 12 6 / 7 * + +
 

b) What is the asymptotic complexity of your algorithm, expressed as a function of n1 and n2, where n1 is the number of
elements in L1 and n2 is the number of elements in L2?  Justify your answer (briefly).

class LisNode {
        protected Object element;
        protected ListtNode next;

        // Constructor: an instance with element x and next field n
        public ListNode (Object x, ListNode n) {
                datum = x;
                next = n;
        }

        public Object getElement () {
                return element;
        }

        public ListCell getNext () {
                return next;
        }

        // Set this node's element to x
        public void setElement (Object x) {
                datum = x;
        }

        // Change this next field to l
        public void setNext (ListNode l) {
                next = l;
        }

        // Print this element together with the rest of the elements in this List
        public String toString () {
                if (next == null) return element.toString();
                return element.toString() + " " + next.toString();
        }
}
 

       f(n) = 2n log(n) + 4n + 17 * log (n)
       g(n) = log(n*n*n)

(c) The following method returns the element number i of an integer list.

public static int element (List list, int i) {
        if (i == 1) return list.first();
        return element(list.rest(), i-1);
}

             (22)

           /      \

       (14)        (25)

      /   \       /    \

   (11)   (16) (23)     (40)

                  \     /

                 (24) (32)

• In what order are the nodes visited during a preorder traversal?  Inorder traversal?  Postorder traversal?
• Show the tree that results when 15 is inserted into the tree.
• Show the tree that results when 25 is deleted from the original tree.

• Operations are Insert, DeleteMax, and DeleteMin.

balanced tree or sorted doubly-linked list
• You have a dictionary containing the keywords of the Pascal programming language.

ordered array or balanced tree
• You have a dictionary that can contain anywhere from 100 to 10,000 words.

unordered linked-list or hash table
• You have a large set of integers with operations insert, findMax, and deleteMax.

unordered array or Hashtable

        h(x) = (sum of the values of the first and last letters of x) mod m

where the value of a letter is its position in the alphabet (e.g., value(a)=1, value(b)=2, etc.). Here are some precomputed hash values:

Draw a picture of the resulting hashtable (using chaining) after inserting, in order, the following words: ibex, hare, ape, bat, koala, mud, dog, carp, stork. Which cells are looked at when trying to find bird?  What is the load factor (lambda) for the hash table?
 

• Under what conditions would you use a balanced tree instead of hashing with chaining?
• Under what conditions would you use an unordered array instead of a balanced tree?
• Under what conditions would you use a binary search tree instead of a heap?
• What implementation would you use to get the best expected time for a search?
• What implementation would you use to get the best worst-case time for a search?

     a.What is the running time for each method when all the keys are equal?
     b.When the keys are in order?
     c.When the keys are in reverse order?
 

public class Num1 implements Enumeration {

    public Num1() { }

    public boolean hasMoreElements()
        { return true;  }

    public Object nextElement()
        { return "hello";  }
}

public class Num2 implements Enumeration {

    public Num2 { }

    private boolean hasMoreElements()
        { return true;  }

    private Object nextElement()
        { return "hello";  }

}

public class Num3 implements Enumeration{

    String[] x;
    int k = 0;

    public Num3() {
        x = new String[10];
        for (int i = 0; i < 10; i++)
        x[i] = "" + i;
     }

    public boolean hasMoreElements()
        { return (k < x.length);  }

    public Object nextElement()
        { return x[k++];  }

    public Object nextElement(int j)
        { return x[j];  }
}