-------------------------------------------------------------------------- Software Design and Development Winter 1996 COM 1205 Karl Lieberherr --------------------------------------------------------------------------- Final 251 points total Question 1: 8 UNKNOWNs, 4 points each: 32 points Question 2: 17 UNKNOWNs, 7 points each: 119 points Question 3 16 UNKNOWNs, 5 points each: 80 points Question 4 2 UNKNOWNs, 10 points each: 20 points --------------------------------------------------------------------------- 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: =========== 8 UNKNOWNs, 4 points each: 32 points This question is about coming up with an object-oriented design for a set of sample objects. Consider the following three W-objects: : W ( < b > : B ( < l > : N ( < first > : Y ( ) < rest > : N ( < first > : Z ( ) < rest > : N ( < first > : Y ( ) < rest > : E ( ) ) ) ) ) < e > : E ( ) < x > : Z ( ) ) , : W ( < b > : B ( < l > : E ( ) ) < e > : E ( ) < x > : Y ( ) ) , : W ( < b > : B ( < l > : E ( ) ) < e > : E ( ) < x > : W ( < b > : B ( < l > : N ( < first > : Y ( ) < rest > : N ( < first > : Z ( ) < rest > : N ( < first > : Y ( ) < rest > : E ( ) ) ) ) ) < e > : E ( ) < x > : Z ( ) ) ) You are asked to give a minimal set of C++ class definitions which makes the objects given above legal. Give the corresponding class definitions in the following order and put your answer into the proper UNKNOWN: W UNKNOWN1 B UNKNOWN2 E UNKNOWN3 N UNKNOWN4 Y UNKNOWN5 Z UNKNOWN6 L UNKNOWN7 L is an abstract class (choose any class name) X UNKNOWN8 X is an abstract class (choose any class name) Use the following format for describing your C++ classes: struct Class1 : public Class2 { Class2* i; Class2* j; Class2* k; }; If you would like to write less, you may also give the answer in class dictionary notation. Use also the above order for the classes. In other words: you have a choice of using C++ notation or class dictionary notation to answer the question. Question 2: =========== 16 UNKNOWNs, 7 points each: 112 points This question is about design recovery. What is the object-oriented design behind the C++ member functions below? Deduce as much as possible about the underlying class structure by writing the class definitions as a class dictionary or as C++ class definitions. Make the class definitions as short as possible. Give the class definitions in the following order in the unknowns: Graph UNKNOWN1 Vertex UNKNOWN2 VertexName UNKNOWN3 SomeAbstractClass UNKNOWN4 AVertex UNKNOWN5 BVertex UNKNOWN6 AuxVertex UNKNOWN7 Marked UNKNOWN8 Unmarked UNKNOWN9 AuxVertex_List UNKNOWN10 Vertex_List UNKNOWN11 Help: Vertex is a superclass of AVertex and BVertex. VertexName has one part called n which is a DemIdent. The member functions have the following names: link_graph link_vertex find (find_) dft There is a group of member functions associated with each name. Express these groups of collaborating member functions as succinctly as possible in terms of the class structure you came up with. Give your answer either using the propagation directive notation or use English, for example: take all paths from A to B, bypassing ... Put your traversal specifications and the wrappers (i.e., the propagation patterns) into the following unknowns: link_graph UNKNOWN12 link_vertex UNKNOWN13 find (find_) UNKNOWN14 init UNKNOWN15 dft UNKNOWN16 Show the uses of the Visitor design pattern below. What are the traversals? What are the visitors? Put your answer into UNKNOWN17. void Graph::link_graph( Graph* g ) { this->get_vertices()->link_graph( g ); } void Vertex::link_graph( Graph* g ) { cout << " linking " << this->get_n() << " now " << endl; this -> link_vertex(g); } void Vertex_List::link_graph( Graph* g ) { Vertex_list_iterator next_Vertex(*this); Vertex* each_Vertex; while ( each_Vertex = next_Vertex() ) { each_Vertex->link_graph( g ); } } void Vertex::link_vertex( Graph* g ) { } void AVertex::link_vertex( Graph* g ) { if ( this->get_x_neighbors() != NULL ) { this->get_x_neighbors()->link_vertex( g ); } if ( this->get_y_neighbors() != NULL ) { this->get_y_neighbors()->link_vertex( g ); } } void BVertex::link_vertex( Graph* g ) { if ( this->get_x_neighbors() != NULL ) { this->get_x_neighbors()->link_vertex( g ); } if ( this->get_y_neighbors() != NULL ) { this->get_y_neighbors()->link_vertex( g ); } } void AuxVertex::link_vertex( Graph* g ) { this -> set_vertex(g->find(this->get_vertex()->get_n())); } void AuxVertex_List::link_vertex( Graph* g ) { AuxVertex_list_iterator next_AuxVertex(*this); AuxVertex* each_AuxVertex; while ( each_AuxVertex = next_AuxVertex() ) { each_AuxVertex->link_vertex( g ); } } Vertex* Graph::find( VertexName* vn ) { Vertex* return_val; this->find_( return_val, vn ); return return_val; } void Graph::find_( Vertex* & return_val, VertexName* vn ) { this->get_vertices()->find_( return_val, vn ); } void Vertex::find_( Vertex* & return_val, VertexName* vn ) { if (this->get_n()->g_equal(vn)) { cout << " found " << this -> get_n() << endl; return_val = this;}; } void Vertex_List::find_( Vertex* & return_val, VertexName* vn ) { Vertex_list_iterator next_Vertex(*this); Vertex* each_Vertex; while ( each_Vertex = next_Vertex() ) { each_Vertex->find_( return_val, vn ); } } void Graph::init( ) { this->get_vertices()->init( ); } void Vertex::init( ) { this -> set_marked(new Unmarked()); } void Vertex_List::init( ) { Vertex_list_iterator next_Vertex(*this); Vertex* each_Vertex; while ( each_Vertex = next_Vertex() ) { each_Vertex->init( ); } } void Graph::dft( ) { this->init(); this->get_vertices()->dft( ); } void Vertex::dft( ) { if (this->is_unmarked()){ set_marked(new Marked()); cout << " Vertex " << this->get_n() << " visited " << endl; }; } void AVertex::dft( ) { if (this->is_unmarked()){ set_marked(new Marked()); cout << " Vertex " << this->get_n() << " visited " << endl; if ( this->get_x_neighbors() != NULL ) { this->get_x_neighbors()->dft( ); } if ( this->get_y_neighbors() != NULL ) { this->get_y_neighbors()->dft( ); } }; } void BVertex::dft( ) { if (this->is_unmarked()){ set_marked(new Marked()); cout << " Vertex " << this->get_n() << " visited " << endl; if ( this->get_x_neighbors() != NULL ) { this->get_x_neighbors()->dft( ); } if ( this->get_y_neighbors() != NULL ) { this->get_y_neighbors()->dft( ); } }; } void AuxVertex::dft( ) { this->get_vertex()->dft( ); } void Vertex_List::dft( ) { Vertex_list_iterator next_Vertex(*this); Vertex* each_Vertex; while ( each_Vertex = next_Vertex() ) { each_Vertex->dft( ); } } void AuxVertex_List::dft( ) { AuxVertex_list_iterator next_AuxVertex(*this); AuxVertex* each_AuxVertex; while ( each_AuxVertex = next_AuxVertex() ) { each_AuxVertex->dft( ); } } From: /proj/lieber/envs/dft/extended/ Question 3 ========== 16 UNKNOWNs, 5 points each: 80 points This question is about doing an object-oriented design for a language design problem. At your next COOP job you are asked to do an object-oriented design and a language design for Directive-objects outlined by example below: 'from' A 'include' -> x,X 'and' =>C 'and' ->y,Y 'at' D 'exclude' => Z 'and' -> q,Q 'at' E 'to' {X Y Z} 'from' A 'to' {X Y} 'from' A 'to' {*} 'from' E 'include' -> x,* 'and' =>C 'and' ->y,Y 'at' D 'include' -> j,J 'and' ->c,* 'and' ->y,* 'and' ->h,* 'at' D 'exclude' => Z 'and' -> q,Q 'at' E 'include' -> j,J 'and' ->c,C 'and' ->y,Y 'and' ->h,H 'at' D 'exclude' => * 'and' -> q,Q 'at' * 'to' {Y U Z} In case you are curious what those sentences mean: They are traversal specifications to be used in conjunction with the Visitor pattern. Those traversal specifications are a little different than the ones used in the course. The second and the third of the four directive objects have the following structure: : Directive ( < from > : Vertex ( < n > : DemIdent "A" ) < conditions > : Condition_List { } < to > : GenVertex_CList { : Vertex ( < n > : DemIdent "X" ) , : Vertex ( < n > : DemIdent "Y" ) } ) : Directive ( < from > : Vertex ( < n > : DemIdent "A" ) < conditions > : Condition_List { } < to > : GenVertex_CList { : WildCard ( ) } ) Design a class dictionary which is consistent with the above objects in sentence and object graph form. Define the classes in the following order and put them into the appropriate knowns: Directive = UNKNOWN1 GenVertex : UNKNOWN2 Vertex = UNKNOWN3 WildCard = UNKNOWN4 Condition : UNKNOWN5 Inclusion = UNKNOWN6 Exclusion = UNKNOWN7 EdgeTail : UNKNOWN8 Constr = UNKNOWN9 Alternation = UNKNOWN10 LabelName = UNKNOWN11 Directive_List ~ UNKNOWN12 Condition_List ~ UNKNOWN13 GenVertex_CList ~ UNKNOWN14 EdgeTail_AList ~ UNKNOWN15 Also do a behavioral object-oriented design for the following problem: Given a Directive-object, print all Vertex-objects which are contained in the conditions part of the directive. Write your answer as a propagation pattern and put it into UNKNOWN16. Question 4 ========== 2 UNKNOWNs, 10 points each: 20 points Answer the following questions assuming you use the Isthmus tool. Explain how to call a C++ function in Tcl. Put your answer into UNKNOWN1. Explain how to call a Tcl procedure in C++. Put your answer into UNKNOWN2.