Spring 2002, CSE 428: Assignment 3


Distributed: Feb 10.
Due: Feb 21 in class.
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with memory management, and with exception handling


Exercise 1 [Points 30]

Consider the following recursive definition of the function "Fibonacci" in C++:
   int fibo(int n) {
       int k1, k2; 
       if (n==1) {
          cout << "returning the result of fibo(1)";
          return 1;
       }
       else if (n==2) {
          cout << "returning the result of fibo(2)";
          return 1;
       }  
       else {
          k1 = fibo(n-1);
          k2 = fibo(n-2);
          return k1 + k2;
       }
   }
Assume that fibo is called from by an instruction of the form
   fibo(5);
Show with a drawing the situation on the stack at the moment in which the string "returning the result of fibo(1)" is printed for the first time. In particular, show the activation records for fibo present on the stack, with the parameters, locals, dynamic links, and their current values, if any.


Exercise 2 [Total points 50]

Consider the following definition of a list in C++:
   class list { //Implementation of a list (only the methods relevant for this exercise)
   private:

      class element {   

      public: 
         int info;
         element* next;
    
         element(int x, element* e) { info = x; next = e; }
      }

      element* first;

   public: 
      list() { first = NULL; }

      void insert(int x) { //Insert x at the beginning of the list
          first = new element(x,first);
      }

   };

  1. [Points 10] Consider now the following procedure definitions in C++:
       void p() {
          list* l;
          l = new list();
          l->insert(1);
          l->insert(2);
          l->insert(3);
       };
    
       void q() {
          p();
          cout << "executing q()";
      };
    
    And a call
       ...
       q();
       ...
    
    Show with a drawing the situation in the memory at the moment in which the string "executing q()" is printed. In particular, show all the memory leaks and dangling pointers (if any).

  2. [Points 10] Same question as before, but with the following definitions for p() and q():
       list* p() {
          list* l;
          l = new list();
          l->insert(1);
          l->insert(2);
          l->insert(3);
          return l;
       };
    
       void q() {
          list * l = p();
          cout << "executing q()";
      };
    

  3. [Points 10] Same question as before, but with the following definitions for p() and q() and l (note that in this definition l is global) :
       list* l;
    
       void p() {
          l = new list();
          l->insert(1);
          l->insert(2);
          l->insert(3);
          delete l;
       };
    
       void q() {
          p();
          cout << "executing q()";
      };
    

  4. [Points 10] Same question as before, but with the following definitions for p() and q():
       void p() {
          list* l;
          l = new list();
          l->insert(1);
          l->insert(2);
          l->insert(3);
          delete l;
       };
    
       void q() {
          p();
          cout << "executing q()";
      };
    

  5. [Points 10] Same question as before, but now assume that p() and q() are defined as in Exercise 2.4, and that the classes element and list are enriched with the following destructor methods:
       ~list() { if (first != NULL) delete first; }
       ~element() { if (next != NULL) delete next; }
    


Exercise 3 [Total points 20]

Consider the following definition in a Pascal-like language.
 
   procedure p
      var x: int;
      procedure q 
         procedure r(x:int) 
            begin 
            x := x-1;
            q
            end; // end body of r
         begin
         x := x-1;
         write(x);
         if x>1 then r(2)          
         end; // end body of q
      begin
      x := 3;
      q
      end // end body of p
Note that q is defined inside p, and r is defined inside q.
  1. [Points 10] Say what are the values printed by a call to p in case of

  2. [Points 10] Illustrate by a drawing the situation on the stack at the moment the second value is printed, in the case of static scope. In particular, represent the locals, the parameters, the static and dynamic links, and their values.