CSE 428, Spring 98: Solution of the Final Exam
===============================================================================

Exercise 1. 
1) The grammar is not ambiguous
2) a) * is left-associative
   b) -> is right-associative
   c) * has precedence wrt to ->
3) The trees are the following (we abbreviate the names of the syntactical 
   categories for graphical reasons)

          T                          T
         /|\                        /|\
        / | \                      / | \
      Tte -> T                  Tte  -> T
       |     |                   |     /|\
      Tfa   Tte                 Tfa   / | \
      /|\    |                   |  Tte -> T
     / | \  Tfa                 Tva  |     |
    (  T  )  |                   |  Tfa   Tte
      /|\   Tva                alpha |     |
     / | \   |                      Tva   Tfa
   Tte -> T gamma                    |     |
    |     |                        beta   Tva
   Tfa   Tte                               |
    |     |                              gamma
   Tva   Tfa
    |     |
  alpha  beta

-------------------------------------------------------------------------------
Exercise 2. We write the function in Pascal:

function GCD(x,y:integer):integer; 
   begin
   while not(x=y) do
      if x > y then x := x-y else y := y-x;
   GCD := x
   end

-------------------------------------------------------------------------------
Exercise 3.

1) The output is 5
2) The output is 7

-------------------------------------------------------------------------------
Exercise 4.

1) ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c

2) ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

3) ('a -> 'b -> 'c -> 'd) -> 'b -> 'a * 'c -> 'd

-------------------------------------------------------------------------------
Exercise 5.

fun insert emptybt x = consbt(x,emptybt,emptybt)
  | insert (consbt(y,lst,rst)) x = if x = y 
                                      then t
                                      else if x < y 
                                              then consbt(y,insert lst x,rst)
                                              else consbt(y,lst,insert x rst)

-------------------------------------------------------------------------------
Exercise 6.

eliminates([],[]).
eliminates([X|L],M) :- member(X,L), eliminates(L,M).
eliminates([X|L],[X|M]) :- not(member(X,L)), eliminates(L,M).

-------------------------------------------------------------------------------
Exercise 7. The following is a possible solution

template<class T> class list : public node<T>{
private: list<T> *next;
public: list(T x){info = x; next = NULL;}
        list(T x, list<T> *n){info = x; next = n;}
        T head(){return info;}
        list<T> *tail(){return next;}
friend class btree<T>;
};

template<class T> class btree : public node<T>{
private: btree<T> *leftsubt;
         btree<T> *rightsubt;
         list<T> *append(list<T> *l1, list<T> *l2){
                   if (l1 == NULL) return l2;
                   return new list<T>(l1->head(),append(l1->tail(),l2));
	 }
public:  btree(T x){ info =x; leftsubt = NULL; rightsubt = NULL; }
         btree(T x,btree<T> *l, btree<T> *r ){ info = x; 
                                               leftsubt = l; rightsubt = r; }
	 list<T> *invisit(){
                   if (this == NULL) return NULL;
                   return append(leftsubt->invisit(),
                                 new list<T>(info, rightsubt->invisit()) );
         }
};