Spring 2000, CSE 428: Solution of test 2

Question 1

The output is: first 1 (no modification in c because it's passed by value), and then 3 (c is modified because we pass the pointer to it)
The output is 2 (c is modified because in Java we pass always a reference to it)

Question 2

A stack for unithread use can be defined in Java as follows:

   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 void push(int k) { head = new Element(k,head); }

      public int pop() { // ignore the case of an empty stack
         int n = head.info; 
         head = head.next; 
         return n;
      }
   };

Note that we don't have a destructor method: Java has garbage collection, so we don't need to take care of heap deallocation.

A stack for multithread use can be defined in Java as follows:

   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); 
         notify(); // We can use notify() instead of notifyAll() 
      }            // because a thread can suspend only on pop()

      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;
      }
   };

Question 3

One way to ensure that the print of the content of the two stacks is not interleaved is to use a semaphore. Note that synchronizing the method popAndPrintAll() would not work, because there are two different stacks. Namely, the critical section is in the printing activity, not in the extraction of elements from the stack.

A semaphore can be defined as in the solution of Assignment #6. Then we need to modify the definition of the class MyThread in the following way:

   import Stack;     // import the definition of the class Stack
   import Semaphore; // import the definition of the class Semaphore
   
   class MyThread extends Thread{
      private Stack myStack;
      private Semaphore sem;
      public MyThread(Stack stk, Semaphore smp) { myStack = stk; sem = smp; }
      public void run() {
         try {   // down() throws InterruptedException, so we need to catch it
            sem.down();
            myStack.popAndPrintAll();
            sem.up();
         }
         catch (InterruptedException e) { }  // if interrupted, do nothing  
      }
   }

Finally, we need to modify the definition of the main() function as follows:

   public static void main(String[] args) { 
      Semaphore sem = new Semaphore(1); // only one thread allowed 
                                        // in the critical section  
      Stack s1 = new Stack();
      s1.push(1);
      s1.push(2);
      ...
      s1.push(...);
      
      Stack s2 = new Stack();
      s2.push(1);
      s2.push(2);
      ...
      s2.push(...);

      MyThread T1 = new MyThread(s1,sem);
      MyThread T2 = new MyThread(s2,sem);
      T1.start();
      T2.start();
   }

Question 4

The methods which need to be synchronized are: depositOrWithdraw() and getBalance(). The method Account(int, int) does not need to be synchronized because it's a constructor, and the method getAccountNumber() does not need to be synchronized because the field accountNumber is not modified by any method except the constructor.

Question 5

   fun filter_positive [] = []
     | filter_positive (a::L) = if a > 0 then a::(filter_positive L)
                                         else filter_positive L;

Question 6

   datatype 'a btree = leaf of 'a | node of 'a btree * 'a btree;

   fun fringe (leaf a) = [a]
     | fringe (node(T1,T2)) = append(fringe T1, fringe T2)
   and
       append([],K) = K
     | append(a::L,K) = a::append(L,K);