Question 1 (Grammars)

1. 1. (4 ^ (2 * 3))   no
   2. 4 ^ 2 * 3   yes
   3. 4 ^ (2)   no
   4. 16   no

2. There are two kinds of ambiguity:
   1. Associativity of *
   2. Precedence between * and ^
   An example of the first is:

   
             Exp            Exp
             /|\            /|\
            / | \          / | \
          Exp * Exp      Exp * Exp
          /|\    |        |    /|\
         / | \   |        |   / | \
       Exp * Exp Num    Num Exp * Exp
        |     |  |        |  |     |
        |     |  |        |  |     |
       Num   Num 4        2 Num   Num
        |     |              |     |
        |     |              |     |
        2     3              3     4
   
   

   An example of the second is:

   
             Exp            Exp
             /|\            /|\
            / | \          / | \
          Exp ^ Num      Exp * Exp
          /|\    |        |    /|\
         / | \   |        |   / | \
       Exp * Exp 4      Num Exp ^ Num
        |     |           |  |     |
        |     |           |  |     |
       Num   Num          2 Num    4
        |     |              |  
        |     |              |   
        2     3              3     
   
   

3.    Exp ::= Exp * A | A
        A ::= A ^ Num | Num | (Exp)
      Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

Question 2 (Parameter passing methods)

1. Call by value   1
2. Call by reference   3
3. Call by value-result   2

Question 3 (Memory management)

Question 4 (Concurrency in Java)

   class Merge extends Thread{
      private Queue q1,q2,q3; //Input queues and output queue

      public Merge(Queue p1, Queue p2, Queue p3){ q1 = p1; q2 = p2; q3 = p3; }

      public void run() {
         for(;;){
            boolAndInt x;
            x = q1.pop();
            if (x.getBool()) q3.insert(x.getInt());
            x = q2.pop();
            if (x.getBool()) q3.insert(x.getInt());
         }
      }
   }

   class Queue {
      private class Element{
         public int info;
         public Element next;
         public Element(int n,Element e){ info = n; next = e; }
      }
      
      private Element first, last;
      
      public Queue() { first = last = null; }
     
      public synchronized boolAndInt pop() { 
         boolAndInt x = new boolAndInt();
         if (first == null) { 
            x.setBool(false); 
            x.setInt(0); 
            return x; 
         }
         else { 
            x.setBool(true);
            x.setInt(first.info);
            first = first.next;
            if (first==null) last = null;
            return x;
         }
      }
    
      public synchronized void insert(int n) { 
         if (first == null) 
            last = first = new Element(n,null);
         else
            last = last.next = new Element(n,null);            
      }
   }
    
   class boolAndInt {
      private int n;
      private boolean b;

      public int getInt() { return n; }
      public boolean getBool() { return b; }

      public void setInt(int k) { n = k; }
      public void setBool(boolean c) { b = c; }
   }

Question 5 (Higher Order in ML)

   fun exists L p = reduce (fn (x,y) => p(x) orelse y) false L;

   fun forall L p = reduce (fn (x,y) => p(x) andalso y) true L;

Question 6 (ML - Data types)

   fun aux [] = []
     | aux (leaf x :: L) = x :: aux L
     | aux (node(t1,x,t2)::L) = x :: aux(L @ [t1,t2]);
   
    fun bftrav t = aux [t]; (* returns the breadth-first traversal of t *)

   fun split [x1,x2] = ([],x1,x2)
     | split (x :: L) = let val (K,x1,x2) = split L
                         in (x::K,x1,x2)
                        end;
   
   fun auxil [] n = []
     | auxil (leaf x :: L) n = leaf n :: auxil L (n+1)
     | auxil (node(t1,x,t2) :: L) n = let val (K,u1,u2) = split (auxil (L @ [t1,t2]) (n+1))
                                       in node(u1,n,u2) :: K
                                      end;

   fun enumerate t = hd (auxil [t] 1);

Question 7 (ML - Data types)

   fun numnodes(t,1) = 1
     | numnodes(leaf x,n) = 0
     | numnodes(node(t1,x,t2),n) = numnodes(t1,n-1) + numnodes(t2,n-1);

Question 8 (Prolog)

   solutions(M,N,X,Y) :- nat(X,M), nat(Y,M), M is X + Y, N is X * Y.

   nat(X,M) :- M >=0, X is M. /* gives all possible integers between 0 and M */
   nat(X,M) :- M > 0, N is M - 1, nat(X,N). 

Question 9 (Prolog)

   flatten([],[]).
   flatten([X|L],[X|K]) :- not(list(X)), flatten(L,K).
   flatten([X|L],K) :- list(X), flatten(X,K1), flatten(L,K2), append(K1,K2,K).

   list([]).
   list([_|_]).

Question 10 (Prolog)

   merge([],L,L).
   merge(L,[],L).
   merge([X|L],[Y|K],[X|M]) :- merge(L,[Y|K],M).
   merge([X|L],[Y|K],[Y|M]) :- merge([X|L],K,M).