Description
Question 1 (10 points)
(a) (5 points) Starting with an empty 2-3 tree, perform the following operations on the
tree in the given order:
• Insert 2
• Insert 20
• Insert 6
• Insert 16
• Insert 10
• Delete 2
• Insert 12
• Insert 14
• Insert 8
• Delete 16
• Insert 18
• Insert 3
• Delete 6
• Delete 14
Show the underlying tree after each insertion and deletion.
(b) (5 points) Repeat part (a) for a 2-3-4 tree.
Question 2 (15 points)
(a) (5 points) Assume that we have a hash table with size 13 (index range is 0 . . . 12), and
we use
h(x) = x mod 13
as the hash function to map a given numeric key into this hash table. Assuming open
addressing with linear probing, draw the hash table after the insertion of the keys
45 64 54 17 69 58 32 60 26
in the given order.
Find the average number of probes for a successful search and an unsuccessful search
for the final hash table.
(b) (5 points) Repeat part (a) for open addressing with quadratic probing.
(c) (5 points) Repeat part (a) for separate chaining.
Page 2 of 5
Question 3 (75 points)
(a) You are asked to develop a driver program that allows an airline company to perform
some operations on a flight map.
• The flight map is represented as a weighted undirected graph where the vertices
correspond to the airports and the edges correspond to the flights between these
airports.
• The weight of each edge represents the duration of the flight.
• The operations to the program execution are provided by an input file.
• The first line of the input file contains an integer n, which is the number of airports.
• Each airport is denoted by an integer from 0 to n − 1, inclusive.
• The second line of the input file contains an integer m, which is the number of
operations.
• The following m lines are operations in the following format:
– opCode is a single character operation code, matching one of the operations
below.
– arguments is a single line of arguments for the related operation.
• Possible operations:
– Insertion:
opCode: I
arguments: u v w
Details: Inserts a two-way flight between two airports u and v. w is the
duration of the flight, represented as an integer. If there is a previous flight
between u and v, keep both.
Expected output:
Inserted a new flight between and
The number of flights from is
– List:
opCode: L
arguments: u
Details: Lists the flights from airport u.
Expected output:
List of flights from :
to
to
…
The number of flights is
Page 3 of 5
– Shortest Path:
opCode: S
arguments: s t
Details: Reports the shortest possible path from airport s to airport t.
Expected output:
The shortest path from to
to
…
Total flight duration of path:
or, if there is no path from s to t:
No paths from to
– Minimize Costs:
opCode: M
arguments: no arguments
Details: The company requests a cost minimization. Assume that the cost of a
two-way flight is equal to the duration. To minimize, they want to cancel some
of the flights, while also keeping the connectivity. If two airports are reachable
before the operation, they should also be reachable after the operation. This
operation should lead to the minimum possible cost under the constraints.
This operation should modify the underlying graph.
Expected output:
Total cost of operations before minimization:
Total cost of operations after minimization:
• The program should execute the operations one by one.
• The underlying graph should be an adjacency list implementation.
• You should provide an efficient implementation for each operation.
• The name of the executable of your program should be hw4.
• Your program should accept the path to the input file as a parameter to your
program, e.g. if the input file is in.txt in the same directory as the executable,
then the following command should execute your program:
hw4 in.txt
Page 4 of 5
Example Input File
5
12
I 0 1 2
I 0 2 3
I 0 4 6
I 1 2 6
S 2 3
I 3 4 3
S 2 3
I 1 3 6
L 2
S 2 3
M
L 2
Example Output
Inserted a new flight between 0 and 1.
The number of flights from 0 is 1.
Inserted a new flight between 0 and 2.
The number of flights from 0 is 2.
Inserted a new flight between 0 and 4.
The number of flights from 0 is 3.
Inserted a new flight between 1 and 2.
The number of flights from 1 is 2.
No paths from 2 to 3.
Inserted a new flight between 3 and 4.
The number of flights from 3 is 1.
Inserted a new flight between 1 and 3.
The number of flights from 1 is 3.
List of flights from 2:
2 to 1 with a duration of 6.
2 to 0 with a duration of 3.
The number of flights is 2.
The shortest path from 2 to 3:
2 to 0 with a duration 3
0 to 1 with a duration 2
1 to 3 with a duration 6
Total flight duration of path: 11
Total cost of operations before minimization: 26
Total cost of operations after minimization: 14
List of flights from 2:
2 to 0 with a duration of 3.
The number of flights is 1.
(b) Prepare a report and discuss the worst-case asymptotic complexities of your
implementation of operations.
Page 5 of 5