Contents:
Abstract reasoning is important throughout all stages of developing a software system. This problem set starts off by developing your ability to reason abstractly about the properties of the code that you write.
Then you will be challenged to think ahead about Husky Maps's graph-building algorithm.
There is no code provided in this problem set, but you will want to update the cse331 directory in your SVN repository to create the cse331/src/ps5 directory.
By the end of the problem set, you should have the following files
committed to SVN in your ps5 directory:
In Problem Set 3, you specified and implemented a generic graph
abstraction.
Answer the following questions
in a file called problem1.txt. Place it in your answers/ folder
and add it to SVN:
ps3/Graph.java,
though you may well have made improvements or changes
since you submitted it for PS3. Ensure that your overview and
specfields correspond to a graph abstraction and not to your particular
implementation. Include a copy of your Graph implementation in your answers/ folder
and add it to SVN so the grader can reference it easily.Graph preserves its
representation invariant. Please be as concise as possible. A good argument
will explain why the representation invariant is not broken by each public
method in the class.Graph to represent the same abstract state? (We are not
asking about whether two distinct objects with the same concrete state
may exist, such as the result of two calls to new Graph()
that create two distinct Java objects at different locations in memory
but with the same concrete state.)
If so, give
an example; if not, briefly explain why this is impossible.Now we add a class Tree that extends Graph. A tree
is a connected graph in which every node A has only one edge coming in from
another node B. A is the child of B and B is the parent
of A. All nodes in a tree, except the root, have exactly one parent.
A tree must not contain cycles, meaning that if B is the parent of
A, B cannot be a child or a descendant of A.
When adding a node to a tree, you must specify the parent of the node as well. We do not allow new edges to be added other than those added when adding new nodes.
A simple implementation of Tree could inherit its constructors
and observers from the Graph class, and create an addNode
method that adds the new node and an edge to its parent at the
same time.
class Graph<N> {
// Adds a node to the graph
void addNode(N node);
// Adds an edge from parent to child
void addEdge(N parent, N child);
// Other additional methods, including a constructor that
// takes no parameters and returns an empty graph.
}
class Tree<N> extends Graph<N> {
/* @requires root != null
* @effects Constructs a tree with a single node, root.
*/
public Tree(N root) {
super();
super.addNode(root);
}
/* @requires parent != null && child != null && parent is in graph
* @effects Add the node child to graph, and add an edge from parent to child
*/
void addNode(N parent, N child) {
if (parent not in graph) {
// Error handling code
} else {
super.addNode(child);
super.addEdge(parent, child);
}
}
// Unsupported in Tree
// Throws exception regardless of input
void addNode(N node) throws UnsupportedOperationException {
throw new Exception("Unsupported in Tree");
}
// Unsupported in Tree
// Throws exception regardless of input
void addEdge(N parent, N child) throws UnsupportedOperationException {
throw new Exception("Unsupported in Tree");
}
// Other additional methods
}
Answer the following questions in problem2.txt. Place
the file in your answers/ folder and add it to SVN.
Tree a true subtype of Graph? Why?Tree to subclass
Graph? Why or why not?This problem lets you practice using induction over operators to prove correctness. We will work with a representation of a tree data structure. Recall that a tree is a connected graph that contains no cycles. Our tree's nodes are identified by integer values. A node's "descendants" include any node that can be reached by traversing edges to successive children.
Remember that the concept of correctness is undefined without a specification and representation invariant. The specification uses the convention that x' is the state of x at the method exit (in other words, x is like x_pre, and x' is like x_post; they are just different conventions for saying the same thing). The specification is:
// Represents a multiset of integers.
class Tree {
public Tree()
effects: creates an empty Tree that contains zero nodes and edges.
public void addNode(int n)
modifies: this
effects: this' = this + {TreeNode(n)}
public void deleteNode(int n)
modifies: this
effects: this' = this - {TreeNode(n)}
public boolean containsNode(int n)
returns: this.contains(TreeNode(n))
}
class TreeNode {
public TreeNode(int v)
effects: create a node with the given value
public void addChild(TreeNode n)
modifies: this
effects: this'.children = this.children + n
public void removeChild(TreeNode n)
modifies: this
requires: this.children.contains(n)
effects: this'.children = this.children - n
public int getValue()
returns: this.value
public TreeNode getInsertableNode()
returns: any descendent node with fewer than 2 children
public TreeNode findParentOf(int n)
returns: the parent of any node with the value n
public TreeNode findNode(int n)
returns: any node, from among all descendants, with the value n
public List getChildren()
returns: this.children
}
Here is pseudo-code for an implementation along with a representation invariant with two clauses. Note that this specification is different from the one given in Problem 2.
class Tree {
private TreeNode rootNode;
// Representation invariant:
// - there are no cycles in the tree,
// - there is exactly one path from the root to any node in the tree.
public Tree() {
// set rootNode to null
}
public void addNode(int n) {
// if the rootNode is null,
// set it to TreeNode(n)
// otherwise,
// Create a new node with value n.
// Find a descendant with fewer than 2 children.
// Add a new node as its child.
// (note: one or more other TreeNode objects with the same
// value might already be in the tree.)
}
public void deleteNode(int n) {
// if the root node isn't null:
// if the root node has value n
// Make one of the root's children the new root.
// Make all the other children be children of the new root.
// Delete the node.
// else
// Find the node and its parent.
// Make every child of the node be a child of the node's parent.
// Delete the node.
}
public boolean containsNode(int n) {
// if the root node isn't null:
// if the node is the root,
// return true
// else
// if a descendant node has value n:
// return true
// else
// return false
}
}
class TreeNode {
List<TreeNode> children;
int value;
public TreeNode(int v) {
value = v;
children = new ArrayList<TreeNode>();
}
public void addChild(TreeNode n) {
// insert n into the children List
}
public void removeChild(TreeNode n) {
// remove n from the children List
}
public int getValue() {
return value;
}
public TreeNode getInsertableNode() {
// do a depth-first search of the
// children and find a node with fewer than 2 children
}
public TreeNode findParentOf(int n) {
// do a depth-first search of the children,
// stopping at a node that has a child with value n
}
public TreeNode findNode(int n) {
// if value == n
// return this
// else
// do a depth-first search of the of children,
// stopping at the node that has value n
}
public List<TreeNode> getChildren() {
return Collections.unmodifiableList(children);
}
}
Using this specification and implementation outline, let's reason about the representation invariants:
Tree that has no cycles. We must prove that
each operator does not induce a cycle. If [the proof that operator X
does not induce a cycle] depends on [the proof that operator Y does
not induce a cycle], that's okay, as long as you eventually prove that
operator Y does not induce a cycle. This could happen, for example, if
one of your operators calls one of your other operators. Further, we
will only give proofs for methods in Tree, not TreeNode. The method
addNode(int n) has two cases:
Answer the following questions in problem3.txt. Place it in your answers/
folder and add it to SVN. For your proofs you may assume that no two nodes in the
tree have the same value.
deleteNode(int n) does
not induce any cycles in the tree.
Your proof should not be long. You should
break the proof into cases that mirror the cases in the pseudo-code.addNode(int n). (Hint:
you can assume that you have a path from the root to the node
where you're inserting the new node.)deleteNode(int n).containsNode(int n).addNode, a node has more than 2 children? Explain why
or why not, in no more than one paragraph.In Problem Set 6, you will build a graph-based representation of the streets in the Husky Maps database.
Consider the following pseudo-code to build such a graph g from a
collection of StreetSegments:
g = a new Graph
for each segment s in the collection of segments
s_r <- reverse of s
g.addNode(s) // add s to the set of nodes
g.addNode(s_r) // add s_r to the set of nodes
for each segment s in the set of nodes
for each segment s' in the set of nodes
if s.p2 = s'.p1
g.addEdge(s, s1) // add an edge from s to s'
Unfortunately, this algorithm requires quadratic time in the number of segments. For Husky Maps, this is unacceptable due to the large number of segments in the database.
Give a more efficient algorithm to build the graph.
The algorithm should call addNode and addEdge.
Your algorithm should run in expected time O(n*outDegree) where n is the
number of segments and outDegree is the maximum number of segments a single
segment connects to. You may assume that the addNode and
addEdge operations of Graph run in expected constant time.
Describe your algorithm in problem4.txt and argue that it
meets the specified time bound. Place the file in your
answers/ folder and add it to SVN.
Feel free to use pseudo-code and to introduce auxiliary data structures or helper procedures as necessary.
Half a page is more than adequate. Any answer longer than 1 page (as printed by the CSE 331 staff tools used in previous problem sets) will receive no credit.
Please answer the following questions in a file named collaboration.txt in your answers/ directory.
The standard collaboration policy applies to this problem set.
State whether or not you collaborated with other students. If you did collaborate with other students, put their names and a brief description of how you collaborated.
Please answer the following questions in a file named reflection.txt in your answers/ directory.
2/8/2011: Added a missing line to the Graph Building pseudocode.
This section will list clarifications and answers to common questions about problem sets. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully rereading the problem set handout and the specifications) when you have a problem.