CS 242 Fall 2010 : Assignment 2.2

This page last changed on Oct 10, 2010 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 accomodate 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 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.

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/fa10-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. 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:

  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

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 four 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

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)

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.

Getting information about a route

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:

  • The total distance of the route
  • The cost to fly the route
  • The time it will take to travel the route

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.

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 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).

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 four 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 6 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 – Editing 3  
Requirements – JSON Serialization 3  
Requirements – Route Statistics 3  
Requirements – Shortest Path 3  
Code Reading 2  
Testing 3  
Document generated by Confluence on Feb 22, 2012 18:13

  1. No comments yet.

  1. No trackbacks yet.