|
CSE 331 Homework 5 - Winter 2012 |
|
 CSE Home |
About Us |
Search |
Contact Info |
Useful LinksRemote access: accessing attu and your personal files from home. Homework 5: ADTs and class designDue: Tuesday, Feb. 28th at 11pm The purpose of this assignment is to get more practice designing, implementing, and testing a program. As before, you get to decide exactly what classes to write and what data and methods each should have. You will also get experience using the model-view-controller design pattern and designing code for reuse. As you know, the UW campus is large and can be difficult to navigate at times. In response, UW Marketing has commissioned you to build a route-finder tool. It will take the names of two buildings and generate directions for the shortest walking route between them, using your graph ADT to model buildings and pathways on campus. For now you will provide a simple text interface, and on the next homework you will write a graphical user interface (GUI). This project was adapted from an assignment in an MIT course taught by Profs. Daniel Jackson and Srinivas Devadas. Errata
IntroductionFor organization, we divide this writeup into a section for each logical component you will write. The order of the sections is not meant to suggest an order of implementation. You will certainly want to design the whole system before attempting to implement any part. As always, you should also develop incrementally, which may mean repeatedly writing a bit of all the parts and verifying that they work together. As before, you should begin by sketching a design alone and should do the final implementation on your own, but we encourage you to discuss your high-level design with classmates and your TAs before implementing it. Please include a list of all students (TAs don't count) with whom you discussed your design in answers_hw5.txt or answers_hw5.pdf. Place all non-test classes in a You should design your application according to the model-view-controller (MVC) design pattern we will discuss in lecture.
For a simple interface like in this assignment, it's not unusual for the view and controller to be intermingled somewhat in code. Don't worry too much about the distinction there; the key part for now is that the model is kept separate. In answers_hw5.txt/pdf, please list which of the classes you write during this assignment are part of the model, the view/controller, or neither (if any). SetupThere is no starter code for this assignment, but we have added several files to your repository:
To get these files, update your project (right-click > Team > Update to HEAD) and they should show up at the top level of the project. If you not using Subclipse, you may need to refresh your project in Package Explorer (right-click > Refresh) after updating to see the new files. ParserYour program will read in data from campus_buildings.txt and campus_paths.txt to construct the graph. You may use The file short_name long_name x_loc y_locwhere short_name is the abbreviated name of a building, long_name is the full name of a building, and (x_loc, y_loc) are the building's location on the map in pixels. The file x1,y1 x2,y2: distance_1_2 x3,y3: distance_1_3 ...Some endpoints are buildings and will match the coordinates of an entry in campus_buildings.txt, but most will not.
Graph representation & minimum-cost pathsYou will use your graph ADT to model the buildings and pathways on campus. We recommend that nodes represent all endpoints of path segments (not just buildings) and edges represent path segments between nodes. As explained in the section slides, finding the minimum-distance route between buildings becomes a matter of finding the minimum-cost path between their nodes, where the cost of an edge is the physical distance of that path segment. Dijkstra's algorithm is a well-known and efficient solution for finding min-cost paths. There are slight variations in implementations of Dijkstra's algorithm. Below is a version that you can use on this assignment. You are welcome to use your own variation, but it must essentially be Dijkstra's algorithm. The standard Java library includes a
// Dijkstra's algorithm: Given a graph with weights/costs on the edges, find the
// minimum-cost path between two nodes
// start is the starting node of our desired path
// dest is the node we are trying to reach
// The priority queue contains nodes with priority equal to the cost of the
// shortest path from start to that node. Nodes for which no path is known yet
// are not in the queue. Initially it only contains start, which has a cost of
// zero because there is a zero-edge path from start to itself.
// For simplicity, the pseudocode below describes the priority queue as storing
// nodes. As described above, items in the priority queue are perhaps better
// represented as paths from start to some node, as the cost of this path
// determines their ordering in the priority queue.
PriorityQueue active = { start }
// The set of finished nodes are those for which we know the shortest paths
// from start and have examined their children.
Set finished = { }
while active is non-empty {
// queueMin is the element of active with the shortest path
queueMin = active.removeMin()
// Somewhere you store the minimum path known thus far (if any)
// from start to a given node.
queueMinPath = path from start to queueMin
if (queueMin == dest) {
return queueMinPath
}
for each edge e = <queueMin, nbr> {
if (nbr is not in finished) {
// If we don't already know of a path from start to nbr (i.e. if nbr
// is not in finished or active), or if we know of a path but the new
// path has a lower cost, then update nbr's min cost path
if (no known path from start to nbr OR
cost of that path > cost of queueMinPath + cost(e)) {
nbr's minPath = queueMinPath + e
cost of nbr's minPath = cost of queueMinPath + cost(e)
}
if (nbr is in active), remove and reinsert since its ordering has changed
else (nbr is not in active), add nbr to active
}
}
add queueMin to finished
}
// execution only reaches this point if no path exists from start to dest
return No Path Exists
ModelAs described above, the model handles the data and contains the major logic and computation of your program. The view simply calls methods of the model to get the information it needs. Functionality of the model includes:
The view can interact with multiple classes in the model, the idea being to avoid one oversized "god class" that does everything. Generally any class that exists solely to represent data is part of the model. For this assignment, you will likely choose to have one central model class that manages the graph and does most of the heavy lifting, but you will likely also want some smaller objects that encapsulate related data. Some of these objects might be returned to the view so it can access their data directly, avoiding the "god class" scenario; others might be used only internally within the model. Your model should be completely independent of the view (UI), which means it shouldn't know or decide how data is displayed. The model does know something about what data and operations the application needs, and it should provide methods to access them; however, it shouldn't return strings tailored to a particular view and definitely shouldn't contain printlns(). Imagine replacing your text UI with a GUI or a Spanish/Mandarin/Klingon text UI (but with the same English building names) and ask yourself: will my model be reusable with the new view? On the flip side, the view doesn't know anything about how the model stores data internally. Someone writing a view for your application should only know that the model somehow stores buildings and paths on campus and should only interact with the data at this level. In other words, the public interface of the model should give no indication that this data is represented internally as a graph. That level of detail is irrelevant to the view, and revealing it publicly means the model can no longer change its implementation without potentially breaking view code. All of your model classes should include an abstraction function, representation invariant, and checkRep() since they should all represent an ADT in some form. Hint: if you are struggling to write the abstraction function, make sure you have clearly defined what the ADT is - in other words, what collection of data this class represents to the client. The description of the ADT goes in the public class comments. Unit TestsOne advantage of separating the model from the UI is that it is easier to unit-test the core logic of the program. You will write unit tests for each public model class. Place these in the package View/ControllerOn this homework, you will write a simple text interface that repeatedly accepts one-character commands from the user:
We have provided the output from a sample run of our solution. Your solution should match this format as closely as possible. Route directions are printed one line per path segment. Each line is indented with a single tab and reads "Walk [dist] feet [direction] to ([x],[y])" where [dist] is the length of that segment in For readability, distances and coordinates should be formatted with a fixed number of digits after the decimal point. The easiest way to specify the desired format of a value is using format strings. For example, to create the String "Walk 12.2 feet NE to (1.23,4.56)" you could write:
String.format("Walk %.1f feet NE to (%.2f,%.2f)", 12.2222222, 1.239999999, 4.5699999999);
If one or both buildings in a route is not recognized, the program prints an "Unknown building: [name]" message. For ease of grading, please follow the format of the sample output exactly for the commmands listed above. You are welcome (but not expected!) to get creative with better ways to display directions or additional features by adding commands to the menu, e.g. 'r2' for improved directions. We may award a small amount of extra credit for especially interesting features, but we make no guarantees. Briefly describe any additional commands in answers_hw5.txt/pdf. Note: for now, your view will probably also include your controller implicitly. Don't worry about the distinction between these components just yet; just focus on the view as the user interface. Hints & Tips
TurninAs before, turnin will consist of adding your files to your repository before the deadline. If you are unsure whether you have added and committed everything, you can to check out a second copy of your repo in a project with a different name and verify that it contains everything you expect. The necessary components include:
The abstraction function, representation invariant, and checkRep() are not required for the parser or view since these classes generally do not represent ADTs. 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 |