Exercise 10        Name _________________ Points       /15

1. (2) Give the C++ function for computing the binomial coefficients C(n,k) for the following definition:
where n>=0, k>=0, and n>=k
C(n,n) = 1
C(n,0)=1
C(n,k)=C(n-1,k-1)+C(n-1,k) for (0<k<n) and n>1
 
 
 

 
 
2. (6)    Give the corresponding Assembly code for function C.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. (6)    The following function produces the result in eAx of 10 and the stack below when invoked by:

Push    20
Push    50
Call     GCD
Draw the stack values when the same GCD function is invoked by:
Push    50
Push    20
Call     GCD
      ___________                    
  Y  |     20    | <- eBp+12          
     |___________|              
  X  |     50    | <- eBp+8       
     |___________|               
     |Return Addr| <- eBp+4      
     |___________|              
     |   eBp     | <- eBp       
     |___________|____________ 
  Y  |     10    | <- eBp+12
     |___________|
  X  |     20    | <- eBp+8                                      
     |___________|
     |Return Addr| <- eBp+4
     |___________|
     |   eBp     | <- eBp       
     |___________|____________ 

      Y   EQU  dWord Ptr [eBp+12]
      X   EQU  dWord Ptr [eBp+8]    ; int GCD(int X, int Y) {
 GCD      Proc  Near
          Push  eBp                        
          Mov   eBp, eSp                    

          Mov   eAx, X
          Mov   eDx, 0
          Div   Y
    
    If:     Cmp  eDx , 0        ; if (X % Y == 0)
            Je   Then           ;    return Y
            Jmp  Else           ;  else return GCD(Y,X % Y);
      Then: Mov  eAx, Y         ; }
            Jmp  EndIf
      Else: 
            Push eDx
            Push Y
            Call GCD

            Add  eSp, 8
    EndIf:
           Pop  eBp
           Ret                            
GCD   Endp
4. (1) Give the recursive call tree of the Fibonacci algorithm for F(6) based upon the tree for F(5) below.