codingprolab@gmail.com

- Home
- Uncategorized
- CS 202 Homework #4 – Hashing and Graphs

$30.00

Category: Uncategorized

Description

5/5 - (2 votes)

Question 1 – 15 points

(a) [6 points] Insert {12, 15, 20, 30, 41, 29, 17, 25, 22} 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 unsuccessful search for the hash tables which you created in part a. Use the following numbers

for unsuccessful searches: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 38}

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

1Retrieved 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 executable 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 report.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 |E| and |V |?

• What is the worst case time complexity of part d in terms of |E| and |V |?

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

2Please 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

WhatsApp us