CS 242 Fall 2010 : Assignment 2.2
CS 242 Fall 2010 : Assignment 2.2
This page last changed on Oct 10, 2010 by cemeyer2.
This week, you will be expanding the software you built for CSAir last week to include several important new features.
Language: Continue working in the same language that you used last week, unless your moderator last week told you to switch languages.
Due Date and Submission: This assignment is due in Subversion at 8:00 AM on Wednesday, October 13th. This change is intentional, since we will be doing code reading for assignment 2.x. Please commit to a folder in SVN named Assignment2.2.
Being the superstar senior software engineer that you are, CSAir has decided that your work last week as impeccable and have asked you to add new features to the routing program you wrote for them last week. CEO Woodley has decided that in order to continue the development of the company, the software needs to be able to accommodate changes and be useful for travel agents. The new requirements for the software are:
This week’s assignment is split into four main components.
This component of the assignment requires you to write an interface that allows the user to do the following to the already constructed route network:
CEO Woodley has said that it is not up to you to verify correctness of any information that is added or edited, but you do need to sanity check inputs (no negative distances or populations, etc)
You will need to edit your software to allow the user to save their changes back to disk in JSON format. The format of the JSON file you generate must match the format of the input file you were given last week. That is, your code from last week should be able to load in the JSON you generate this week with no changes made to it.
We encourage you to use the JSON library that you used last week to help you. Many of these libraries allow you to build up a JSON type of object and then the library will convert it out to JSON for you. This way you do not need to worry about JSON syntax, just about the structure of the data.
You will need to take in a list of cities that form a valid route in the network (you will need to check for this), and print out information about the route. The information that needs to be printed must include:
In order to calculate the last two pieces of data, CEO Woodley has provided you with the following algorithms:
Cost: To calculate cost, the first leg of any flight will cost $0.35 per kilometer traveled. Each additional leg will cost $0.05 less per kilometer. If the cost for a leg of the route becomes free, keep the cost free for the rest of the route. This cost schedule is due to the fact that non-stop flights are preferable to customers, so we discount them if they stay on our airline even if it means taking more flights.
Time: CSAir operates a fleet of jets that all have a cruising speed of 750 kph. Each jet spends the first 200 kilometers of its flight uniformly accelerating from 0 kph to 750 kph, stays at 750 kph while it is cruising, and then decelerates uniformly from 750 kph to 0 kph during the last 200 kilometers of its flight. If a flight is less than 400 kilometers in distance, the jet accelerates uniformly for the first half of the flight and decelerates uniformly for the second half of the flight. In addition, passengers will experience some layover time while waiting at airports for connecting flights. The schedule to determine the layover time works as follows. The airport with the least number of outbound flights (1) has a layover time of 2 hours. For airports with 2 outbound flights, the layover time is 1hr 50min. Continue subtracting 10 minutes for each additional outbound flight that CSAir has from an airport to calculate its layover time.
Your task here is given two cities in CSAir’s route network, find the shortest path by distance between those two cities and print out the statistics about that route that we mentioned earlier. To do this, you will need to employ Dijkstra’s algorithm. The basic outline of the algorithm on Wikipedia does a good job of laying out the steps to perform it. You will probably need to modify your graph data structure to handle marking nodes as visited and assigning them distances. It is up to you to determine how to do this. Also, think about what other data structures you could use to improve the running time of this algorithm (hint…priority queue).
As usual, we require that you write extensive unit tests for each part of this assignment. We realize that testing a console interface is difficult, so it is acceptable to write unit tests for each of the functions that your library has.
You should have unit tests that thoroughly cover each of the four components of this assignment. All of your tests should pass when you complete the assignment.
|Document generated by Confluence on Feb 22, 2012 18:13|