6.170 Laboratory in Software Engineering
Spring 2002
Problem Set 3: Design an Abstract Data Type
Due: Tuesday, March 5, 2002 at 4pm

Handout P3

Quick links:

We recommend that you read the entire problem set before you begin work.

Introduction

In this exercise, you'll design and implement an abstract type. Designing an abstract type involves determining what services it should provide and what their behavior should be -- that is, writing a specification. Implementing an abstract type involves choosing a representation and algorithms, and embodying them in code. The focus of this exercise is the design, so you should expect to spend a considerable amount of time on it. In order to get you started, we will ask you to criticize a sample abstract type. Note the distribution of points among each problem. We advise you to distribute your time accordingly.

Problems

Problem 1: Critique an ADT (15 points)

People have relationships. For example, Alyssa P. Hacker and Ben Bitdiddle may be married (spouses of one another) and have children (be parents of the children). Families are groups of people. The abstract object model shown below is one particular embodiment of a family. In this problem, you will critique this model and its specification.

Provided data

Questions

Graphs

The abstract type that you'll design is a directed labelled multi-graph. A graph is just a collection of nodes with edges between them.  Every edge connects one node to one other node. There can be nodes without edges but no edges without nodes. A node may be connected to itself. In a multi-graph, there can be zero, one or more edges between a pair of nodes. Every edge has a label; distinct edges may have the same label.

Here are some examples of applications of directed labelled multi-graphs.
Your type will be used to find directions on the Boston subway, so in its use, the nodes will represent stations and the edges will represent track segments. But your design and implementation should be polymorphic . This means that the node type should be generic; it should be possible to use your graph design and implementation in different applications.

Your graph implementation must be efficient. This means it should perform reasonably for medium sized graphs -- those consisting of thousands (but not millions) of nodes and edges. You should not assume that the graph will be sparse (that is, containing very few edges compared to nodes) or dense (that is, with most node pairs connected).

Ideas

To give you some sense of the kinds of issues you should be considering in your design, here are some questions you might want to consider. These don't in general have simple answers. You'll need to exercise careful judgment, and think carefully about how decisions you make interfere with each other.

Problem 2: Graph Specification (55 points)

Design an abstract data type for a directed, labelled graph. Your record of your design should be included in one or more files distinct from the source code itself, and should include at least the following elements:
  1. A brief overview paragraph saying what classes or interfaces are visible to clients of the graph, and what role they play.
  2. A comment on the computational complexity of the graph: say which methods you expect to be computationally intensive, and give a bound on their asymptotic cost, and give a bound on the space requirements. For example, you may say (rather implausibly) that addNode will be the most costly method, that, as the graph grows, its cost should increase at most quadratically with the size of the graph, and that the memory required to represent the graph will grow exponentially with the number of edges.
  3. For each public class or interface:
  4.  A brief design rationale (no more than half a page long) listing, as separate points, a variety of alternative design features that you considered but rejected, with explanations of why they were rejected.

Problem 3: Graph Implementation (20 points)

Implement the graph and test your implementation using JUnit.

You should hand in:

  1. A brief overview of the implementation you chose, along with a brief rationale justifying your in comparison to another, different (but still plausible) implementation.
  2. A code object model which contains all the important implemented classes along with textual constraints. Note that code object models need not have all the details of the implementation.
  3. Tastefully commented source code.
  4. Code for your test cases.
  5. A statement indicating whether or not your code passes all the tests. We will assume that your code fails if you say nothing.

For this problem, a small collection of plausible test cases will suffice. In next week's exercise, you'll return to the code and examine it more carefully. Here, the purpose of the testing is to make you comfortable with JUnit, and to help you weed out egregious errors that would prevent you from completing this problem.

Problem 4: Using the Graph (10 points)

Build a program that generates directions for the Boston subway system. It should accept two station names as input on the command line, and output a list of steps to be taken.

A simple breadth-first search is adequate. Don't worry about handling the kinds of complications a real program would have to handle (such as selecting a Green Line train at Park Street, and amalgamating steps into journeys on individual lines).
We have written some code that parses the file describing the Boston subway system. This file bostonmetro.txt should be an input to the program. The code in question is found in MetroMapParser.java. You should make modifications to this file, by inserting calls to your Graph ADT methods. Depending on how you have designed your ADT, these calls will be different. For example, if you have built an immutable Graph, you might have to collect all the information from the file before you build your Graph. However, if you have built a mutable Graph, you might be able to build it up incrementally as the file is parsed. In any case, you should read through the parser code carefully, and provide clear documentation on the modifications you are making.

You should hand in:

  1. Tastefully commented source code.
  2. Sample output for some test cases.

Provided Code

Getting started

Make sure you have followed the instructions on the tools handout relevant to directory setup and using Java before you begin development.

Create a ps3 directory and copy the provided files to it: 

mkdir ~/6.170/ps3
cp -p /mit/6.170/www/psets/ps3/src-subway/*.java ~/6.170/ps3

Hints

See the problem set guidelines and advice .

If you are unclear about how to read/write specifications, read Handout S3 (A Guideline to Specifications).

You may find the Integer.parseInt(String s) method to be of use in converting String's into int's.

Although it is generally a bad idea to start coding before you have thought deeply, it often makes sense to work incrementally, interleaving design and coding. Once you have a sketch of your specification, you may want to write some experimental code. This should give you some concrete feedback on how easy it is to implement the methods you've specified. You may even want to start at the end, and write the code that uses your type, so that you can be confident that the methods you provide will be sufficient.

This strategy can backfire and degenerate into mindless hacking, leaving you with a pile of low-quality code and an incoherent specification. To avoid that, bear two things in mind. First, you must be willing to start again: experimental code isn't experimental if you're not prepared to throw it away. Second, whenever you start coding, you must have a firm idea of what you're trying to implement. There's no point starting to code to a specification that is vague and missing crucial details. That doesn't mean that your specification must be complete and polished, but it does mean that you shouldn't start coding a method until at least you have its own specification written. Third, should must write down the specification of a method and not just imagine it; it's too easy to delude yourself. Try to write it on paper and mull it over before you start any coding. It's tempting to sit in front of an editor, write some specification as comments, and then start coding around them, but this tends not to be nearly so effective.

Make good use of your TA. Take your specification to office hours before going to the lab and get some feedback on your design and style. This is likely to save you a lot of time!

Errata

None, so far.

Q & A

This section will list clarifications and answers to common questions. 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 handout) when you have a problem.

Back to the Problem Sets .
For problems or questions regarding this page, contact: 6.170-webmaster@mit.edu .

$Id: ps3.html,v 1.17 2002/02/25 20:00:19 kalpak Exp $