HW#2 – Comparison Shopping & Country PESTS Infographic 75 Points OVERVIEW: As a product developer, there are 2 keys points to successful product lines – know your customer (target market)….
An airline wants to store information on the cities it covers and which flights fly between these cities.
Question 1 (18 marks)
An airline wants to store information on the cities it covers and which flights fly between these cities. Assume that the flights have an identifying String ID. The information needed to be stored is the starting city and destination for each flight.
Your task is to decide what data structure/s would be best to store this information. This can include any of the data structures studied in the module, e.g. graphs, hash maps, trees, linked lists. When selecting a data structure, think about what operations the users might want to perform with the data, and which structures would be more efficient for these operations.
(a) Explain which data structure/s you chose and how it would store the information. Be as specific as possible, e.g. if you chose to use a graph, state clearly whether the graph will be implemented as an adjacency matrix or adjacency lists, or if you used a hash map, state what type the keys and values are. (4 marks)
(b) Show, with the aid of diagrams or tables if appropriate, how the information would be stored in your chosen structure. Your diagrams should contain at least 6 separate flights and at least 5 cities. (4 marks)
(c) Give two examples of operations that can be performed using your data structure. Here are some suggestions:
▪ Finding whether it is possible to travel from a given city A to a given city B, including travelling using several connections.
▪ Listing all the flights that travel directly between two given cities with no connections. ▪ Listing all the destination cities that this airline reaches.
▪ Listing all the flights that this airline runs.
▪ Listing all the cities that can be reached directly from a given city, i.e. the given city is
the starting city and the operation lists all the destinations from that starting city.
▪ Listing all the cities that can reach a given city, i.e. the given city is the destination and
the operation lists all the starting cities that have flights to that destination.
For each of the example operations you choose, explain how it would work using the data structure/s you chose and what time complexity it would have. (10 marks)