Spring 2001, CSE 428: Solution of MT 2

Exercise 1

   fun minmax (leaf n) = (n,n)
     | minmax (node(t1,n,t2)) = let val (m1,n1) = minmax t1
                                    val (m2,n2) = minmax t2
                                 in (min3(m1,n,m2) , max3(n1,n,n2))
                                end
Note that the declaration val (m1,n1) = minmax t1 has the purpose of extracting the components of the pair returned by minmax t1. In particular, m1 will be associated to the minimum of t1 and n1 will be associated to the maximum of t1. Analogously for the declaration of (m2,n2).

Note also that an expression of the form min3(minmax t1,n,minmax t2) would be wrong, because minmax returns a pair, while min3 requires numbers.

The extraction of the components of a pair is the same problem that was encountered in Exercise 1 of Assignment 5.

Exercise 2

  1. 
         2               
        / \      
       3   4    
      /   / \    
     5   6   7
  


  2.   
         3               
        / \      
       3   3   
      /   / \    
     3   3   3
    Note that the t1 in the anonymous function (fn x => height t1) does not change during the evaluation of the tree (the only t1 which changes is local to map , hence it does not affect the anonymous function). For this reason the application of the anonymous function always returns 3, independently of the argument x.

  3. Error because hd x and tl x have different types, hence they cannot be compared. 

  4.   
   [1,2,3,1,2,3]              
        / \      
    [4,4] [5,5,5,5]  
    /   \    
 [6,6] [7,7]
  


  5.   
       false               
        / \      
    true  false
      /     \    
   false   true
  


  6.   
       false               
        / \      
    false  false
      /      
   false   
  


  7.   
         3              
        / \      
       7  11
      /      
     15

Exercise 3

  1. ML: no,   DR: no

  2. ML: yes,   DR: no

  3. ML: no,   DR: no

  4. ML: no,   DR: yes, to the heap

  5. ML: no,   DR: no (the reason why we don't have DR here is that s2 is local)

Exercise 4

   class Stack {
          
       private class Element {
          int info; 
          Element next;
          Element(int k, Element n) { info = k; next = n; }
       }
             
       private Element head;
    
       public Stack() { head = null; }
    
       public synchronized void push(int k) { 
          head = new Element(k,head); 
          if (head.next = null) notify(); // We can use notify() instead of notifyAll() 
                                          // because a thread can suspend only on pop()
                                          // Note also that the test on (head.next = null)
                                          // avoids unnecessary calls of notify()
       }
       public synchronized int pop() { 
          try { 
             while (head == null) wait(); 
          }
          catch (InterruptedException e) {
             return 0; // We could do a better treatment of interruptions,
          }            // but it's not the object of the exercise
          int n = head.info; 
          head = head.next; 
          return n;
       }
    }

Exercise 5

  1. There are 8 possible sequences: 
    1) in A, out A, in B, out B \
2) in A, in B, out B, out A  \_ "correct" sequences
3) in B, out B, in A, out A  /
4) in B, in A, out A, out B /

5) in A, out B, in B, out A \_ "wrong" sequences due to push-print
6) in B, out A, in A, out B /

7) in A, in B, out A, out B \_ "wrong" sequences due to pop-print
8) in B, in A, out B, out A /
    The sequences 5, 6, 7 and 8 less likely, but still possible. The sequences 5 and 6 are due to the possibility that the two consecutive actions push and print are interleaved oddly with actions of the other thread. The sequences 7 and 8 are due to an analogous odd interleaving for the sequence pop-print. Note that even though at the source level there is only an instruction which does pop-print, at the machine level this instruction is broken into a sequence of elementary steps which can be interleaved in between.

    You can check yourself that all these sequences can be obtained. Download this code and save it with name Test.java. Then give the command 

       javac Test.java
    and then give the command 
       java Test
    Repeat the latter command several times to see different outputs.

  2. As discussed above, the answer is yes. One possible remedy is to extend the class Stack with two synchonized methods, pushAndPrint(int) and popAnPrint(), and replace in the run() method the sequences push-print and pop-print with calls to pushAndPrint(int) and to popAnPrint() respectively.

    Another possibility is to use a semaphore and treat the sequences push-print and pop-print as critical sections.