|
![]() |
![]() |
![]() |
![]() |
Useful LinksJavadoc specification for the Remote access: accessing attu and your personal files from home. Homework 4: ADTs and class designDue: Thursday, February 9, 2012 at 11pm In this assignment you will practice designing and implementing an ADT. For simplicity, the assignment is broken into several parts: writing the public specification, implementing it and testing it, and writing a client application. In reality, these parts will likely overlap as later parts suggest improvements to your earlier design. You will also learn to use version control software, an important tool for managing large projects. Although this is an individual assignment, you will learn more and ultimately produce a better design by bouncing ideas off others, getting feedback and sharing ideas. You should begin by sketching out a design alone, but you are strongly encouraged to then discuss your design from Part 2 with your classmates as well as your TAs during office hours. The standard collaboration policy still applies to your implementation in Part 3, however: you should not show other students your code. Please include a list of everyone with whom you discussed your design in your answers.txt/answers.pdf file. This project was adapted from an assignment in an MIT course taught by Profs. Daniel Jackson and Srinivas Devadas. ErrataFeb. 5: Feb. 5: I should add that if you had unit tests in Feb. 6: The released version of else { bookChars.add(character); } SetupIn this project you will learn to use version control software, in particular a flavor called Subversion (SVN). We will discuss what version control is, common terminology, and how to use SVN/Subclipse during section. You can also refer to this SVN cheat sheet.
The GraphApplications project should now appear in Package Explorer with the rest of your projects. Part 1: Written ExercisesThis part is designed to test your understanding of some of the ADT concepts from lecture. Place your answers in a file named answers.txt or answers.pdf at the top level of your
Parts 2-4: Writing a graph ADTIn the rest of this assignment, you will design, implement, and use a graph ADT - specifically, a directed labeled multi-graph. Given an abstract, high-level description of the ADT, you will create and test a working Java implementation. When a client application has a need for this ADT, it can construct an instance of your representation. You will decide what classes and public methods/constructors to expose to the client (the public interface) and what instance fields, etc. your classes will need to accomplish what it promises (the internal representation). Here is more information on a directed labeled multi-graph:
![]() Many diverse and interesting problems can be represented with graphs. Often the labels on edges represent the "cost" of traversing a given edge. For example:
The two most common ways to represent a graph are with adjacency lists or an adjacency matrix. For this assignment, we recommend adjacency lists, in which each node is associated with a list containing all its outgoing edges. Part 2: DesignApproachYou will start by designing the public interface for a Java class or classes that represent a directed labeled multigraph as described above. Your design should be general enough to serve as the main data structure for a variety of applications requiring graphs, including the one you will implement in Part 4 and the examples given earlier. In addition to edge labels, each of your nodes will need to store some sort of data/value. For example, in the airline flight graph described earlier, a node might store the name of a city or airport. Design problems such as this one are open-ended by nature. A good design provides the functionality the client needs in an interface that is easy to use and supports clean, readable, and maintainable code, both in the ADT itself and in the client code. There is no one "right" design, but there are general principles of good design to which you will be introduced in lecture. We recommend that you work in iterative layers of detail. Start rough - preferably with pencil and paper. Brainstorm what operations the ADT needs to support, how it might be logically broken into modules (classes/interfaces), and how these modules connect to each other. Then jot down a list of methods for each class that provide these operations. "Test" your design by thinking through some possible client applications, particularly the application you will implement in Part 4. Write some pseudocode (or even real code) for the application and make sure your graph interface meets its needs. Keep your design rough at first: avoid writing extensive descriptions of your methods or formal Java method signatures, let alone compilable Java code. Your design will likely go through multiple iterations, and it's easier to throw away parts before you've invested too much effort in them. DeliverablesOnce you are satisfied with your high-level design, add detail and structure by writing Javadoc pages. Return to the computer and write a skeleton for each class or interface, placing them in the Your generated Javadoc pages should go in the We recommend you generate the Javadoc pages before going on to Part 3. Seeing the "client contract" alone without the source code may help you mentally separate the external specification and internal implementation. You are welcome to make adjustments to your ADT in Parts 3 and 4. We recommend regenerating and reviewing the Javadoc pages anytime you make significant changes and generating a final copy just before turnin. In addition to Javadoc, include a short writeup describing your final design and design process. This should include:
Because your design is likely to change in Parts 3 and 4, we recommend that you be sure to check this summary and revise it just before turnin. Keep notes as you go to remind yourself of the process. Your writeup should be brief, just one or a few short paragraphs. We are grading for content, not length, and one concise paragraph will be favored over several paragraphs that say the same thing in twice as many words. Place this paragraph in your answers file from Part 1. You should not write about implementation details at this point. Hints & GuidelinesAs mentioned earlier, you should think through some client applications to determine what functionality your class needs. Operations a client will surely want include the ability to:
Should the client be able to remove nodes from a graph? get a list of all edges? Should path-finding operations be included as methods of the graph, or should they be implemented in client code on top of the graph? These, along with the questions below, are examples of what you should be considering as you think through your design. Generally the questions raised here don't have clear, simple answers. In making a decision, you'll need to weigh tradeoffs, consider the unique requirements of your design, and think carefully about how decisions will interfere with each other.
Part 3: Implementation & testingOnce you are satisfied with your design, implement it! Include an abstraction function, representation invariant, and checkRep() function in each class, calling checkRep() where you deem appropriate (particularly in mutator methods - generally, anywhere the RI might have been broken). Your graph implementation should have reasonable performance for graphs with thousands (but not millions) of nodes and edges, such as the application in Part 4. 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). For instance fields, try to choose data structures best suited for the given purpose. Also write JUnit tests for your implementation and put these in the We recommended that you try a test-driven development approach, writing the tests before the implementation. You might write the entire test suite first or you might develop incrementally, writing the tests for a method just before implementing that method. Lastly, submit a brief paragraph describing your implementation experience. What worked as you expected? What changes did you make along the way? How did your implementation experience affect the ultimate design, if it did? What were the biggest surprises? What alternative implementations did you consider, and why did you choose the one you did? If you tried a test-driven development approach, feel free to mention your impressions of this approach. Part 4: Using your ADTIn this part, you will use your graph ADT to model the Marvel Comics universe! In this application, nodes represent characters, and edges represent appearances of two characters in the same comic book. For example, if Zeus and Hercules both appear in book "T 221," then there will be an edge from Zeus to Hercules with label You will write a class Char1 Book1 Char2 Char2 Book2 Char3 ... CharN-1 BookN-1 CharNwhere Char1 is the first command-line argument, CharN is the second argument, Char_k is the name of some character, and Book_k is the title of some book for all k . Each character and book is separated by one tab. This path indicates that Char1 appeared in Book1 with Char2, Char2 appeared in Book2 with Char3, and so on, ending with CharN-1 appearing in BookN-1 with CharN.
Not all characters have a path between them. If the user gives two valid character names with no path, print Command-line arguments are simply parameters specified when the program is launched, and they are accessible via the For example, to find a path from "FLYING FOX" "FLYING TIGER"and your program should print a list such as: FLYING FOX SSU 1 BOVA BOVA M/TIO 74 HUMAN TORCH/JOHNNY S HUMAN TORCH/JOHNNY S ASPOT 29/2 FLYING TIGER Your program should print the shortest path between two characters, but if there are several shortest paths it can print any one. We recommend that you use a breadth-first search (BFS) for pathfinding. A BFS from node u to node v, visits all of n's neighbors first, then all of n's neighbors' neighbors', then all of n's neighbors' neighbors', and so on until v is found or all nodes with a path from u have been visited. Below is a pseudocode algorithm to find the shortest path from u to v in a graph G: u = starting node v = destination node M = map from visited nodes to paths: initially empty. paths should be stored as lists of nodes or edges (or perhaps just the node data or edge labels). Q = queue of nodes to visit: initially empty Add u to Q Add u->[] to M (u mapped to an empty list) while Q is not empty: dequeue next node n if n == v, lookup n in M and return the associated path for each edge e=<n,m>: if m is not in M, i.e. m has not been visited: add m to Q let p be the path n maps to in M let p' be the path formed by appending e to p add m->p' into M if loop terminated, no path exists from u to v (return some value that indicates this) In the top level of your project is a file [character] [book]where [character] is the name of a character, [book] is the title of a comic book he/she/it appeared in, and the two fields are separated by a tab. The file is sorted by character name, so all entries for a given character are consecutive.
We provide you with a class TurninRather than submitting files to the dropbox, you will commit them to your repository, which we will check out to grade. Be aware that new files are not added to the repository until you tell Subversion to do so. If a file isn't added, it will appear with a question mark icon in Package Explorer, and we won't see it when we check out your repo. To add the file, right-click on the file or directory and choose Team >> Add to Version Control. The added files will now appear with a plus sign icon until your next commit. If you are unsure whether you have added and committed everything, you can to check out a second copy of your repo in a different workspace or a project with a different name and verify that it contains everything you expect. You should add the following files to your repo:
LATE DAYS: As usual, you may use up to two late days on this assignment. We will check out your repository as of the deadline for grading, which means we will assume you have have NOT used late days unless we hear otherwise. Please email the coures staff if you are using a late day, and we will check out your repository 24 or 48 hours after the deadline.. |
![]() |
Computer Science & Engineering Box 352350, University of Washington Seattle, WA 98195-2350 (206) 543-1695 [comments to Hal Perkins] Privacy policy and terms of use |