--------------------------------------------------------------------------
Software Design and Development                      Winter 1994 
COM 1205
---------------------------------------------------------------------------
Final

340 points total
QUESTION 1:
12 unknowns, 3 points each	36
QUESTION 2:
13 unknowns, 3 points each	39
QUESTION 3:
17 unknowns, 3 points each	51
QUESTION 4:
24 unknowns, 5 points each	120
QUESTION 5:
24 unknowns, 3 points each	72
QUESTION 6:
11 unknowns, 2 points each      22

---------------------------------------------------------------------------
Open book and open notes. 

To make the grading easier, please put your values for the
unknowns on the enclosed answer sheet.

THE GAME OF REDUNDANCY AND UNKNOWNS
-----------------------------------

Most of the questions in this exam ask you to determine unknowns
of the form UNKNOWN1, UNKNOWN2, ... This makes it easier for you
to answer the questions, since you get extra context information.
Yet you need to master the behavioral objectives of the course to answer
the questions. Guessing an answer is not a successful strategy and
therefore a "game of redundancy" test is more interesting than
a multiple choice test.

The questions have the following pattern: I show you several artifacts
which are related by the theory of object-oriented design and 
programming. Because of the dependencies between the artifacts,
some of the information is redundant and can be recovered from the
context by applying the objectives covered in the course. 
The information which you should discover is marked UNKNOWNx.

If an unknown is not uniquely determined, mark the answer with *CHOICE*.
An unknown may be anything, e.g., a number, an identifier, a character,
two identifiers with a blank between them,
a string etc. If an unknown is the empty string, give NOTHING as answer,
e.g., UNKNOWN = NOTHING. 

Example:

5 + UNKNOWN1 = 8

UNKNOWN1 = 3

---------------

UNKNOWN2 * UNKNOWN3 = 20

UNKNOWN2 = 4 *CHOICE*
UNKNOWN3 = 5 *CHOICE*

At the beginning of a question we give the number of points per unknown.


Question 1:
===========
12 unknowns, 3 points each

(/proj/adaptive/lieber/regression-test/f-final-cube)

Consider the following class dictionary graph CUBE (the graph structure
is that of a 3-dimensional cube):

CubePaths = <paths> List(A).
List(S) ~  { S} .
A =  [B] [D] [E] .
B =  [A] [C] [F] .
C =  [B] [D] [G] .
D =  [A] [C] [H] .
E =  [A] [F] [H] .
F =  [B] [E] [G] .
H =  [D] [E] [G] .
G =  [C] [F] [H] .

Dummy = List(Visited).
Visited : A | B | C | D | E | F | H | G | Comment.
Comment = DemString.

1a) 
===

Find the unknowns in the following propagation directive and 
propagation graph:

Traversal directive:

*from* { CubePaths } *to* { A } 

Propagation graph for traversal:

*source* { CubePaths } 
*target* { A } 
   *paths* 
      UNKNOWN1 = UNKNOWN2 .
      A = UNKNOWN3 .
      B = [ < a > A ] [ < c > C ] [ < f > F ]  . 
      C = [ < b > B ] [ < d > D ] [ < g > G ]  . 
      D = UNKNOWN4 .
      E = [ < a > A ] [ < f > F ] [ < h > H ]  . 
      F = [ < b > B ] [ < e > E ] [ < g > G ]  . 
      H = UNKNOWN5.
      G = [ < c > C ] [ < f > F ] [ < h > H ]  . 
      UNKNOWN6 ~ { A }  .


1b) 
===

Find the unknowns below (use class dictionary graph CUBE):

Traversal directive:

*from* { A } *via* { B } *via* { F } *to* { G } 

The propagation graph of this directive is UNKNOWN7 (give a description
in less than 5 words).

Recall that a propagation directive has information loss
if the propagation graph contains a knowledge path which 
does not satisfy the propagation directive.

Does this propagation have information loss? Answer = UNKNOWN8
If the answer is "yes", give a
path (containing 3 edges UNKNOWN9, UNKNOWN10, UNKNOWN11)
which is in the propagation graph but which does not
satisfy the above directive.


1c) 
===

Find the unknowns in the following propagation directive and
propagation graph:

Traversal directive:

    *from* A
      *bypassing* -> *,e,*,
                  -> *,f,*,
                  -> *,c,*,
                  -> *,d,*
    *to-stop* B



Propagation graph for traversal:

*source* { A } 
*target* { B } 
   *paths* 
      UNKNOWN12

Question 2:
===========

13 unknowns, 3 points each
Consider the class dictionary graph CUBE from the previous question:


CubePaths = <paths> List(A).
List(S) ~ UNKNOWN1 {UNKNOWN2 S} UNKNOWN3.
A = UNKNOWN4 [B] UNKNOWN5 [D] [E] UNKNOWN6.
B = UNKNOWN7 [A] UNKNOWN5 [C] [F] UNKNOWN6.
C = UNKNOWN8 [B] UNKNOWN5 [D] [G] UNKNOWN6.
D = UNKNOWN9 [A] UNKNOWN5 [C] [H] UNKNOWN6.
E = UNKNOWN10 [A] UNKNOWN5 [F] [H] UNKNOWN6.
F = UNKNOWN11 [B] UNKNOWN5 [E] [G] UNKNOWN6.
H = UNKNOWN12 [D] UNKNOWN5 [E] [G] UNKNOWN6.
G = UNKNOWN13 [C] UNKNOWN5 [F] [H] UNKNOWN6.

Dummy = List(Visited).
Visited : A | B | C | D | E | F | H | G | Comment.
Comment = DemString.

Make the class dictionary graph into a class dictionary
by filling in the unknowns
so that the object

: CubePaths ( 
   < paths > : A_List { 
      : A ( 
         < b > : B ( 
            < f > : F ( 
               < g > : G ( ) ) ) ) , 
      : A ( 
         < b > : B ( 
            < c > : C ( 
               < d > : D ( 
                  < h > : H ( 
                     < e > : E ( 
                        < f > : F ( 
                           < g > : G ( ) ) ) ) ) ) ) ) } ) 

has the following representation as a sentence:

( , a b f g . . . . , a b c d h e f g . . . . . . . . ) 

Question 3:
===========

17 unknowns, 3 points each

Find the unknowns in the descriptions below.
Consider the following propagation pattern which is customized by
class dictionary CUBE from the previous question.

*operation* Visited_List* f4()
  *init* (@ new Visited_List() @)
  *traverse*
    *from* CubePaths
    *to* A
  *wrapper* CubePaths
    *suffix* 
      (@ return_val -> 
	   append(UNKNOWN1); @)
  *wrapper* A 
    *prefix* (@ this -> ff4(return_val); @)
*operation* void ff4(Visited_List* visited)
  *traverse*
    *from* A
      *bypassing* -> *,e,*,
                  -> *,f,*,
                  -> *,c,*,
                  -> *,d,*
    *to-stop* B
  *wrapper* *
    *prefix* 
      (@ 
	visited -> append(this);
	cout << " visited " << endl << this << endl; @)

Find the unknowns in the descriptions below:

The above propagation pattern is called for the following input object:

: CubePaths ( 
   < paths > : A_List { 
      : A ( 
         < b > : B ( 
            < UNKNOWN2 > : UNKNOWN3 ( 
               < g > : G ( 
                  < h > : H ( 
                     < UNKNOWN4 > : UNKNOWN5 ( ) ) ) ) ) ) } ) 

which has the following representation as a sentence:

(
,a b UNKNOWN6 g h UNKNOWN7......
)

The trace produced is:

>> Visited_List*  CubePaths::f4()
 >> void CubePaths::f4_(Visited_List* & return_val)
  >> void A_List::f4_(Visited_List* & return_val)
   >> void A::f4_(Visited_List* & return_val)
    >> void A::ff4(Visited_List*  visited)
 visited 
a b UNKNOWN8 g h UNKNOWN9 . . . . . . 
     >> void B::ff4(Visited_List*  visited)
 visited 
b UNKNOWN10 g h UNKNOWN11 . . . . . 
     << void B::ff4(Visited_List*  visited)
    << void A::ff4(Visited_List*  visited)
    >> void B::f4_(Visited_List* & return_val)
     >> void F::f4_(Visited_List* & return_val)
      >> void UNKNOWN12::f4_(Visited_List* & return_val)
       >> void H::f4_(Visited_List* & return_val)
        >> void D::f4_(Visited_List* & return_val)
        << void D::f4_(Visited_List* & return_val)
       << void H::f4_(Visited_List* & return_val)
      << void UNKNOWN13::f4_(Visited_List* & return_val)
     << void F::f4_(Visited_List* & return_val)
    << void B::f4_(Visited_List* & return_val)
   << void A::f4_(Visited_List* & return_val)
  << void A_List::f4_(Visited_List* & return_val)
 << void CubePaths::f4_(Visited_List* & return_val)
<< Visited_List*  CubePaths::f4()

Result returned by f4 (printed with g_print()):

(, a b UNKNOWN14 g h UNKNOWN15 . . . . . . 
, b UNKNOWN16 g h UNKNOWN17 . . . . . , " f4 is done" ) 

Question 4:
===========

24 unknowns, 5 points each.

(/proj/adaptive/lieber/regression-test/f-final-w94)

Consider the following class dictionary BASKET:

Basket = <nested> NestedBasket.
NestedBasket = "nested" "basket" <contents> SeveralThings.
SeveralThings : None | OneOrMore.
None = "()".
OneOrMore = "(" <one> Thing <more> SeveralThings ")".
Thing : NestedBasket | Fruit.
Fruit : Apple | Orange *common* <weight> DemNumber.
Apple = "apple".
Orange = "orange".

Dummy = List(Thing).
List(S) ~ "(" {S} ")".

Find the unknowns below by completing the propagation patterns
based on the informal task description at the beginning of each
propagation pattern:

// Add the weight of all Apple-objects. 
*operation* int all_apples() *init* (@ UNKNOWN1 @)
  *traverse* 
    *from* UNKNOWN2 *to* UNKNOWN3
  *wrapper* UNKNOWN4      
    *prefix* (@ UNKNOWN5 += *(this -> UNKNOWN6()); @)


// Add the weight of all Fruit-objects. 
*operation* int all_fruit() *init* (@ UNKNOWN7 @)
  *traverse* 
    *from* UNKNOWN8 *to* UNKNOWN9
  *wrapper* UNKNOWN10      
    *prefix* (@ UNKNOWN11 += *(UNKNOWN12()); @)

// Produce a list of all Thing-objects.
*operation* Thing_List* all_thing() *init* (@ UNKNOWN13 @)
  *traverse* 
    *from* Basket *to* UNKNOWN14
  *wrapper* UNKNOWN15      
    *prefix* (@ UNKNOWN16 -> UNKNOWN17(this); @)

// Produce a list of all Thing-objects which contain an Apple.
*operation* Thing_List* all_thing_containing_apples(int& apple_count) 
  // is called with variable as first argument which has value 0
    *init* (@ new Thing_List() @)
  *traverse* 
    *from* Basket *via* Thing *to* Apple
  *wrapper* Apple 
    *prefix* 
      (@ apple_count ++ ;@)
  *wrapper* Thing      
    *prefix* (@ int UNKNOWN18 = apple_count; @)
    *suffix* (@ if (UNKNOWN19) UNKNOWN20 -> UNKNOWN21(this); @)

//Add two to the weight of all Orange-objects.
*operation* void oranges_plus_two() 
  *traverse* 
    *from* Basket *to* Orange 
  *wrapper* Orange      
    *prefix* (@ 
      cout << "weight before change " << this-> get_weight() << endl;
      UNKNOWN22;
      cout << "weight after change " << this-> get_weight() << endl;
      @)

Write the above propagation pattern 
*operation* Thing_List* all_thing_containing_apples(int& apple_count) 
without an argument by defining a transportation pattern

*carry* UNKNOWN23
  *along* UNKNOWN24
*wrapper* ...

Question 5:
===========

24 unknowns, 3 points each

We reuse class dictionary BASKET.
Find the unknowns below:

Consider the propagation pattern:

//Print all Thing-objects and for each print its nesting level.
//  (Things in the outermost basket have level 0.)
*operation* void print_nesting_level() 
  *traverse* 
    *from* Basket *to* Thing 
  // transportation pattern
  *carry* *out* int UNKNOWN1 = (@ -1 @)
    *along* *from* Basket *to* Thing
  *wrapper* NestedBasket      
    *prefix* (@ nesting_level = nesting_level +  1 ; @)
    *suffix* (@ nesting_level = nesting_level -  1 ; @)
  *wrapper* Thing
    *prefix* (@ cout << this << endl << " nesting_level " 
      << nesting_level ; @)

For input sentence:

nested basket
  ( UNKNOWN2 (UNKNOWN3 (
  nested UNKNOWN4
    ( UNKNOWN5 (UNKNOWN6 (
    nested basket
      ( UNKNOWN7
      ())
    ( UNKNOWN8 
    ()))))
  ())))

the program produces the following output:

nested basket ( UNKNOWN9 ( UNKNOWN10 ( 
nested UNKNOWN11 ( UNKNOWN12 ( UNKNOWN13 ( 
nested basket ( UNKNOWN14 () ) ( UNKNOWN15 () 
) ) ) ) () ) ) ) 
 nesting_level UNKNOWN16  
apple 10 
 nesting_level UNKNOWN17   
orange 15 
 nesting_level UNKNOWN18    
nested basket ( orange 11 ( apple 14 ( 
nested basket ( apple 8 () ) ( apple 9 () ) ) ) ) 
 nesting_level UNKNOWN19      
orange 11 
 nesting_level UNKNOWN20       
apple 14 
 nesting_level UNKNOWN21        
nested basket ( apple 8 () ) 
 nesting_level UNKNOWN22          
apple 8 
 nesting_level UNKNOWN23           
apple 9 
 nesting_level UNKNOWN24          

Question 6 :
============

11 unknowns, 2 points each.

Consider the propagation pattern and the corresponding C++
code which was obtained for class dictionary BASKET.
Find the unknowns.

//Print all Thing-objects and for each print its nesting level.
//  (Things in the outermost basket have level 0.)
*operation* void print_nesting_level() 
  *traverse* 
    *from* Basket *to* Thing 
  // transportation pattern
  *carry* *out* int nesting_level = (@ -1 @)
    *along* *from* Basket *to* Thing
  *wrapper* NestedBasket      
    *prefix* (@ nesting_level = nesting_level +  1 ; @)
    *suffix* (@ nesting_level = nesting_level -  1 ; @)
  *wrapper* Thing
    *prefix* (@ cout << this << endl << " nesting_level " 
      << nesting_level ; @)


============

//  Basket  = <nested > NestedBasket .
void Basket::print_nesting_level(  )
{
  // variables for carrying in and out
  int nesting_level =  UNKNOWN1 ;
  // outgoing calls
  this->UNKNOWN2()->print_nesting_level( nesting_level  );
}

//  NestedBasket  = "nested" 
//               "basket" 
//               <contents > SeveralThings .
void NestedBasket::print_nesting_level( int&  nesting_level )
{
  // prefix class wrappers
  UNKNOWN3
  nesting_level = nesting_level +  1 ; 
  // outgoing calls
  this->get_contents()->print_nesting_level( nesting_level  );
  // suffix class wrappers
  UNKNOWN4
}

//  SeveralThings  : None   |
//                OneOrMore 
//           *common* .
void SeveralThings::print_nesting_level( int&  nesting_level )
{
}

//  OneOrMore  = "(" 
//            <one > Thing 
//            <more > SeveralThings 
//            ")" .
void OneOrMore::print_nesting_level( int&  nesting_level )
{
  // outgoing calls
  this->UNKNOWN5()->print_nesting_level( nesting_level  );
  this->UNKNOWN6()->print_nesting_level( nesting_level  );
}

//  Thing  : NestedBasket   |
//        Fruit 
//           *common* .
void Thing::UNKNOWN7( int&  UNKNOWN8 )
{
  // prefix class wrappers
 cout << this << UNKNOWN9 << " UNKNOWN10 " 
      << UNKNOWN11 ; 
}

Question 7 :
============

20 points.

Give a one-paragraph definition of "adaptive program".