Homework #4 Hashing and Graphs Solution

Question 1 – 15 points

    (a) [6 points] Insert f12; 15; 20; 30; 41; 29; 17; 25; 22g into an empty hash table which:

        ◦ uses linear probing for collision resolution.

        ◦ uses quadratic probing for collision resolution.

        ◦ uses separate chaining.

The size of each hash table is 13 and the hash function is: h(x) = x mod 13

    (b) [9 points] Find the average number of probes for a successful search and an unsuccess-ful search for the hash tables which you created in part a. Use the following numbers for unsuccessful searches: f0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 38g

Table 1: Average number of probes


Successful Search    Unsuccessful Search


Calculated    Theoretical    Calculated    Theoretical


Linear Probing

Quadratic Probing

Separate Chaining








Page 2
Fundamental Structures of Computer Science II



Question 2 – 70 points

In this part you will design and implement a flight database network system. You will use the dataset, routes.csv, provided with the homework.1 The dataset has the following format:

Dataset format

Airline, Source airport, Destination airport

Airline:  2 or 3-letter
code of the
airline.
Source airport:  3 or
4-letter code
of the source airport.
Destination airport:
3
or 4-letter
code of the destination airport.

In total, there are 67652 routes between 3425 airports in the dateset.

Sample entry:

TK,ESB,IST

The example above means that there is a direct flight from ESB (Ankara Esenboga Airport) to IST (Istanbul Ataturk Airport) operated by TK (Turkish Airlines).

Note: routes are directional: if an airline operates services from A to B and from B to A, both A-B and B-A are listed separately.

First create a class named FlightNetwork, put all related code into FlightNetwork.h and FlightNetwork.cpp files. In the constructor of the FlightNetwork class, you will read the provided dataset and store it in appropriate data structure (airports in the dataset will be vertices and flights will be directed edges in the graph). You should decide whether adjacency matrix or adjacency list fits best for the purpose of this assignment. You need to implement the following functionalities in FlightNetwork class.

    (a) [10 points] Checks if there are any direct flights from airport A to airport B. input: source airport, destination airport
output:  boolean

    (b) [10 points] Finds and prints all airports which are directly accessible from airport A. input: source airport

    (c) [10 points] Checks if there are any flight paths from airport A to airport B.

input:    source airport, destination airport

output:    boolean

    (d) [15 points] Finds and prints the flight path from airport A to airport B with the minimum number of stops. If there are multiple such paths, printing one of them is sufficient.

input:  source airport, destination airport


    • Retrieved from https://openflights.org/data.html#route and simplified.


Page 3
Fundamental Structures of Computer Science II



    (e) [15 points] Finds and prints all of the flight paths with n or lower number of stops from airport A to airport B. Go to the hint!
input:  source airport, destination airport, n

    (f) [10 points] In this part of the assignment, you will write a program which takes arguments from the command line and runs appropriate functions. The first argument defines which function will be run. If the first argument is a, then you will run part a. If it is b, then you will run part b and etc. The remaining arguments will be passed to the corresponding function. For example: if your program is called as

./hw4 d IST ESB

then in your main function, you should call the function in part d and provide IST and ESB parameters to it.

At the end, write a basic Makefile which compiles all your code and creates an ex-ecutable file named hw4. Check out these tutorials for writing a simple make file: tutorial 1, tutorial 2. Please make sure that your Makefile works properly on the dijkstra server.


Question 3 – 15 points

After implementing FlightNetwork class, you are expected to prepare a single page re-port.2 In your report, state which data structure (adjacency matrix or adjacency list) you used to store the graph and explain the reasoning behind your decision. And answer the following questions:

    • What would the time complexity (in terms of D - degree of source airport) of part a be if:

– adjacency matrix is used?

– adjacency list is used?

    • What is the worst case time complexity of part c in terms of jEj and jV j?

    • What is the worst case time complexity of part d in terms of jEj and jV j?

For time complexity calculations, show all your work clearly. Answers without expla-nations will not get any credits.


    • Please make sure that your report does not exceed the specified page limit, otherwise you may lose points







Page 4
Fundamental Structures of Computer Science II



Hint for Question 2 Part (e)

You can solve this problem by modifying the BFS algorithm. Instead of vertices, keep the paths in the queue.

    • Initial path is source airport, add this to the queue.

    • Then until queue is empty repeat the following:

– dequeue an element from the queue and assign it to currentPath

– set v to be the last element of currentPath

– if v ==  destination airport, then print currentPath

– visit each vertex u adjacent to v:

∗ if u is not in the currentPath, create a new path by combining currentPath and u, and add it to the queue













































Page 5