CS 242 Fall 2011 : Assignment 2.2

This page last changed on Sep 26, 2011 by cemeyer2.

Assignment 2.2 – Expanding your routing software

This week, you will be expanding the software you built for CSAir last week to include several important new features.

Objectves:

  • Modify your existing design to accommodate new features
  • Learn about and implement Dijkstra’s algorithm
  • Work with JSON in reverse (write to JSON)

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.

Different Due Date Than Normal
Code is due on Wednesday for assignment 2.x, not Thursday. This is to facilitate code reading. Code reading will be posted each Wednesday morning at https://subversion.ews.illinois.edu/svn/sp11-cs242/_public/code_reading. Your moderator will assign whose code you will read each week, and that week in discussion, you will lead the discussion on that person’s code. To ensure a lively discussion, it is important that you read the assigned code and come prepared to section.

Background

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:

  1. Allow for online editing of the route network
  2. Saving the route network back to disk
  3. Displaying additional information about routes in the network
  4. Allow for finding the shortest route between two cities
  5. Allow for planning an itinerary for travelers
  6. Enhance the system to accommodate CSAir’s expansion

The Data

CSAir has provided you with a text file containing a representation of its route map in JSON format. You can get the given data here. This is the same data we gave you last week.

Your Task

This week’s assignment is split into five main components.

Online editing of the route network

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:

  1. Remove a city – be careful of side effects (what should you do with routes to/from a city if it is deleted)
  2. Remove a route
  3. Add a city, including all its necessary information
  4. Add a route, including all its necessary information
  5. Edit an existing city

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)

Saving the route network to disk

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.

Finding the shortest route between two cities

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.

Getting information about a route

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:

  • The total distance of the route
  • The cost to fly the route
  • The time it will take to travel the route
  • A detailed itinerary of the route (a listing of which flights at what time a passenger will need to take to get from his origin to his destination, you will also need to prompt the user to input the time of day which the passenger wishes to depart)
    • Remember to print out flight departure and arrival times in the timezone local to the origin and destination. The time zones are given in the JSON files. As a reference, CST is -6.

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.

Enhancing the system to accommodate CSAir’s expansion

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.

Challenge!

The challenge for this week is a multi-part one:

  1. Using the cost structure given above, augment it to account for a 3 class cabin on all aircraft. That is, calculate costs for economy, business, and first classes. The cost structure above is for economy pricing. Business class costs 20% more per flight. First class costs 35% more per flight.
  2. Add an option to your reservations system to print out a complete flight schedule for CSAir
  3. When the reservations system you designed produces an itinerary for a passenger, have it also produce several others that have the same source and destination but also:
    • Depart or arrive within an hour of the original routing or
    • Have a lower total cost than the original routing or
    • Have a shorter total travel time than the original routing

Testing

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.

Grading

Criteria Weight Comment
Basic preparation 1  
Cleverness 1  
Code submission 4 submitted on time for code reading and to the correct location, so that the code reading script could grab it
Decomposition 3  
Documentation 1  
Effort 2  
Naming 2  
Overall design 4  
Participation 2 How you critique others code.
Performance 1  
Presentation 2 How you critique your code.
Requirements – Additional JSON 2  
Requirements – Editing 2  
Requirements – JSON Serialization 2  
Requirements – Route Statistics 6  
Requirements – Shortest Path 4  
Code Reading 2  
Testing 3  

cmi_hub.json (application/json)
Document generated by Confluence on Feb 22, 2012 18:09

  1. No comments yet.

  1. No trackbacks yet.