--------------------------------------------------------------------------
Adaptive Object-Oriented Software Development                   Fall 1998
COM 3360/NTU SE737                                              Karl Lieberherr
---------------------------------------------------------------------------

Final

Question 1:

Algorithm 1:

For each edge (u,v) in strategy graph S check 
ExistsPath(G,u,v).
ExistsPath(G,u,v) can be implemented by a depth-first
or breadth-first search.

Bound on running time:
(number of edges in S) * 
(number of edges in G + number of nodes in G)

If n is the number of nodes in G:
O(n^2)*O(n^2+n) = O(n^4)

===
Algorithm 2:

Compute transitive closure T(G): O(n^3).
For each edge (u,v) in strategy graph S check:
is (u,v) in T(G).

Bound on running time:
O(n^3)+O(n)= O(n^3)


Graph expansion applications (mention one):

class graph should be expansion of strategy graph
class graph should be expansion of interface class graph
refined strategy graph should be expansion of strategy graph


Question 2:

The cd is object-equivalent to the following cd:

A: D|J.
B: E|C.
C: M|N.
D: I|K.
E: L|O.


Question 3:

Any LL(k) cd (k>1) will do. 

An example of a not LL(1) and non-ambiguous 
cd is:

X = A.
A:B|C.
B="b" "x".
C="b" "y".



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

UNKNOWN1 = c c c c

UNKNOWN2 = c c c

UNKNOWN3 = c c

UNKNOWN4 = c

UNKNOWN5 = c c

UNKNOWN6 = c

UNKNOWN7 = from A to E = {A -> E}



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

UNKNOWN1 = to BusStop

UNKNOWN2 = BusStop

UNKNOWN3 = host

UNKNOWN4 = to BusStop

UNKNOWN5 = BusStop

UNKNOWN6 = to Person

UNKNOWN7 = Person

UNKNOWN8 = newPasList

UNKNOWN9 = Bus

UNKNOWN10 = host

UNKNOWN11 = to Person_List

UNKNOWN12 = Bus

UNKNOWN13 = Person_List

UNKNOWN14 = to RouteLoc

UNKNOWN15 = Person

UNKNOWN16 = Person

UNKNOWN17 = Bus

	UNKNOWN17a = BusCap
	UNKNOWN17b = BusCap

UNKNOWN18 = Person

UNKNOWN19 = BusStop

UNKNOWN20 = Person

UNKNOWN21 = BusStop

UNKNOWN22 = host


Question 6:

The bus simulation is written in an adaptive style.
Therefore, the program does not require much change.
Where is the path from BusRoute to BusStop mentioned
explicitly? In method g_print()! 

To make g_print() more flexible, we could decouple
it from the class structure written in the program
and tie it to the class dictionary directly:

void g_print() to * (PrintVisitor);

If the syntax for printing is different than the
syntax for parsing, we generate the PrintVisitor
in a separate directory and copy it.

An alternative correct answer is to make some manual
changes to the g_print() method.