PurposePart 1: ExercisePart 2: DesignDeliverablesResourcesPartial Solution to PS4MapsGraph FilesSample CodeDijkstra's AlgorithmStatisticsMechanics6.170 Laboratory in Software Engineering Fall 2005 Problem Set 5: Stata Center Navigation and AnalysisDue Date: Oct 20, 2005 Quick links: • Purpose • Part 1. Exercise • Part 2. Design • Resources o Partial Solution to PS4 o Maps o Graph Files o Sample Code o Dijkstra's Algorithm o Statistics • Mechanics • Expectations • Errata We recommend that you read the entire problem set before you begin work. Purpose The purpose of this problem set is to exercise your design and implementation skills. At the end of the problem set, you will have designed and implemented a complete interactive program, from start to finish. You will also gain some experience with component reuse, and its pros and cons. Part 1: Exercise Draw a module dependency diagram for the code that your wrote in the last problem set (the graph datatype and subway route finder). You'll need to review your code very carefully to make sure you haven't omitted any dependences. After that, answer the following 3 questions: • 1) Briefly comment on the quality of your design as measured by the presence of dependences.• 2) Are any of the dependences undesirable? • 3) If so, how might the code be changed to eliminate them? To hand in: • 1. Type your answer to these 3 questions in doc/exercise.txt then add it to CVS. • 2. You can draw the diagram using any tool you like. Just make sure you export it as a GIF or PNG file, then add it to your CVS as doc/exercise.gif or doc/exercise.png. Make sure you add the picture in BINARY mode, or else the picture will be corrupted. To ensure that your pictures are added in binary mode, go to the menu on top and click on Window. Then click on Preferences.... Expand the Team option on the left. Then click on the CVS option under Team. Make sure you check the checkbox that says Treat all new files as binary. You can then click OK to close the window. Running validate6170 ps5 will verify whether your picture and text files are correctly added to the CVS repository. Part 2: Design As some of you may have discovered, getting round Stata isn't always easy. In this problem set, you'll build a program that generates directions to help you find your way around. Your program should take as input a starting and ending point, specified by MIT room numbers (eg. "123", "D430", "G519", etc), and should be able to generate both a minimum time and a minimum distance path. It should handle starting and ending points that are on different floors. We will supply you with a map of (most of) the building in textual form, as well as images showing the room layout of individual floors. How you use these resources is up to you. You will probably want to display the recommended directions graphically, but you DO NOT need to build it as a graphical program if you provide a well-designed textual output instead. The core of your program algorithmically will be the graph datatype that you built in your previous problem set. Below you will find some hints on how to conduct a search in a graph. There are several challenges to overcome beyond the problem of search in a graph, however. At the very least, you will need to figure out how to show directions that cross floors, and how to handle ill-formed input.The focus of this problem is designing a collection of modules that work well together to provide the necessary functionality, but which interact via simple and clean specifications. A measure of the quality of your design is how easy it is to extend the function of the program. As part of your submission, you should explain how you would handle each of the following enhancements. You are not required to implement them (but if you have time, you may well want to). • Find optimal paths during a fire alarm (no elevators), and for handicapped (no stairs). • Find paths that do not pass in front of your TA's office in Stata. • Find shortest path that also goes through places of a particular type. (e.g. past a bathroom or a printer) Deliverables • 1. An object model diagram describing the problem domain: rooms, names, floors, paths, etc. In particular, your model should explain how elevators and stairs are modelled. Please save this picture in doc/pom.png or doc/pom.gif • 2. An object model diagram describing the heap state of the running code. Please save this picture in doc/com.png or doc/com.gif • 3. A module dependency diagram for your program. Please save this picture in doc/mdd.png or doc/mdd.gif • 4. Source code with an appropriate level of commenting and Javadoc specification, and appropriate JUnit tests for your modules. These should be in src/ps5 • 5. Think about the 3 potential enhancements listed earlier, then answer how you might implement them. Please type your answer into doc/enhancements.txt (Note: you are NOT required to implement these 3 enhancements. We just want you think about how someone could implement these 3 enhancements) As in part 1, please make sure all the picture files are added in binary mode. Running validate6170 ps5 will verify whether your picture and text files are correctly added to the CVS repository. In your grading meeting, you will have an opportunity to demonstrate your program to your TA. You can bring your laptop computer, but you do not have to. If you don't have a laptop, tell your TA well ahead of time, so that your TA will try to arrange to have a computer present at the grading meeting.If you absolutely do not wish to use your code from PS4 in this problem set, please email, and we will give you a minimum graph implementation that should suffice for this problem set. Maps In order to make your job easier, Dr. Larry Rudolph and his group have generously supplied maps of each floor. These maps are in the PNG format which can be viewed by most of the popular image editors (GIMP, Windows Picture Viewer, etc). Notice that the scale varies from map to map, and is noted (in pixel/feet) on the top right corner of the image. Also note that the non-EECS floors are missing (6-9D); don't worry about filling these in. These PNG files are located in the input/maps subdirectory of your project. Graph Files Larry Rudolph also supplied a graph file for each of the maps. These graph files contain information about how one can move around in the Stata Center. The