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 MapQuick's graph-building algorithm and GUI component.
There is no code provided in this problem set, but you will want to update the psets module in your CVS repository to create the psets/ps5 directory.
By the end of the problem set, you should have the following files
committed to CVS 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 CVS:
answers/ folder
and add it to CVS so your TA 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? 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 overwrite the addNode
method such that it 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
void addNode(N node) throws UnsupportedOperationException {
// Throws exception regardless of input
}
// Unsupported in Tree
void addEdge(N parent, N child) throws UnsupportedOperationException {
// Throws exception regardless of input
}
// Other additional methods
}
Answer the following questions in problem2.txt. Place
the file in your answers/ folder and add it to CVS.
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 is:
class Tree {
public Tree()
effects: creates an empty Tree -- it contains zero nodes and edges.
public void addNode(int n)
modifies: this
effects: this' = this + {TreeNode(n)} where this' is the state of the object
after applying the method
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 descendent 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.
// and 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
// and 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
// 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. When doing so, we can assume that all other
operators do not break the specification. 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 CVS. 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).In Problem Set 6, you will build a graph-based representation of the streets in the MapQuick database.
Consider the following pseudo-code to build such a graph from a
collection of StreetSegments:
for each segment s in the collection of segments
s_r <- reverse of s
add s to the set of nodes
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
add an edge from s to s'
Note: We are ignoring the issue of one-way streets. We are assuming that all street segments in the database allow bidirectional travel and insert both a segment and its reverse in the set of nodes.
Unfortunately, this algorithm requires quadratic time in the number of segments. For MapQuick, this is unacceptable due to the large number of segments in the database.
Give a more efficient algorithm to build the graph. Your
algorithm should run in time O(n*outDegree) where n is the number of
segments and outDegree is the maximum number of segments a single segment
connects to. 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 CVS.
Feel free to use pseudo-code and to introduce auxiliary data structures or helper procedures as necessary. However, please try to keep your answer concise.
In Problem Set 6, you will build a Graphical User Interface (GUI) for MapQuick. In this problem we ask you to put some preliminary thought into the design of that interface. Specifically, we want you to construct a paper mockup of the GUI you plan to build. You can use paper and pencil, or any drawing software you desire. However, you must either:
answers/ folder
and add it to CVS.There are some scanners (for example in SIPB's office at the 5th floor of the Student Center) available to students on campus for those who want to keep a copy of their work for PS6 while we grade this problem set.
You should also describe your GUI in a file called problem5.txt. Please
discuss at least 2 important design decisions you made, as well as at least
2 alternative decisions you considered and why your design is superior.
Try to be concise. Place this file in your answers/ folder and add it to CVS.
MapQuick takes as input two addresses — a starting address and a destination address — each consisting of a building number, street name, and zipcode (e.g., 500 Memorial Dr. 02139). If there is a path from the start to the destination, MapQuick gives directions; if not, it reports that no path between the two addresses exists. On startup, MapQuick reads a collection of database files containing the map information (it reads these files from a directory), and optionally a set of zipcodes to which searches will be confined.
Your GUI should provide at least the following functionality:
* Note: For the final design of MapQuick in PS6, there is a feature that allows users to restrict the search to only certain zipcodes (in order to reduce the graph size that your program will have). Your GUI prototype should have some way of entering this information in, but you may choose to do it in any way you wish.
There exists a great deal of freedom in the design of any graphical user interface. While building your paper mock up, please try to adhere to the guidelines presented in the relevant usability lectures. Try to keep your GUI simple. Your TA will be providing you with feedback about your GUI that you can use in order to update your design before Problem Set 6.
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.
None.
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.