CSE 428, Spring 2000: Solutions of Midterm 2

Exercise 1

   fun factorials [] = []
     | factorials (a::L) = if a<0 then 0::factorials L
                                  else fact(a)::factorials L
   and
       fact 0 = 1
     | fact n = n * fact (n-1);

Exercise 2

  1. The correct definition is:
       datatype 'a btree = empty | node of 'a btree * 'a * 'a btree;
    
    Note: some people defined the datatype as
       datatype 'a btree = empty | leaf of 'a | node of 'a btree * 'a * 'a btree;
    
    This is also correct, but it's redundant, because the tree with only one node x will have two representations: node(empty,x,empty) and leaf(x). Of course there are also all the redundancies induced by this one, and programs will be much more complicated to write.

    On the contarry, the definition

       datatype 'a btree = leaf of 'a | node of 'a btree * 'a * 'a btree;
    
    is not correct, because cannot represent the empty tree. Note that cannot represent the trees like T1 and T2 either, because of the nodes which have one subtree empty and one not (like the node 2 in T1, whose right subtree is empty and the left subtree is not)

  2.    fun height empty = 0
         | height (node(T1,x,T2)) = 1 + max (height T1, height T2)
       and
           max(x,y) = if x < y then y else x;
    

Exercise 3

   class Queue {
       private class Element {
	   int info;
	   Element next;
	   Element(int n) { info = n; next = null; }
       }
       private Element front;
       private Element rear;
       Queue() { front = rear = null; }
       public synchronized void insert(int n){
	  if (front == null) 
	    { front = rear = new Element(n); notifyAll(); }
	  else
	    { rear = rear.next = new Element(n); }
       }
       public synchronized int pop(){
	   try { 
	       while (front == null) wait(); 
	   } catch (InterruptedException e) { 
	       return 0; // We could do a better treatment of the case
	   }             // of interruption, but it's not the object of the exercise
	   int n = front.info;
	   front = front.next;
	   if (front == null) { rear = null; }  //this line is not necessary
	   return n;
       }
   }     

Exercise 4

  1. Yes
  2. No: if the semaphore is initialized to 2, then it will allow two threads in the critical (printing) section.
  3. No: even if the two threads are started one after the other, their run() routines may be interleaved
  4. No: the synchronization of run() does not ensure the mutual exclusion; the two threads are two different objects.
  5. No: the synchronization of popAndPrintAll() would ensure the mutual exclusion if the two threads were operating on the same queue, but here we have two different queues.

Exercise 5

  1. 4
  2. No
  3. 1122, 1212, 1221, 2211, 2121, 2112.