Spring 2000, CSE 428: Test 2

Question 1

  1. What is the output printed by the following C++ program ?
       #include  
       
       class Cell{
       private: 
          int x;
       public:
          int get(){ return x; }
          void set(int y){ x = y; }
       };
       
       void setcell1(Cell c){  // parameter of type cell
          c.set(c.get()+1);
       }
       
       void setcell2(Cell* c){  // parameter of type pointer to cell
          c->set(c->get()+2);
       }
       
       void main(){
          Cell c;
          c.set(1);
          setcell1(c);
          cout << c.get();
          setcell2(&c);
          cout << c.get();
       }  
    
    

  2. What is the output printed by the following Java program ?
       class Cell{
       private int x;
       public int get(){ return x; }
       public void set(int y){ x = y; }
       };
       
       public class Test{
        public void setcell(Cell c){ 
          c.set(c.get()+1);
       }
        public static void main(String[] args){    
          Cell c;
          c.set(1);
          setcell(c);
          System.out.println(c.get());
        }
       }   
    

Question 2

Consider the following implementation of a stack in C++:
 
   class Stack {
    
   private:
      class Element {
      public:
         int info; 
         Element* next;
         Element(int k, Element* n) { info = k; next = n; }
      };
	    
      Element* head;
   
   public:
      Stack() { head = NULL; }
      ~Stack() { while (head!=NULL) pop(); }
      void push(int k) { head = new Element(k,head); }
      int pop() { // ignore the case of an empty stack
	 Element* temp = head; 
	 int n = head->info; 
	 head = head->next; 
	 delete temp;
         return n;
      }
   };
  1. Implement an analogous class Stack in Java, for unithread use. Ignore the case of pop() executed on a empty stack.
  2. Modify the implementation so to allow a multithread use of the Stack (i.e. more processes can share the same stack). Make sure that, when pop() is executed on a empty stack, the thread executing the pop() suspends.

Question 3

Suppose that the class Stack previously defined is enriched with the following method, which pops and prints all the elements of the stack:
   public void popAndPrintAll(){
      while (head!=null) System.out.println(pop());
   }
Consider now the following program in java:
   import Stack; // import the definition of the class Stack
   
   class MyThread extends Thread{
      private Stack myStack;
      public MyThread(Stack s){ myStack = s; }
      public void run(){
         myStack.popAndPrintAll();
      }
   }
   
   class TestStack {
      public static void main(String[] args){   
         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);
         MyThread T2 = new MyThread(s2);
         T1.start();
         T2.start();
      }
   }
If you run such a program, you may observe that the printing of the content of s1 and of s2 (executed by the threads T1 and T2 respectively) is interleaved. (This happens if the number of elements on the stacks is large enough, for instance 1000.)

How woud you modify the code so to avoid this interleaving, i.e. in such a way that the content of one stack is all printed before the content of the other stack? Note: the code of TestStack should still create and fill the two stacks in the same way as above, and create and start the two threads one after the other as above.

Question 4

Consider the following implementation of a class Account in Java, representing a bank account
   class Account{
      private int accountNumber;
      private int balance;
      
      public Account(int number, int initialDeposit) { 
         accountNumber = number;
         balance = initialDeposit;
      }
      public int getBalance(){
         return balance;
      }
      public int getAccountNumber(){
         return accountNumber;
      }
      public void depositOrWithdraw(int amount){
         balance = +amount; // if amount is positive it's a deposit
      }                     // otherwise it's a withdrawal
   }
Assume that we want to allow two or more threads to share a same object Account. Say exactly which of the public methods of Account should be synchronized.

Question 5

Define in ML a function
   filter_positive : int list -> int_list
which, given a list of integers, returns a list containing all (and only) the positive elements of the original list. For instance, we should have:
   - filter_positive [];
   val it = [] : int list
   - filter_positive [0,1,~2,3,1];
   val it = [1,3,1] : int list
Note: "~" is the ML unary "minus" operator (i.e. ~2 in ML represents -2)

Question 6

  1. Define in ML a datatype "'a btree" representing the polymorphic type of binary trees in which only the leaves contain information (or type 'a). For instance, we want to represent trees like
           T1             T2
    
           /\             /\
          /  \           /  \
         /\   3        "a"  "b"
        /  \
       1    2
    
  2. Define in ML a function
       fringe : 'a btree -> 'a list
    
    which collects all the nodes of the leaves of a tree into a list, in the order from left to right. For instance, if T1 and T2 are defined as above, then we should have:
       - fringe T1;
       val it = [1,2,3] : int list;
       - fringe T2;
       val it = ["a","b"] : string list;