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 worked with a partner on PS2, you may not work with the same person for PS3. 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 may consult any 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.

Purpose

• Gain experience implementing a data abstraction.
• Learn to use abstraction functions and rep invariants to reason about data abstractions.
• Reason about design trade-offs in implementing data abstractions.

Reasoning About Data Abstractions

import java.util.Vector;

class TermRecord { // OVERVIEW: Record type 
   int power;
   int coeff;
   TermRecord (int p_coeff, int p_power);
}

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

   public int 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.
      return terms.lastElement ().power;
    }

   public int coeff (int d) {
      // EFFECTS: Returns the coefficient of the term of this whose
      //     exponent is d.  

      int res = 0;
      for (TermRecord r : terms) {
	 if (r.power == d) { res += r.coeff; }
      }

      return res;
   }

Implementing StringGraph

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 } , ... } >

  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
       DuplicateException. Otherwise, adds
       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  >

  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.

Vector<String> nodes;
boolean [][] edges;

Set<String> nodes;
Set<Edge> edges;

class Edge { 
   String a, b; 
   Edge (String p_a, String p_b);
}

Set<NodeRecord> rep;

class NodeRecord {
   String key;
   Set<String> values;
}