Introduction

Do not use the

Java built$-$in ADTs $-$ if in doubt, ask.

$**$

The assignment is based on the application of graph, hashing, sorting data structures. Read

carefully the following given problems. Your program should have an interactive menu to call

the necessary functions or methods and check for errors and exceptions.

Problem $1$: Implementing BFS for Route Discovery in an Airline Management System

Develop a Breadth$-$First Search $($BFS$)$ algorithm to discover all possible flight routes from a

given origin to a destination airport, considering a constraint on the number of allowed layovers

$($e$.$g$.,$ no more than two$).$ This task will simulate route finding in real$-$world scenarios where

direct flights are unavailable, or flexibility is needed due to peak travel times.

In airline systems, routes between airports can be represented as graphs, where nodes are

airports and edges are flights connecting these airports. BFS is an ideal algorithm for exploring

such graphs layer by layer, making it well$-$suited for finding all potential routes up to a certain

depth, corresponding here to the number of layovers.

$1\mathrm{.}1.$ Graph Representation: $[$marks $2]$

You are to represent the airline network as a graph using an adjacency list, where each node

$($airport$)$ holds a list of tuples. Each tuple represents a connecting flight and contains the

destination airport and the distance of the flight.

$1\mathrm{.}2.$ BFS Algorithm Implementation: $[$marks $4]$

Implement the BFS algorithm to traverse the graph from the origin airport to the destination

airport. The algorithm should explore all routes within the specified maximum number of

layovers.

Maintain a queue that holds tuples of the current airport, the current path taken $($list of airports

visited$),$ and the cumulative travel distance.

As you explore each airport $($node$),$ check all possible onward flights $($edges$).$ If the destination

is reached within the layover limits$,$ record the route; otherwise, continue to the next possible

airports.

$1\mathrm{.}3.$ Displaying the Results: $[$marks $4]$

For each valid route found, display the route in terms of the sequence of airports, the total

number of layovers, and the cumulative travel distance.

Ensure the results are clear and provide all necessary information for potential passengers to

understand their travel options.

Problem $2$: Hashing for Efficient Airport Lookup $[$marks $10]$

Implement a hashing mechanism to efficiently lookup airport information based on airport

codes. Suppose we have the following airport information:

Airport Code: MEL, Name: Melbourne Tullamarine $($MEL$)$

Airport Code: JFK$,$ Name: John F$.$ Kennedy International Airport

Airport Code: LAX, Name: Los Angeles International Airport

Airport Code: LHR$,$ Name: London Heathrow Airport

Airport Code: BKK$,$ Name: Bangkok Suvarnabhumi Airport

Students should implement a hash table where airport codes are used as keys to quickly retrieve

airport information following the instructions:

Design a hash function that converts airport codes into indices for the hash table. $[$marks $2]$

Implement collision resolution techniques with linear probing. $[$marks $2]$

Provide functions for inserting, searching, and deleting airport information from the hash table.

$[$marks $6]$

Problem $3$: Heap Sort for Optimal Route Selection $[$marks $10]$

After discovering all possible routes using BFS$,$ implement a heap sort algorithm to sort the

routes based on either total travel distance or the number of layovers. Allow passengers to

choose the optimal route based on their preference, whether it's minimizing layovers or

minimizing travel distance.

$3\mathrm{.}1$ Implementing Heap Sort: $[$marks $5]$

Heap sort is a comparison$-$based sorting algorithm that can efficiently sort routes based on total

travel distance or the number of layovers.

Instructions: $$

Implement the heap data structure to organize routes based on the selected criteria.

Utilize heap operations such as heapify to sort the routes in$-$place.

Ensure that the implementation handles both criteria $($total travel distance and number of

layovers$)$ effectively.

$3\mathrm{.}2.$ Allowing Passenger Preference: $[$marks $5]$

Enable passengers to choose the optimal route based on their preference, whether it's

minimizing layovers or minimizing travel distance.

Instructions:

Add one option in interactive menu to allow passengers to specify their preference for route

selection.

Implement logic to select routes based on the specified preference criteria and display the

result.

Further research option: $[$Option to get additional $10$ marks, which can be adjusted with

your total marks$]$

Compare the performance of heap sort with other sorting algorithms in terms of time