CS 35

Final Project

Spring 2007 (Charles Kelemen)

due Friday 11 May at noon
NO LATES. Get me best you have by that date.
Each individual is responsible for this assignment. You may work in groups of two or three. But no excuses will be accepted concerning group dynamics, failure of some group member to perform, difficulty of meeting, etc. If you don't think you can compensate for these issues, work by yourself. This is doable alone. However, I think you will have more fun if you work in groups of two or three.

Look at the data file: /home/cfk/pub/cs35/project/airplane.txt

DO NOT PRINT IT. Save trees. It is a long file. If you want to print something, print shortairplane.txt which is 2 pages long and is enough to give you a complete idea of what the file looks like. If you feel that there are any conflicts in the file, take the material starting at line 100:
AA 748 ABQ 257P ATL 1047P S 1 S80 F Y M Q B
as authoritive.

1. Write a Java program that constructs a flight graph from the data in airplane.txt. Your program should be able to handle any file called airplane.txt that is in the same format so that I may check it with larger or smaller files in the same format. Your program should be standard Java. You may use Java Collections but you may not use Weiss's code directly. You may use Weiss's code for ideas but then credit Weiss and write your own code in standard Java. Your program should be able to interact with a user and do the following:
a. given a city A and a city B, determine if there is a direct flight from A to B.
b. given a city A, list all flights originating from city A.
c. given a city A, list all flights whose destination is city A.
d. insert a new city into the graph.
e. add new flights to the graph.
f. given a city A and a city B, find and display the itinerary with fewest flights to get from A to B, regardless of waiting time. In any intermediate airport, you must allow at least 30 minutes between an arrival and subsequent departure. Assume the data in airplane.txt includes all flights and is the same for every day. Time zones are important. No flight takes negative time. If it appears that a flight takes negative time, you must assume that the arrival time is on the next day and compute its elapsed time accordingly.
g. given a city A and a city B and a depart after time (DAT), find and display the itinerary that will leave city A after DAT and arrive at city B in the minimum total elapsed time. In any intermediate airport, you must allow at least 30 minutes between an arrival and subsequent departure. Assume the data in airplane.txt includes all flights and is the same for every day. Time zones are important. No flight takes negative time. If it appears that a flight takes negative time, you must assume that the arrival time is on the next day and compute its elapsed time accordingly.

Email to me by the due date (Friday, 11 May at noon) a message telling who is in your group and a tarball labeled with the first four letters of last name of one group member. In it you must include:
A) All your source code. If you work in a group, I want one copy with group names displayed early in each file. Source code should be clear and well-documented. The first comment, at the beginning of your files, should have your name(s) early. Each file should have a comment giving its file name.
B) A README file. If your program uses a Graphical User Interface, give me clear directions on how to start it and run it. Tell me in prose about some of the tests that you ran. If your program uses line oriented I/O, give me clear directions on how to start it and run it and provide scripts of at least 5 tests of each feature.
In any case, I should be able to compile your source and run your program. C) a short report labeled Report that includes
a. a description of your major data structures
b. time and space analysis for constructing the flight graph.
c. time analysis for each of the operations in 1.
d. a description of any assumptions, simplifications, and/or generalizations you have made.
e. a description of any special features of your implementation (e.g. gui interface, map,...) and how to run them.
f. reference to any help you received that was not a member of your group, Weiss, or me. (e.g. I got many ideas for this assignment from Iowa State.)

In order to get a B on this assignment, you must write nice, well-documented code, a nice report, complete 1a-1e, and do at least one of 1f or 1g.

In order to get an A, you must do above and both of 1f and 1g.

I hope this will be fun. Remember to start small and work in small increments for lots of CS highs.

--charles

Happy computing.