# Problem Set 3: Implementing Abstract Datatypes

Due: Tuesday, 21 September (beginning of class)

Reading: Before beginning this assignment, you should finish reading Chapter 5 and Chapter 10.

Purpose

• Gain experience implementing a data abstraction.
• Develop and carry out a testing strategy for a data abstraction.
• Learn to use abstraction functions and rep invariants to reason about data abstractions.
Collaboration Policy. For this problem set, you may either work alone and turn in a problem set with just your name on it, or work with one other student in your section of your choice. If you work with a partner, you and your partner should turn in one assignment with both of your names on it. Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways. You should not consult materials from previous cs2220/cs205 courses, but you may consult any other outside resources you wish including books, papers, web sites and people. If you use resources other than the class materials, indicate what you used along with your answer.

First, we will consider a implementing the Poly abstraction from Chapter 5 (specified in Figure 5.4). Suppose we implement Poly using a java.util.ArrayList. The ArrayList type allows us to represent an ordered collection of Objects. The objects we will store in our list are records of <term, coefficient>.

Here is the representation:

```import java.util.ArrayList;

/**
* OVERVIEW: A TermRecord is a record type for a power and coefficient.
*/
class TermRecord {
int power;
int coeff;
TermRecord (int p_coeff, int p_power) {
power = p_power;
coeff = p_coeff;
}
public String toString () {
return "TermRecord: " + coeff + " x^ " + power;
}
}

/**
* OVERVIEW: Polys are immutable polynomials with integer coefficients. A typical Poly is:
*    `c_0 + c_1*x + c_2 * x^2 + ... + c_n * x^n`
*/
public class Poly {
// Rep:
private ArrayList<TermRecord> terms;
...
```

Suppose this is the implementation of degree:

```   /**
*  EFFECTS: Returns the degree of this, i.e., the largest exponent
* 	with a non-zero coefficient.  Returns 0 if this is the zero Poly.
*/
public int degree () {
return terms.get(terms.size() - 1).power;
}
```

1. What abstraction function and rep invariant are needed to make the implementation of degree above satisfy its specification?

In an alternate implementation with the same rep (that is, the abstraction function and rep invariant may be different), suppose this is the implementation of coeff:

```   /**
* EFFECTS: Returns the coefficient of the term of this whose exponent is d.
*/
public int coeff (int d) {
int res = 0;
for (TermRecord r : terms) {
if (r.power == d) { res += r.coeff; }
}

return res;
}
```
2. What rep invariant would make the implementation of coeff above correctly satisfy its specification?
3. Explain how a stronger rep invariant would make it possible to implement coeff more efficiently.

### Implementing StringGraph

Here is the specification of a StringGraph datatype. It is similar to the LabeledGraph datatype from PS2, except it does not have labels on the edges.

```public class StringGraph
OVERVIEW: A StringGraph is a directed graph  where
V is a set of Strings, and E is a set of edges.
Each edge is a pair (v1, v2), representing an edge
from v1 to v2 in G.  A typical StringGraph is
< {v1, v2, ..., vn} , { (v_a1, v_b1), (v_a2, v_b2), ... } >
where each ai and bi is in [1, n].

public StringGraph()
EFFECTS: Creates a new, empty StringGraph: < {}, {} >

public void addNode(String s) throws DuplicateException
MODIFIES: this
EFFECTS: If s is the name of a node in this, throws
s to the nodes in this, with no adjacent nodes:
Gpost = < Vpre U { s }, Epre >

public void addEdge(String s, String t) throws NoNodeException, DuplicateException
MODIFIES: this
EFFECTS: If s and t are not nodes in
this, throws NoNodeException.  If there is already an edge
between s and t, throws DuplicateEdgeException.
Otherwise, adds an edge between s and t to this:
Gpost = < Vpre, Epre U { (s, t) } >

public Set<String> getAdjacent(String s) throws NoNodeException
EFFECTS: If s is not a node in this, throws NoNodeException.
Otherwise, returns a set containing the nodes adjacent to s

That is, returns the set of nodes
{ e | <s, e> is in E }

public String toString()
EFFECTS: Returns a human-readable string representation of this.
```

There are many possible representations for the StringGraph. Here are three possibilities:

 a ```ArrayList nodes; boolean [][] edges; ``` b ```Set nodes; Set edges; ``` where Edge is a record type containing two String values: ```class Edge { String a, b; ... // constructors and toString } ``` c ```Set rep; ``` where NodeRecord is a record type that records a String and an associated set of Strings: ```class NodeRecord { String key; Set values; ... // constructors and toString } ```

4. For each representation choice (a, b, and c), provide an abstraction function and rep invariant.
5. Which representation choice would make implementing addNode most difficult? Explain why.
6. Which representation choice would enable the most efficient getAdjacent implementation? Explain why.

The next two questions ask you to implement the StringGraph datatype. The first question asks to develop a testing strategy, and the second question asks for the datatype implementation. You will probably want to revise your answers to question 7 as you develop your implementation, but we strongly recommend thinking about and developing your tests before the implementation, and refining them as you develop the implementation and are actually able to run the test cases.

7. Describe a testing strategy for an implementation of StringGraph datatype. Design a set of test cases, and implement code that performs them. Include all the code you developed for testing in your answer.
8. Implement the StringGraph datatype specified above. Your implementation may use any representation you want (including the ones describe above, but not limited to those choices). Your implementation should clearly document its abstraction function and rep invariant.

Note that the specification requires the NoNodeException and DuplicateException datatypes. These should be defined in separate files as subtypes of Exception. For example, NoNodeException should be defined as:

```package ps3;

public class NoNodeException extends Exception {
private static final long serialVersionUID = 1L; // Avoids compiler warning
}
```
9. Consider adding a removeNode method to the StringGraph datatype that removes a node from a graph. Write a declarative specification for the removeNode method. Consider carefully what should happen with the edges of the graph when a node it removed, and make sure your specification is total.
10. Implement the removeNode method you specified in question 8, and extend your testing to include the removeNode method.
This is the end of the expected part of this problem set. The following two questions are optional.
11. (optional) Specify, implement, and test a GenericGraph<V> parameterized type where V is the type parameter representing the type of each node in the graph. You should be able to reuse most of the code you wrote to implement the StringGraph type, as well as the tests.
12. (optional) Specify, implement, and test a LabeledGraph<V, E> parameterized type where V is the type parameter representing the type of each node in the graph and E is the type of the edge label.
Turn-in Checklist: You should turn in your answers to questions 1-10 on paper at the beginning of class on Tuesday, 21 September. (It is not necessary to submit your code electronically.)

### 5 Responses to Problem Set 3: Implementing Abstract Datatypes

1. bkn3yh says:

In public class Poly {
// Rep:
private ArrayList<TermRecord&gt terms;

what does &gt mean?

• David Evans says:

Sorry, its an html bug. It should just be a >. Its fixed now, thanks for reporting the problem!

2. David Evans says:

I’ve fixed a couple typesetting problems with the StringGraph specification. The overview specification should list the edges as ordered pairs, instead of sets. It now reads,

A typical StringGraph is
< {v1, v2, ..., vn} , { (v_a1, v_b1), (v_a2, v_b2), ... } >
where each ai and bi is in [1, n].

Note that the abstract representation of the edges is a set of pairs of Strings, where each string is the name of a node in the node set.

Also, I fixed the specification of addEdge. There was a problem with the html, it should read

Gpost = < Vpre, Epre U { (s, t) } >

to show the new edge is added to the set of edges.

Sorry for the confusion!

3. blantonj says:

The specification for StringGraph says that it is a directed graph, which means that each connection goes one way. For getAdjacent, then, should it include all nodes in any way connected to the input or just ones that start at the input?

• David Evans says:

The specification is less clear than it should be on this, since the prose is ambiguous, but the formal notation is more clear (but not consistent with the notation used elsewhere!):

EFFECTS: If s is not a node in this, throws NoNodeException.
Otherwise, returns a set containing the nodes adjacent to s

That is, returns the set of nodes
{ e | <s, e> is in E }

This suggests that it should only include nodes that can be reached following an edge from s to e. The inconsistency is the abstract notation uses (s, e) to denote edges, but the spec here incorrectly uses <s, e>.

A better specification would make this more clear:

EFFECTS: If s is not a node in this, throws NoNodeException.
Otherwise, returns a set containing the nodes that can be reached following an edge from s

That is, returns the set of nodes { e | (s, e) is in E }