CS 242 Fall 2011 : Assignment 2.2
CS 242 Fall 2011 : Assignment 2.2
This page last changed on Sep 26, 2011 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 10:00 AM on Wednesday, October 5th. 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. CEOs Woodley and Kamin have 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 five 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:
CEOs Woodley and Kamin have 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.
Your task here is given two cities in CSAir’s route network, find the shortest path by distance between those two cities. 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 cities 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). Please note, if you decided to find a version of the algorithm that is already written and cite it, you will not be penalized for plagiarism, but you will not get credit for this portion of the assignment, so please write your own implementation from scratch.
You will need to take in a source and destination city that CSAir services (you will need to check for this), and print out information about the route. You can assume that the shortest route by distance is the route you should calculate for here. 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:
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. For simplicity, we ignore things like the jet stream impact on aircraft speed.
In addition, passengers will experience some layover time while waiting at airports for connecting flights. CSAir has a relatively simple schedule for its flights to allow you to calculate this. 1 jet departs on each route in each direction exactly at 06:00 CST regardless of where the origin of the flight is. The two planes traveling opposite directions on the same route will meet exactly half way. Once the flight lands, there is a 60 minute layover period for the passengers to disembark, the plane to be cleaned and refueled, and to board the next flight. Exactly 60 minutes after the flight lands (rounding to the nearest minute), the plane takes off on the same route but in the opposite direction. The last flight of the day on each route is the first trip on each route to land after 22:00.
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. Flights that depart before 09:00 CST and after 17:00 CST automatically cost 15% more for the entire leg of the flight. If a passenger needs to stay overnight between flights on his route, CSAir has an exclusive deal with a major hotel chain that happens to have hotels at every airport CSAir serves. Hotel rooms cost an automatic $100 per night.
CSAir has decided that due to the economic upturn, CEOs Woodley and Kamin have decided to open up a new hub city in Champaign. They choose Champaign due to the impending closing of the institute of aviation there and only one other airline servicing the airport, so there is plenty of room for CSAir to move in. You have been provided with another json file that has all the data you need. Incorporate this new data into your application, so that it can read in multiple json files and merge them together into one route network. Ensure that none of the other functionality is broken. That is, the statistics and route maps you generated last week should be updated to reflect the new data.
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 five components of this assignment. All of your tests should pass when you complete the assignment.
|Document generated by Confluence on Feb 22, 2012 18:09|