BestTravel is a tourism company which decided to offer new service to its customers – better travel planning with airplanes around the world. The new system needs to be established, but there are no specialists. It was decided to organize the creation in 2 parts – 1) the creation of a conceptual solution; 2) the creation of a final solution according to the conceptual solution.
The company's most important desires:
- All airports are around the world, which could be up to 50 000. Employees will form or throw airports out of the system. Airports are constructed or eliminated rarely.
- Employees will enter information on each flight (flight identifier, airprot_from, airport_to, minimum price per person) or discard the flights that have been eliminated. One day there may be many flights between two airports, but flight identifiers are unique. Flight information may change frequently.
- You should be able to answer questions quickly:
- a. Can you get from airport X to airport Y?
- b. Where can I get from Airport X if there are N money units?
- c. What routes can be taken from the X airport, returning to the same airport and using no more than N money units?
Your job is to perform an analysis of the problem and create a conceptual design for the solution. It is desirable for the solution and description to be good and to be understood by any reasonably serious software development company.
Sales could be a set of multiple modules where the interface is realized with files for each module, i.e. the input data is in the file and the result of the operation of the module is written in the file.
The design or description of the task solution could contain the following parts:
- Input file. Description and examples of the format of the input file (s).
- Results file. Description and examples of the format of the output file (s).
- Possible solutions and their [theoretical] prove. At least at the level of idea, all the real solutions to the task should be presented as far as possible and should try to prove why they are doing the necessary task. For each option, mention its positive and negative sides. Show the paradigm of the algorithms that are used, if there are any.
- Chosen solution. The selected solution must be presented. The task solution algorithm must be described in an informal language if it is not already sufficiently explained in the previous paragraph. The essentials of the algorithm must be described in a formal way. The most important data structures and their use also should be described.
- An estimate of the complexity of the algorithm. The complexity of the algorithm for the most important parts of the algorithm, and the entire algorithm as a whole for both time and space, must be shown. Explain your algorithm assessment.
- Implementation and its assessment. Assess, as far as possible, the potential implementation of the project: How understandable would this solution be for another programmer? How easily and quickly can one be programmed? How quickly could the program work? How much memory would it require? etc.
- Various examples for the operation of the program: input data and output data. In fact, it could be a simple set of accepting tests. It is also desirable to provide guidance on how to prepare large tests (by volume of data) and make sure that the program works correctly on them.
You can choose a different work structure and additional ways of describing the problem and its solution. No standards are set. The above is what the I would like to see in the work.
The application interface, i.e. data formats in files must be easy to apply.
It is strongly recommended that you use diagrams/charts/images to display data structures, and to display the operation of an algorithm. It usually increases the readability of the work and therefore the grade.