Question 1:


A) 

 (From Cormen pp 65-66):

 Let k = log_b n,

T(n) = f(n) + a T(n/b) 
     = f(n) + a f(n/b) + a^2 T(n/b^2) 
     = f(n) + a f(n/b) + a^2 f(n/b^2) + a^3 T(n/b^3)
     = f(n) + a f(n/b) + a^2 f (n/b^2)  + ......     + a^k-1  f(n/b^k-1) + a^k T(n/b^k)

Because n/b^k= 1 is the end of the recursion,

    T(n) = f(n) + a f(n/b) + a^2 f (n/b^2)  + ......a^k-1  f(n/b^k-1) + a^k T(1)

As  T(1) = theta(1) and

a^k = a^ log_b n = n ^ log_b a, 

          k-1
T(n) =  SIGMA  ( a^j f(n/b^j) ) + n ^ log_b a  theta(1) 
          j=0

          k-1
     =  SIGMA  ( a^j f(n/b^j) ) + theta (n ^ log_b a)  
          j=0



B) 

  The cost of Divide and Combine is 

          k-1
        SIGMA  ( a^j f(n/b^j) ) 

          j=0

  and the cost of solving all the subproblems at the end of the recursion is:
 
         theta (n ^ log_b a)  



Question 2:

  Make a regular singly-linked list, but with an additional record at the END
of the list.  This additional record will have a "DUMMY" info (which is not
the info of any other record). Delete will copy the element at next(X) into 
the element X. Thus the element originally at next(X) is out of the list.


Delete(P,X)
-----------

      /* COPYING THE NEXT ELEMENT INTO X */
         info(X) = info(next(X))
         next(X) = next(next(X))

      /* IF X IS THE LAST, info(X) WILL NOW BE DUMMY */
      /* AND next(X) CAN POINT TO NIL */
         if (info(X)="DUMMY") then
            next(X) = nil


If we want to explicitly free the unused element, we can do so before 
updating next(X):
        temp = next(X)
        info(X) = info(temp)
        next(X) = next(temp)
        free(temp)


Note that  P is not even needed!
 


Question 3:
- ----------

General Assumptions :

  1) A structure  Tree  defined as follows :

      - key        : integer number.
      - left,right : Pointers to a structure of type Tree  (Tree*)

  2) A structure  List  defined as follows :

      - key        : integer number
      - next       : Pointer to a structure of type List (List*)

  3) We denote the NULL pointer by nil
  4) *XX denote  a pointer to a structure of type XX
  5) X->Y denote the value of field Y in the structure X

Alef:: the function leaves calls leaves1. the function leaves1 has two

arguments: a tree pointer and a list pointer. the list pointer points
to the part of the list of leaves that was generated till now. it is
initially nil. we build the list of leaves backwards from right to
left.


   List* leaves( Tree* t )
   begin
      leaves(t,nil)
   end   


   function leaves2( Tree* t , List* p ) : List*
   var
      listnode : List*

   begin
      if ( t = nil ) then

        return p
      else
        if ( is_leaf(t) ) then
          begin
            listnode       = new( List )
            listnode->key  = t->key
            listnode->next = p
            return p
          end
        else
          return leaves2( t->left , leaves(t->right) )
   end;

   function is_leaf(Tree* t) : Boolean
   begin
     if ( t->left=nil and t->right=nil )
       return true
     else

       return false

Bet.
   In order to check if the leaves of two trees are the same, we generate the
   two lists of leaves using the function of (A). and pass through both lists
   and check the equivalence of each two corresponding nodes.

   // same-leaves( Tree* , Tree* ) --> Boolean
   //
   // return true if t1 and t1 have the same leaves (order and value ).
   //

   function same-leaves( Tree* t1 ,Tree* t2 ) : boolean
   var
     t1_leaves, t2_leaves : Tree*
     tmp1 ,tmp2           : Tree*
     same                 : Boolean;
   begin

     t1_leaves = leaves(t1)
     t2_leaves = leaves(t2)

     tmp1=t1_leaves
     tmp2=t2_leaves

     same = true;

     while ( tmp1<>nil and tmp2<>nil and same=true ) do
       begin
         if ( tmp1->key <> tmp2->key ) then
           same = false
         else
           begin
             tmp1=tmp1->next
             tmp2=tmp2->next
           end

      end;

     if ( tmp1<>nil or tmp2<>nil ) then
       same=false;

     free( t1_leaves )
     free( t2_leaves )
   end


Gimmel: 

   We must define a mechanism that provides the option to get one leaf
   from each tree and then continue the traversal from the place we
   stopped. 
   For this purpose we simulate the recursion process using a stack. Each entry
   in the stack contain a Tree Node.



   function same-leaves( Tree* t1 ,Tree* t2 ) : Boolean
   var
     S1,S2 : stack of Tree*
     leaf1,
     leaf2 : Tree*

   begin

     if ( t1<>nil ) then push( S1, t1 )
     if ( t2<>nil ) then push( S2, t2 )
     same = true

     while ( (not empty(S1)) and (not empty(S1)) and (same=true))
       begin
         leaf1 = search_until_leaf(S1);
         leaf2 = search_until_leaf(S2);


        if ( leaf1->key <> leaf2->key ) then
           same=false;
       end;

     if ( (not empty(S1)) or (not empty(S2)) ) then
       same=false;

     return same;
   end

   
   function search_until_leave(Stack S) : Tree*
   var
     t     : Tree*

   begin
     t = pop(S)


     while ( not is_leaf(t) ) do
       begin
         push(S , t->right)
         t = t->left
       end
   end



Question 4:
Simple AVL tree with pointers to the leftmost anf rightmost leaves.