Exercise 1

1. ML: no, DR: no
2. ML: yes, DR: no
3. ML: no, DR: no
4. ML: no, DR: no
5. ML: no, DR: yes, to the stack

Exercise 2

   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 3

1. i1 i2 p1 p2
   i1 p1 i2 p2
   i2 i1 p2 p1
   i2 p2 i1 p1

2. With the modification we could have, in principle, also sequences like i1 i2 p2 p1. This is because the elementary steps which constitute the instruction System.out.print("p" + myQueue.pop() + " "); may be interleaved with those of another thread. In particular, between the execution of myQueue.pop() and the execution of the print, there may be another thread which does a pop as well, and print the value popped. Thus a value popped second may actually appear first in the output sequence.

Exercise 4

   class Boat{
      
     private int remainingCapacity;
     private int currentWeight; 
    
     public Boat(int c) { remainingCapacity = c; }

     public synchronized void getIn(int k) throws InterruptedException {
        while (remainingCapacity < k) wait(); 
        remainingCapacity = remainingCapacity - k;
     }

     public synchronized void getOut(int k) {
        remainingCapacity = remainingCapacity + k;
        notifyAll();    //Note that notify() would not work here
     }

Exercise 5

1. 21 (the sum of all the elements)
2. error (the result of reduce should be of the same type as the elements of the tree)
3. 6 (the maximum element)
4. [7,4,8,1,2,3,5,6] (the concatenation of all the elements, according to the in-order traversal)
5. false (the conjunction of all truth values on the tree)
6. (16,20) (the componentwise sum of all the elements)

Exercise 6

   fun aux p [] n = []
     | aux p (x::L) n = (if p x then [n] else []) @ (aux p L (n+1));

   fun positions p L = aux p L 1;

Exercise 7

   fun apply_repeatedly 0 f x = x
     | apply_repeatedly n f x = f(apply_repeatedly (n-1) f x);