--------------------------------------------------------------------------
Adaptive Object-Oriented Software Development        Fall 1998
COM 3360
NTU SE-737
---------------------------------------------------------------------------
Final

QUESTION 1:					40
QUESTION 2:					20
QUESTION 3:					20
QUESTION 4:					35
7 UNKNOWNs, 5 points each: 35 points
QUESTION 5:					96
24 UNKNOWNs, 4 points each: 96 points
QUESTION 6:					30

241 points total

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

To make the grading easier, please sort the unknowns in increasing order.

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

Some 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*


 
Question 1:
===========
40 points

This question is about some important concepts covered in class.
Please indicate whether you have taken Analysis of Algorithms already.

Consider the following definitions:
A graph H is a tuple (V,E), where V is the set of nodes 
and E is the set of edges represented as a set of ordered pairs of V.

A graph G is an expansion of a graph S= (V,E), 
if  G contains V and if S contains an edge (u,v) then 
G contains a path from u to v. 

Problem 1.1: (30 points)
Describe an algorithm that checks whether G is an expansion of S. 
What is the running time of your algorithm?
It is not important that you find the fastest algorithm possible
but the running time should be bounded by a polynomial.

Problem 1.2: (10 points)
Give an example of an application of the concept of expansion 
in the context of adaptive programming.


Question 2:
===========
20 points

Consider the following class dictionary that uses multiple inheritance.
Is it possible to transform it into an object-equivalent 
single inheritance class dictionary? 
Classes I through O are concrete.

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

If it is possible, give the single inheritance class dictionary, 
otherwise explain why it is not possible.


Question 3:
===========
20 points

Give a very simple example of a class dictionary that 
is not LL(1) and non-ambiguous.


Question 4:
===========
7 UNKNOWNs, 5 points each: 35 points

Consider the following class dictionary program.cd:

A = B E .
B : C | D .
C = "c" E .
D = "d" .
E = B .

Main = .

TestVisitor = <count> int .

and the behavior file program.beh:


Main {
  (@
  public static void main(String args[]) throws ParseException{
    A theA = A.parse("c c c c c d c c d"); 
    // input sentence is given here
    TestVisitor tv = new TestVisitor();
 
    theA.testTrav(tv);

    if(tv.get_count() == 8) {
      System.out.println("SUCCESS");
    } else {
      System.out.println("FAILURE");
    }
  }
  @)
}

A {
  traversal testTrav(TestVisitor v) {
    {
       A -> B
       B -> C
       C -> E
       E -> B
    } ;
    // source: A target: E;
  }
}

E {
  void p1() to * (PrintVisitor);
}

TestVisitor {
  init (@ count = 0; @)
  before E 
    (@ count += 1; host.p1(); 
      System.out.println(" E-object printed "); @)
}

Find the UNKNOWNs in the following output:

Demeter/Java version 0.7.3
Reading project file program.prj...
Running the test...

UNKNOWN1 d E-object printed 
UNKNOWN2 d E-object printed 
UNKNOWN3 d E-object printed 
UNKNOWN4 d E-object printed 
d E-object printed 
UNKNOWN5 d E-object printed 
UNKNOWN6 d E-object printed 
d E-object printed 
SUCCESS

The strategy
    {
       A -> B
       B -> C
       C -> E
       E -> B
    } ;
is not minimal for the particular class graph. Find a minimal
strategy so that the program produces identical output
for the given class graph.
Put the minimal strategy into UNKNOWN7?


Question 5:
========================================================================
22 UNKNOWNs, 4 points each: 88 points

The task is to find the 22 unknowns in the program below.
You are given a complete class dictionary and an input/output
example to show what the program does.

Consider the class dictionary:

BusRoute =
	"BusRoute:" <name> RouteName
	"total" "route" "length" ":" <totalLength> RouteLen
	"consisting" "of" "bus" "stops" ":" <busStops> BusStop_List
	"with" "assigned" "busses" ":" <buses> Bus_List.
BusStop	=
	<id> StopId
	"at:" <location> RouteLoc  // clockwise dist. from origin
	"with" "waiting" "list" ":" <waitingList>Person_List.

Bus : NaturalGasBus | GasolineBus | DieselBus
*common* 
	<id> BusId
	"at:" <position> RouteLoc  // clockwise dist. from origin
	[ "currently" "at" "stop" ":"  <currentStop>  StopId]
	"driver:"<drivername>DriverName
	"capacity:" <capacity> BusCapac
	"speed:" <speed> BusSpeed
	"carrying" "passenger(s)" ":" <passengers> Person_List.
NaturalGasBus = "*N*".
GasolineBus="*G*".
DieselBus="*D*".
Person =
	<id> PersonId
	"destination:" <destination> StopId.   // id of the dest. stop

BusStop_List  ~ "(" { BusStop } ")".
Bus_List ~ "(" { Bus } ")".
Person_List ~ "(" { Person } ")".


RouteName = <v> String.
DriverName= <v> String.
RouteLen  = <v> Integer "ft".
RouteLoc  = <v> Integer "ft".
BusCapac  = <v> Integer "passengers".
BusSpeed  = <v> Integer "ft/min".
StopId    = <v> Ident.
BusId     = <v> Ident.
PersonId  = <v> Ident.
Main =.

///////////////////////////////////////////////////////
The following BusRoute-object:

// Here is a sample BusRoute object:

BusRoute: "MIT / Oak Grove"
total route length : 7000 ft
consisting of bus stops : (
  Stop0 at: 0 ft
	with waiting list : (
	  Person1 destination: Stop1
	  Person2 destination: Stop1
	  Person3 destination: Stop2
	  Person4 destination: Stop1
	  Person5 destination: Stop3
	  Person6 destination: Stop2
	)
  Stop1 at: 2500 ft 
	with waiting list : (
	  Person7 destination: Stop0
	  Person8 destination: Stop3
	  Person9 destination:  Stop3
	  Person10 destination: Stop2
	  Person11 destination: Stop2
	)
  Stop2 at: 5000 ft 
	with waiting list : (
	  Person12 destination: Stop3
	  Person13 destination: Stop1
	  Person14 destination: Stop3
	  Person15 destination: Stop1
	  Person16 destination: Stop1
	  Person17 destination: Stop0
	)
 Stop3 at: 6500 ft
	with waiting list : (
	  Person18 destination: Stop2
	  Person19 destination: Stop0
	  Person20 destination: Stop1
	)
)
with assigned busses : (
*G*  Bus1  at: 0 ft
	currently at stop : Stop0
	driver: "Alex Thomson"
        capacity: 7 passengers
	speed: 800 ft/min
	carrying passenger(s) : ()
)
///////////////////////////////////////////////////////////////////
The program below produces the following output for the input above
(I added some line breaks):

Running the test...
Initial state of the input bus route : 

BusRoute:  MIT / Oak Grove total route length:  7000  ft 
consisting of bus stops: 
( Stop0 at:  0  ft 
with waiting list: ( 
Person1 destination:  Stop1  Person2 destination:  Stop1  
Person3 destination:  Stop2  Person4 destination:  Stop1  
Person5 destination:  Stop3  Person6 destination:  Stop2 )
 Stop1 at:  2500  ft 
with waiting list: ( 
Person7 destination:  Stop0  Person8 destination:  Stop3  
Person9 destination:  Stop3  Person10 destination:  Stop2  
Person11 destination:  Stop2 )
 Stop2 at:  5000  ft 
with waiting list: ( 
Person12 destination:  Stop3  Person13 destination:  Stop1  
Person14 destination:  Stop3  Person15 destination:  Stop1  
Person16 destination:  Stop1  Person17 destination:  Stop0 )
 Stop3 at:  6500  ft 
with waiting list: ( 
Person18 destination:  Stop2  Person19 destination:  Stop0  
Person20 destination:  Stop1 )
)
with assigned busses: ( 
Bus1 at:  0  ft currently at stop:  Stop0 
Driver:  Alex Thomson capacity:  7  passengers 
speed:  800  ft/min carrying passenger(s): ()
)

Next state (after 1 minutes) : 


BusRoute:  MIT / Oak Grove total route length:  7000  ft 
consisting of bus stops: 
( Stop0 at:  0  ft 
with waiting list: ()
 Stop1 at:  2500  ft 
with waiting list: ( 
Person7 destination:  Stop0  Person8 destination:  Stop3  
Person9 destination:  Stop3  Person10 destination:  Stop2  
Person11 destination:  Stop2 )
 Stop2 at:  5000  ft 
with waiting list: ( 
Person12 destination:  Stop3  Person13 destination:  Stop1  
Person14 destination:  Stop3  Person15 destination:  Stop1  
Person16 destination:  Stop1  Person17 destination:  Stop0 )
 Stop3 at:  6500  ft 
with waiting list: ( 
Person18 destination:  Stop2  Person19 destination:  Stop0  
Person20 destination:  Stop1 )
)
with assigned busses: ( 
Bus1 at:  0  ft 
Driver:  Alex Thomson capacity:  7  passengers 
speed:  800  ft/min carrying passenger(s): ( 
Person6 destination:  Stop2  Person5 destination:  Stop3  
Person4 destination:  Stop1  Person3 destination:  Stop2  
Person2 destination:  Stop1  Person1 destination:  Stop1 )
)

....

Final state of the input bus route (after 3 minutes) : 

BusRoute:  MIT / Oak Grove total route length:  7000  ft 
consisting of bus stops: 
( Stop0 at:  0  ft 
with waiting list: ()
 Stop1 at:  2500  ft 
with waiting list: ( 
Person7 destination:  Stop0  Person8 destination:  Stop3  
Person9 destination:  Stop3  Person10 destination:  Stop2  
Person11 destination:  Stop2 )
 Stop2 at:  5000  ft 
with waiting list: ( Person12 destination:  Stop3  Person13 
destination:  Stop1  Person14 destination:  Stop3  Person15 
destination:  Stop1  Person16 destination:  Stop1  Person17 
destination:  Stop0 )
 Stop3 at:  6500  ft 
with waiting list: ( Person18 destination:  Stop2  Person19 
destination:  Stop0  Person20 destination:  Stop1 )
)
with assigned busses: ( 
Bus1 at:  1600  ft 
Driver:  Alex Thomson capacity:  7  passengers 
speed:  800  ft/min carrying passenger(s): ( 
Person6 destination:  Stop2  Person5 destination:  Stop3  
Person4 destination:  Stop1  Person3 destination:  Stop2  
Person2 destination:  Stop1  Person1 destination:  Stop1 )
)

*** FINISHED ***
========================= PROGRAM STARTS HERE
Find the UNKNOWNs in the following program:


// NEW CLASS STARTS HERE
Main{
(@
  static public void main(String args[]) throws Exception {
      BusRoute iBusRoute = BusRoute.parse(System.in);
  int i, stime;

  //Simulation time. System simulates this amount of time in minutes.
  stime = 3;

  // Display the initial state of the bus route
  System.out.println("Initial state of the input bus route : \n\n");
  iBusRoute.g_print();

  // Do the simulation here
  for (i=1; i < stime; i++) {
    System.out.println("\n\nNext state (after " + 
      i + " minutes) : \n\n");
    iBusRoute.simulate();
    iBusRoute.g_print();
  }
    
  // Display the final state of the bus route
  System.out.print
    ("\n\nFinal state of the input bus route (after ");
  System.out.println( stime + " minutes) : \n\n");
  iBusRoute.simulate();
  iBusRoute.g_print();

  System.out.println("\n\n*** FINISHED ***" );

  }
@)
}
//---------------------------------------------------------------------
// NEW CLASS STARTS HERE
BusRoute {
//Simulate () function does 1 min. simulation each time.
 void simulate()
 to  Bus

{
     (@ BusRoute busRoute; @)
   before BusRoute  (@ busRoute = host; @)
   before  Bus (@ 
     StopId  stopId = host.get_currentStop();
     if (stopId != null) {
       // waiting at a stop
       host.drop_passengers(stopId);
       host.load_passengers( busRoute.find_stop(stopId) );
       host.set_currentStop(null);   // prepare to move
     }	
     else {
       // moving along the route
       int prevPos = host.get_loc();
       int nextPos = (prevPos + host.get_spd()) % 
	 busRoute.get_len();
       BusStop  stop = busRoute.any_stop_around(prevPos, nextPos);
       if (stop == null)
			host.proceed_to(nextPos);
          else if (host.have_stop_request( stop.get_id() )) 
		   {
		     host.proceed_to( stop.get_loc() );
		     host.set_currentStop( stop.get_id() );   // stop here
		   }
	         else 
		  {
		   int have_room = 
		     host.get_cap() - host.count_passengers(); 
		     if ( (have_room > 0) && stop.anybody_waiting() ) {
		        System.out.println("proceeding to stop at " 
			  + stop.get_loc());
		        host.proceed_to( stop.get_loc() );
		        host.set_currentStop( stop.get_id() );// stop here
		      } 
		       else
		          host.proceed_to(nextPos);
		  }
	}
     @)
}
//-------------------------------------------------------------------
// function to find the stop from given StopId.

// Finds for a given BusRoute-object and StopId-object,
// the BusStop-object with the given StopId-object.

BusStop find_stop(StopId iStopId)
  UNKNOWN1 

{  
  before UNKNOWN2
     (@  
  if (iStopId.g_equal( host.get_id() ))
       return_val = UNKNOWN3;

      @)
}
//----------------------------------------------------------------
// adaptive method  to search for a stop in the given interval of route.
BusStop any_stop_around(int prevPos, int nextPos)
to UNKNOWN4

{
 before UNKNOWN5
    (@ 
      int stopLoc = host.get_loc();
     if (prevPos < nextPos) 
	 {
          if ((stopLoc > prevPos) && 
               (stopLoc <= nextPos))
	  return_val = host;
	  }
       else 
        if ((stopLoc > prevPos) || (stopLoc <= nextPos))
			return_val = host;
     @)
}

//----------------------------------------------
// function to get the length of BusRoute.
int get_len()
to RouteLen
{
before RouteLen
     (@ 
	 return_val = host.get_v().intValue(); @)
}
//------------------------------------------------------------------
//function to print the information about simulation results.
void g_print()
to {*}
{
before -> BusRoute,name,RouteName 
  (@ System.out.print("BusRoute: "); @)	
before -> BusRoute,totalLength,RouteLen
	(@ System.out.print("total route length: "); @)
before -> BusRoute,busStops,BusStop_List
	(@ System.out.print("\nconsisting of bus stops: \n"); @)
before -> BusRoute,buses,Bus_List
	(@ System.out.print("\nwith assigned busses: "); @)
before -> BusStop,location,RouteLoc (@ System.out.print("at: "); @)
before -> BusStop,waitingList,Person_List
	(@ System.out.print("\nwith waiting list: "); @)
before -> Bus,position,RouteLoc (@ System.out.print("at: "); @)
before -> Bus,currentStop,StopId 
  (@ System.out.print("currently at stop: "); @)
before -> Bus,drivername,DriverName (@ System.out.print("Driver: ");@)
before -> Bus,capacity,BusCapac (@ System.out.print("capacity: "); @)
before -> Bus,speed,BusSpeed (@ System.out.print("speed: "); @)
before -> Bus,passengers,Person_List 
        (@ System.out.print("carrying passenger(s): "); @)
before -> Person,destination,StopId 
  (@ System.out.print("destination: "); @)
before BusStop_List  (@ System.out.print("("); @)
after BusStop_List (@ System.out.print(")"); @)
before Bus_List (@ System.out.print("("); @)
after Bus_List (@ System.out.print(")"); @)
before Person_List (@ System.out.print("("); @)
after Person_List (@ System.out.print(")\n"); @)
before RouteName (@ System.out.print(" " + host.get_v() + " "); @) 
before RouteLen  (@ System.out.print(" " + host.get_v() + " "); @)
after RouteLen  (@ System.out.print(" ft "); @) 

before RouteLoc  (@ System.out.print(" " + host.get_v() + " "); @)
after RouteLoc  (@ System.out.print(" ft "); @)

before BusCapac  (@ System.out.print(" " + host.get_v() + " "); @)
after BusCapac  (@ System.out.print(" passengers "); @) 

before BusSpeed  (@ System.out.print(" " + host.get_v() + " "); @)
after BusSpeed  (@ System.out.print(" ft/min "); @) 
before DriverName (@ System.out.print(" "+ host.get_v() + " "); @)
before StopId    (@ System.out.print(" " + host.get_v() + " "); @)
before BusId     (@ System.out.print(" " + host.get_v() + " "); @)
before PersonId  (@ System.out.print(" " + host.get_v() + " "); @)
}
}
//----------------------------------------------------------------
// NEW CLASS STARTS HERE
// Bus 
Bus {
//function to drop the  passengers who want to get off at this BusStop
// The adaptive method updates the Bus-object with the new passenger
// list. All persons who have arrived at the destination are
// removed from the bus. The destination stop is an argument to
// the adaptive method.
void drop_passengers(StopId iStopId)
 UNKNOWN6

{
  (@ Person_List newPasList = new Person_List(); @)
  
   before UNKNOWN7
   (@
      if (!iStopId.g_equal( host.get_destination() )) 
       UNKNOWN8.append(host);
   @)
   after  UNKNOWN9
     (@ 
	 UNKNOWN10.set_passengers(newPasList); 
     @)
}
//----------------------------------------------------------------
// function to load the waiting people at the stop
void load_passengers(BusStop iStop)
UNKNOWN11
{
 (@ Person_List newPasList = new Person_List(); @)
 
 before UNKNOWN12
    (@ 
     int allowance = host.get_cap() - host.count_passengers();
    newPasList = iStop.give_passengers(allowance);   @)
 before  UNKNOWN13
      (@ host.concatenate(newPasList);   @)
}

//----------------------------------------------------------
//function to count the passengers on the bus.
int count_passengers()
 to Person_List
{
before  Person_List
    (@ 
	return_val = host.list_length();
    @)
}
//---------------------------------------------------------
//function to move the bus to its next position.
void proceed_to(int newPos)
UNKNOWN14	
{
before RouteLoc
    (@ 
	host.set_v(new Integer(newPos)); @)
}
//---------------------------------------------------------------------
// function to find out if there is any passenger who wants to get off
boolean have_stop_request(StopId iStopId)
to UNKNOWN15
{ (@ Integer ret = new Integer(0); @)
 before UNKNOWN16
    (@
        if (iStopId.g_equal( host.get_destination() ))
            ret = new Integer(1);
  @)  
 after UNKNOWN17 (@  return_val=(ret.intValue()>0); @)	
  }
//---------------------------------------------------------------------
// function to get the capacity of Bus 
int get_cap()
to UNKWNON
{
before UNKWNON
     (@ 
	 return_val = host.get_v().intValue(); @)
}
//---------------------------------------------------------------------
// function to get the speed of Bus
int get_spd ()
to BusSpeed
 {
before BusSpeed
     (@ 
	 return_val = host.get_v().intValue(); @)
 } 
}
//---------------------------------------------------
// NEW CLASS STARTS HERE
BusStop  {
// The following adaptive method transfers people from a stop to a bus.
// It returns the list of passengers which the stop "gives",
// and it updates the BusStop object to reflect the people
// who have entered the bus.

Person_List give_passengers(int allowance)
to UNKNOWN18
{
 (@ Person_List newWaitList = new Person_List();  @)
 
 before UNKNOWN19 (@  return_val=new Person_List();@)
 before UNKNOWN20
    (@ 
      if (return_val.list_length() < allowance)
       return_val.append(host);
     else
       newWaitList.append(host);
     @)
after  UNKNOWN21 
    (@ 
	host.set_waitingList(newWaitList);  @) 
}
//----------------------------------------------
//function to find out if there is anybody waiting at the stop
boolean anybody_waiting()
to Person_List
{
  (@ Boolean ret = new Boolean(false);  @)
before Person_List
     (@ 
	 ret = new Boolean(! host.empty());
         ret.booleanValue();  @)
}

}
//---------------------------------------------------------------------
// NEW CLASS STARTS HERE
Person_List {
// function to append the given person to Person_List
void append (Person p)
to Person
{
before Person_List
(@ Nonempty_Person_List newlist = new 
	   Nonempty_Person_List( p , host.get_first());
	host.set_first(newlist);
 @)
}
//--------------------------------------------------------------------
// function to concatenate the given Person Lists
void concatenate(Person_List pl)
to Person
{
  before Person_List   (@	
   	   if(host.get_first() == null)
		host.set_first( pl.get_first()); @)
}
//-----------------------------------------------------------------
//function to count # of person in the List, and returns length of List
int list_length()
to Person
{
(@ int i=0 ; @)
 before Person
    (@ 	i++;  @)
after Person_List 
	(@ return_val =i; @)
}
//---------------------------------------------------------------
// function to check the Person_List for emptiness
boolean empty()
to Person_List
{
before Person_List
(@ return_val = (!(host.list_length() > 0)); @)
}
}
//---------------------------------------------------------------------
// NEW CLASS STARTS HERE
StopId
{
 (@
  boolean g_equal(StopId it)
   {  return this.get_v().equals(it.get_v()); }
 @)
}
//----------------------------------------------------------------------

// NEW CLASS STARTS HERE
{Bus, BusStop} {
//--------------------------------------------------------------------
//function to get the location of Bus or BusStop
int get_loc()
to RouteLoc
{
before RouteLoc
     (@ 
	 return_val = UNKNOWN22.get_v().intValue(); @)
}
}

Question 6:
==============================================================
30 points

Consider the class dictionary for the bus simulation problem. 
Assume the class structure is extended as follows:

BusRoute =
	"BusRoute:" <name> RouteName
	"total" "route" "length" ":" <totalLength> RouteLen
	"consisting" "of" "bus" "stops" ":" 
	// CHANGED PART
	// <busStops> BusStop_List
	<villages> List(Village) 
	// END CHANGED PART
	"with" "assigned" "busses" ":" <buses> Bus_List.
// ADDED PART
Village = <busStops> List(BusStop).
BusStop = same as before.

What needs to be adapted in the program of question 5?
Can you make the program more structure-shy so that no
update at all would be needed?


HAPPY HOLIDAYS