-------------------------------------------------------------------------- Software Design and Development Fall 1995 COM 1205 --------------------------------------------------------------------------- Final QUESTION 1: 14 UNKNOWNs, 7 points each 98 QUESTION 2: 2 UNKNOWNs, 10 points each 20 QUESTION 3: 5 UNKNOWNs, 5 points each 25 QUESTION 4: 5 UNKNOWNs, 4 points each 20 163 points total --------------------------------------------------------------------------- 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: =========== 14 UNKNOWNs, 7 points each Consider the following class dictionary, propagation patterns and main program. The adaptive program simulates one bus route with several buses. The program prints the state of the bus route every (simulated) minute. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ begin example EXAMPLE: By running the program with run demeter-input 3 for the demeter-input object given below, we get a simulation of the bus route for 3 minutes, also shown below. // Here is a sample BusRoute object: BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( Person1 destination: Stop1 ) Stop1 at: 2000 ft with waiting list : ( Person10 destination: Stop0 ) Stop2 at: 3500 ft with waiting list : ( Person5 destination: Stop0 Person10 destination: Stop1 ) ) with assigned busses : ( Bus1 at: 0 ft currently at stop : Stop0 capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : () ) OUTPUT FROM THE SIMULATION: Initial state of the input bus route : BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( Person1 destination: Stop1 ) Stop1 at: 2000 ft with waiting list : ( Person10 destination: Stop0 ) Stop2 at: 3500 ft with waiting list : ( Person5 destination: Stop0 Person10 destination: Stop1 ) ) with assigned busses : ( Bus1 at: 0 ft currently at stop : Stop0 capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ( ) ) Next state (after 1 minutes) : BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( ) Stop1 at: 2000 ft with waiting list : ( Person10 destination: Stop0 ) Stop2 at: 3500 ft with waiting list : ( Person5 destination: Stop0 Person10 destination: Stop1 ) ) with assigned busses : ( Bus1 at: 0 ft capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ( Person1 destination: Stop1 ) ) Next state (after 2 minutes) : BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( ) Stop1 at: 2000 ft with waiting list : ( Person10 destination: Stop0 ) Stop2 at: 3500 ft with waiting list : ( Person5 destination: Stop0 Person10 destination: Stop1 ) ) with assigned busses : ( Bus1 at: 700 ft capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ( Person1 destination: Stop1 ) ) Final state of the input bus route (after 3 minutes) : BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( ) Stop1 at: 2000 ft with waiting list : ( Person10 destination: Stop0 ) Stop2 at: 3500 ft with waiting list : ( Person5 destination: Stop0 Person10 destination: Stop1 ) ) with assigned busses : ( Bus1 at: 1400 ft capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ( Person1 destination: Stop1 ) ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ begin example Find the UNKNOWNs so that the program fits the documentation and has the beavior as shown by the above example. // ============================================================ // BusRoute.cd : Class dictionary for bus routes. // Written by Ali Ozmez for the COM3360 project. // Last update on Tue Nov 28 17:11:12 1995. // ============================================================ BusRoute = "BusRoute:" RouteName "total" "route" "length" ":" RouteLen "consisting" "of" "bus" "stops" ":" List(BusStop) "with" "assigned" "busses" ":" List(Bus). BusStop = StopId "at:" RouteLoc // clockwise distance from origin "with" "waiting" "list" ":" List(Person). Bus = BusId "at:" RouteLoc // clockwise distance from origin [ "currently" "at" "stop" ":" StopId] "capacity:" BusCapac "speed:" BusSpeed "carrying" "passenger(s)" ":" List(Person). Person = PersonId "destination:" StopId. // id of the dest. stop List(S) ~ "(" { S } ")". RouteName = DemString. RouteLen = DemNumber "ft". RouteLoc = DemNumber "ft". BusCapac = DemNumber "passengers". BusSpeed = DemNumber "ft/min". StopId = DemIdent. BusId = DemIdent. PersonId = DemIdent. Create a numbered cross reference list for a class dictionary. ------------------------------------------------------------- Class Dictionary ------------------------------------------------------------- 1 2 // ============================================================ 3 // BusRoute.cd : Class dictionary for bus routes. 4 // Written by Ali Ozmez for the COM3360 project. 5 // Last update on Tue Nov 28 17:11:12 1995. 6 // ============================================================ 7 8 BusRoute = 9 "BusRoute:" RouteName 10 "total" "route" "length" ":" RouteLen 11 "consisting" "of" "bus" "stops" ":" List(BusStop) 12 "with" "assigned" "busses" ":" List(Bus). 13 14 BusStop = 15 StopId 16 "at:" RouteLoc // clockwise dist. from origin 17 "with" "waiting" "list" ":" List(Person). 18 19 Bus = 20 BusId 21 "at:" RouteLoc // clockwise dist. from origin 22 [ "currently" "at" "stop" ":" StopId] 23 "capacity:" BusCapac 24 "speed:" BusSpeed 25 "carrying" "passenger(s)" ":" List(Person). 26 27 Person = 28 PersonId 29 "destination:" StopId. // id of the dest. stop 30 31 List(S) ~ "(" { S } ")". 32 33 RouteName = DemString. 34 RouteLen = DemNumber "ft". 35 RouteLoc = DemNumber "ft". 36 BusCapac = DemNumber "passengers". 37 BusSpeed = DemNumber "ft/min". 38 StopId = DemIdent. 39 BusId = DemIdent. 40 PersonId = DemIdent. ------------------------------------------------------------- Alphabetically Sorted Cross Reference List ------------------------------------------------------------- Bus :19 12 BusCapac :36 23 BusId :39 20 BusRoute :8 BusSpeed :37 24 BusStop :14 11 List :31 11 12 17 25 Person :27 17 25 PersonId :40 28 RouteLen :34 10 RouteLoc :35 16 21 RouteName :33 9 StopId :38 15 22 29 // ============================================================ // simulate.pp : Propagation patterns for bus route simulation. // Written by Ali Ozmez for COM3360 project. // Last update on Tue Nov 28 21:51:23 1995. // ============================================================ // Following PP does a unit time long (1 min) simulation. *operation* void simulate() *traverse* *from* BusRoute *to* Bus *carry* *in* BusRoute *busRoute = (@ this @) *along* *from* BusRoute *to* Bus *wrapper* Bus (@ StopId *stopId = this->get_currentStop(); if (stopId != NULL) { // waiting at a stop this->drop_passengers(stopId); this->load_passengers( busRoute->find_stop(stopId) ); this->set_currentStop(NULL); // prepare to move } else { // moving along the route int prevPos = this->get_loc(); int nextPos = (prevPos + this->get_spd()) % busRoute->get_len(); BusStop *stop = busRoute->any_stop_around(prevPos, nextPos); if (stop == NULL) this->proceed_to(nextPos); else if (this->have_stop_request( stop->get_id() )) { this->proceed_to( stop->get_loc() ); this->set_currentStop( stop->get_id() ); // stop here } else { int have_room = this->get_cap() - this->count_passengers(); if ( have_room && stop->anybody_waiting() ) { this->proceed_to( stop->get_loc() ); this->set_currentStop( stop->get_id() ); // stop here } else this->proceed_to(nextPos); } } @) // PP to drop the passengers who want to get off at the current stop. // The propagation pattern 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 propagation pattern. *operation* void drop_passengers(StopId *iStopId) *traverse* UNKNOWN1 *carry* *in* Person_List *newPasList = (@ new Person_List() @) *along* UNKNOWN2 *wrapper* UNKNOWN3 (@ UNKNOWN4 @) *wrapper* Bus *suffix* (@ UNKNOWN5 @) // PP to load some (or all) of the people waiting at the stop. *operation* void load_passengers(BusStop *iStop) *traverse* *from* Bus *to* Person_List *carry* *in* Person_List *newPasList *along* *from* Bus *to* Person_List *wrapper* Bus (@ int allowance = this->get_cap() - this->count_passengers(); newPasList = iStop->give_passengers(allowance); @) *wrapper* Person_List (@ this->concatenate(newPasList); @) // PP to find the stop from its id. // Finds for a given BusRoute-object and StopId-object, // the BusStop-object with the given StopId-object. *operation* BusStop *find_stop(StopId *iStopId) *init* (@ NULL @) *traverse* UNKNOWN6 *wrapper* UNKNOWN7 (@ UNKNOWN8 @) *wrapper* ~> BusStop_List, BusStop (@ if (return_val) return; @) // PP to count the passengers travelling on a bus. *operation* int count_passengers() *traverse* *from* Bus *to* Person_List *wrapper* Person_List (@ return_val = this->list_length(); @) // PP to transfer people from a stop (to a bus). // The following pp 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. *operation* Person_List *give_passengers(int allowance) *init* (@ new Person_List() @) *traverse* *from* UNKNOWN9 *carry* *in* Person_List *newWaitList = (@ new Person_List() @) *along* UNKNOWN10 *wrapper* UNKNOWN11 (@ if (return_val->list_length() < allowance) return_val->append(this); else newWaitList->append(this); @) *wrapper* BusStop *suffix* (@ this->set_waitingList(newWaitList); @) // PP to search for a stop in the given interval of route. *operation* BusStop *any_stop_around(int prevPos, int nextPos) *init* (@ NULL @) *traverse* *from* BusRoute *to* BusStop *wrapper* BusStop (@ int stopLoc = this->get_loc(); if (prevPos < nextPos) { if ((stopLoc > prevPos) && (stopLoc <= nextPos)) return_val = this; } else if ((stopLoc > prevPos) || (stopLoc <= nextPos)) return_val = this; @) *wrapper* ~> BusStop_List, BusStop (@ if (return_val) return; @) // PP to move the bus to its new position. *operation* void proceed_to(int newPos) *traverse* *from* Bus *to* RouteLoc *wrapper* RouteLoc (@ UNKNOWN12 @) // PP to see if there is any passengers who wants to get off at // the specified stop. *operation* int have_stop_request(StopId *iStopId) *init* (@ 0 @) *traverse* *from* Bus *to* Person *wrapper* Person (@ if UNKNOWN13 return_val = 1; @) *wrapper* ~> Person_List, Person (@ if (return_val) return; @) // PP to see if anybody waiting at the specified stop. *operation* int anybody_waiting() *init* (@ 0 @) *traverse* *from* BusStop *to* Person_List *wrapper* Person_List (@ UNKNOWN14 = this->empty(); @) // PP to get the get the length of a BusRoute object as an int. *operation* int get_len() *traverse* *from* BusRoute *to* RouteLen *wrapper* RouteLen (@ return_val = this->get_v()->get_val(); @) // PP to get the get the position of a Bus or BusStop object as an int. *operation* int get_loc() *traverse* *from* {Bus, BusStop} *to* RouteLoc *wrapper* RouteLoc (@ return_val = this->get_v()->get_val(); @) // PP to get the get the capacity of a Bus object as an int. *operation* int get_cap() *traverse* *from* Bus *to* BusCapac *wrapper* BusCapac (@ return_val = this->get_v()->get_val(); @) // PP to get the get the speed of a Bus object as an int. *operation* int get_spd() *traverse* *from* Bus *to* BusSpeed *wrapper* BusSpeed (@ return_val = this->get_v()->get_val(); @) //----------------------------------------------------------------- // main.C : Main function for bus route simulation program. // Written by Ali Ozmez for COM3360 project. // Last update on Tue Nov 28 17:11:23 1995. //----------------------------------------------------------------- #include "proj.h" int main( int argc, char* argv[], char* envp[] ) { //---------------------------------------- // Parsing an object //---------------------------------------- // specify file to parse in const int MAXPATH = 256; char Dem_input[MAXPATH]; // Input file is first argument if( argc >= 2 ) strcpy( Dem_input, argv[1] ); else { strcpy( Dem_input, "demeter-input" ); // default input } // parse it in cout << "Parsing in object in: " << Dem_input << "." << endl; BusRoute* iBusRoute = new BusRoute(); if ( ( BusRoute* ) iBusRoute -> g_parse( Dem_input ) == NULL ) { cerr << "Parser error." << endl; exit(1); } cout << endl; //---------------------------------------- // Your own code follows after this //---------------------------------------- int i, stime; // Simulation time is the second argument stime = (argc >= 3) ? atoi(argv[2]) : 30; // Display the initial state of the bus route cout << "Initial state of the input bus route : \n\n"; iBusRoute->g_print(); // Do the simulation here for (i=1; i < stime; i++) { cout << "\n\nNext state (after " << i << " minutes) : \n\n"; iBusRoute->simulate(); iBusRoute->g_print(); } // Display the final state of the bus route cout << "\n\nFinal state of the input bus route (after "; cout << stime << " minutes) : \n\n"; iBusRoute->simulate(); iBusRoute->g_print(); cout << "\n\n*** FINISHED ***" << endl; return ( 0 ); } Question 2: ============================================================== 2 UNKNOWNs, 10 points per UNKNOWN. Consider the class dictionary from question 1. It only provides for one bus route. Change the class dictionary so that it describes a bus system consisting of several bus routes. Specifically, you class dictionary should accept the following sentence describing a bus system. Assume that a bus system contains at least one BusRoute-object. (busroutes BusRoute: "Ruggles / Harvard Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( Person1 destination: Stop1)) with assigned busses : ( Bus1 at: 0 ft currently at stop : Stop0 capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ()) ++++ BusRoute: "Alewife / Burlington Square" total route length : 5000 ft consisting of bus stops : ( Stop0 at: 0 ft with waiting list : ( Person1 destination: Stop1)) with assigned busses : ( Bus1 at: 0 ft currently at stop : Stop0 capacity: 5 passengers speed: 700 ft/min carrying passenger(s) : ()) ) Find the UNKNOWNs below. Your new class dictionary should have the following form: BusSystem = UNKNOWN1 FourPlusList ~ UNKNOWN2 followed by the class dictionary from question 1. Question 3: ================================================================ 5 UNKNOWNs, 5 points each. Consider the traversal directives below and the corresponding propagation patterns which have been computed for the class dictionary in question 1. Find the UNKNOWNS. Traversal directive: *from* { BusRoute } *to* { Bus } Propagation graph for traversal: BusRoute = UNKNOWN1. UNKNOWN2 UNKNOWN3 = . ================================ Traversal directive: *from* { Bus , BusStop } *to* { RouteLoc } Propagation graph for traversal: BusStop = UNKNOWN4 . Bus = UNKNOWN5 . RouteLoc = . Question 4: ===================================================================== 5 UNKNOWNs, 4 points each Consider the C++ program below which was produced from the simulate propagation pattern from question 1. Find the UNKNOWNs below: void BusRoute::simulate( ) { // variables for carrying in and out UNKNOWN1 // outgoing calls // construction edge prefix wrappers this->get_buses()->simulate( busRoute ); } void Bus::simulate( UNKNOWN2 ) { // prefix class wrappers StopId *stopId = this->get_currentStop(); if (stopId != NULL) { // waiting at a stop this->drop_passengers(stopId); this->load_passengers( busRoute->find_stop(stopId) ); this->set_currentStop(NULL); // prepare to move } else { // moving along the route int prevPos = this->get_loc(); int nextPos = (prevPos + this->get_spd()) % busRoute->get_len(); BusStop *stop = busRoute->any_stop_around(prevPos, nextPos); if (stop == NULL) this->proceed_to(nextPos); else if (this->have_stop_request( stop->get_id() )) { this->proceed_to( stop->get_loc() ); this->set_currentStop( stop->get_id() ); // stop here } else { int have_room = this->get_cap() - this->count_passengers(); if ( have_room && stop->anybody_waiting() ) { this->proceed_to( stop->get_loc() ); this->set_currentStop( stop->get_id() ); // stop here } else this->proceed_to(nextPos); } } } void Bus_List::simulate( UNKNOWN3 ) { // outgoing calls Bus_list_iterator next_Bus(*this); Bus* each_Bus; while ( UNKNOWN4 = UNKNOWN5() ) { each_Bus->simulate( busRoute ); } } --- HAPPY HOLIDAYS From: /course/com1205/hw-f95/project/sample/u/questions/to-post