Exam 1

Out: 10 September 2002 Due: Tuesday, 15 October 2002, 2:05pm No exams will be accepted after 2:05pm Tuesday

Collaboration Policy (read carefully)

Work alone. You may consult any material you want including the course notes, text and additional sources (including anything you find on the Web). If you use a source other than the course materials or text, you should cite the source in your answer.

You may not discuss this exam with any human, other than the course staff (who will answer clarification questions only). You may not use a Java compiler during this exam, unless you write your own.

Answer all 9 questions (100 points total). There is no time limit on this exam, but you shouldn't spend more than three hours on it.

Specifying Procedures

1. (10) Muddle B. Fuddle wants to add a deleteName method to the StringTable class from Problem Set 3 (http://www.cs.virginia.edu/evans/cs201j-fall2002/problem-sets/ps3/StringTable.spec):

public class StringTable 
{
    // overview: StringTable is a set of <String, double> entries,
    //    where the String values are unique keys.  A typical StringTable
    //    is {<s0: d0>, <s1: d1>, ... }.
    //

    ...
}

Muddle is planning to use a Vector of String, value record pairs to represent his StringTable. He suggests this specification:

public boolean deleteName (String name)
   // REQUIRES: The parameter name is not null.
   // EFFECTS: Goes through the entries in the elements Vector, and removes
   //     the one whose key matches name.
   

Identify at least three important problems with Muddle's specification and explain why each problem is bad.

2. (10) Write a good specification for the deleteName method.

Data Abstractions

For these questions, we will use the WDGraph data abstraction specified below:

public class WDGraph {
   // OVERVIEW: 
   //      A WDGraph is a mutable type that represents a weighted,
   //      directed graph. 
   //
   //      It consists of nodes that are named by Strings, and edges
   //      with non-zero integer weights that connect a pair of nodes.
   //      For any two nodes, a and b, there is at most one edge from
   //      a to b and one edge from b to a.  
   //
   //      A typical Graph is: < nodes, edges >
   //       where
   //         nodes = { n1, n2, ..., nm }
   //       and 
   //         edges = { <from_1, to_1, weight_1>, ..., <from_n, to_n, weight_n> }
   //
   //      For example,
   //	      nodes = { "Charlottesville", "Dulles", "Richmond" }
   //         edges = { <"Charlottesville", "Dulles", 119>,
   //                   <"Dulles", "Charlottesville", 139>,
   //                   <"Charlottesville", "Richmond", 89>,
   //                   <"Richmond", "Dulles", 79> }
   //      could represent the flights and fares between
   //      Charlottesville, Dulles and Richmond (e.g., you can fly from
   //      Richmond to Dulles for $79, but there is no direct flight from
   //      Richmond to Charlottesville.

   // Creator
   public WDGraph () 
      // EFFECTS: Initializes this to a graph
      //      with no nodes or edges: < {}, {} >.

   // Mutators
   public void addNode (String node) throws DuplicateNodeException
      // MODIFIES: this
      // EFFECTS: If node is the name of a node in this.nodes,
      //    throws the DuplicateNode exception.  Otherwise, 
      //    adds a node named name to this:
      //        this_post = < this_pre.nodes U { node }, this_pre.edges >

   public void addEdge (String fnode, String tnode, int weight) 
      thows NoNodeException, DuplicateEdgeException, InvalidWeightException
      // MODIFIES: this
      // EFFECTS: If fnode or tnode is not the name of a node in
      //    this.nodes, throws NoNodeException.  If this already has
      //    an edge between fnode and tnode, throws
      //    DuplicateEdgeException.  If weight is 0, throws
      //    InvalidWeightException.  Otherwise, adds an edge to this
      //    from fnode to tnode with weight:
      //       this_post = < this_pre.nodes, 
      //                     this_pre.edges U { <fnode, tnode, weight> } >
      
   // Observers
   public boolean hasNode (String node)
      // EFFECTS: Returns true iff node is a node in this.

   public boolean hasEdge (String fnode, String tnode)
       throws NoNodeException
      // EFFECTS: If fnode or tnode is not the name of a node in
      //    this.nodes, throws NoNodeException.  Otherwise, returns
      //    true iff there is an edge from fnode to tnode.
}

3. (7) As specified above, is WDGraph likely to be a useful abstraction? If so, explain briefly an application that could use it. If not, explain what methods must be changed or added to make it useful.

4. (8) As specified, WDGraph is a mutable type. Explain what changes would be necessary to make WDGraph an immutable type instead, and identify at least one good reason why we might prefer the immutable version.

5. (15) Suppose we decide to implement WDGraph using this rep:

   // Rep:
   String nodes[]; 
   int edges[][];

   // Abstraction Function:

   // AF (c) = < nodes, edges > where
   //          nodes = { c.nodes[i] | 0 < i <= c.nodes.length }
   //          edges = { < c.nodes[fi], c.nodes[ti], c.edges[fi][ti] > |
   //                    0 < fi <= c.nodes.length,
   //                    0 < ti <= c.nodes.length 
   //                    where c.edges[fi][ti] != 0
   //
   // For example, the representation below would represent the flight
   // graph described in the overview:
   //    
   //     c.nodes = [ "Charlottesville", "Dulles", "Richmond" ]
   //     c.edges = [ [   0, 119, 89],
   //                 [ 139,   0, 0 ],
   //                 [   0,  79, 0 ]
   //

The hasEdge method is implemented as:

   private int lookupNode (String node) throws NoNodeException
      // EFFECTS: If node is a node in this.nodes, returns the
      //    index such that this.nodes[result].equals (node).
      //    Otherwise, throws NoNodeException.

      //   (Note that lookupNode is a private method.  Hence, it is okay that we
      //    have specified it using the concrete representation instead of in
      //    terms of the abstraction.)

   public boolean hasEdge (String fnode, String tnode) 
      throws NoNodeException {
      return (edges[lookupNode (fnode)][lookupNode (tnode)] != 0);
   }

What rep invariant would be necessary to make this implementation correct?

Testing

6. (10) What would be a reasonable set of black box test cases to the addNode method?

7. (10) Suppose we implement addNode as below. What additional glass box test cases (if any) are necessary?

      public void addNode (String node) throws DuplicateNodeException {
         try {
	    lookupNode (node);
	    throw new DuplicateNodeException (node);
	 } catch (NoNodeException e) {
	    String [] oldnodes = nodes;
	    nodes = new String [oldnodes.length + 1];

	    for (int i = 0; i < oldnodes.length; i++) {
	       nodes[i] = oldnodes[i]; 
	    }
	    nodes[oldnodes.length] = node;
	}
     }	

8. (10) What is the serious flaw with our addNode implementation?

Design

9. (20) Due to recent budget cuts at the University, SEAS has decided to replace the student advising office with a computer program. The program will take student course selections as input and either approve or disapprove of the course selections based on whether or not the student has satisfied the necessary prerequisites. (Note: the advising office does many other useful things too, of course. The administration is still working on ways to replace those functions with programs.)

All courses have a department mnemonic (e.g., "CS") and course number (e.g., 201). (As a further cost saving measure, the administration has decided to eliminate deviant courses that have extra modifiers after the number so you don't need to worry about handling courses with names like "CS201J".) Courses also have a name that purports to describes their content (e.g., "Engineering Software").

The program will use a database with information on courses and their prerequisites. A course may have no prerequisites, or may have multiple prerequisites or alternate prerequisites. For example, the prerequisites for "CS201: Engineering Software" are "either CS101: Intro to Computer Science OR CS200: Computer Science from Ada and Euclid to Quantum Computing and the World Wide Web". The prerequisites for "UBW101: Underwater Basketweaving" are "SCU101: Scuba Diving AND (either ART253: Introduction to Basketweaving OR SPD101: Weaving Webs for Poets)".

You've been hired to design the prerequisites checking program. Describe your design using a modular dependency diagram, and a brief description that describes each of the modules in your design. If a module is an abstract data type, write an overview specification of the data type and identify important methods (but you do not need to specify them). Explain a brief strategy for implementing and testing your design.

Your answer should clearly identify the data abstractions in your design, but you need not explain how they will be implemented. Your answer to this question should not require more than two pages (but if you really want to say more than that, its better to use more pages than to write really small).

10. (Optional, no credit) Do you feel your performance on this exam will fairly reflect your understanding of the course material so far? If not, explain why.

University of Virginia Department of Computer Science CS 201J: Engineering Software

Sponsored by the National Science Foundation

cs201j-staff@cs.virginia.edu