[Solved] CSE310 Homework 5

Q1) (40 points) Suppose you are implementing a dynamic set of student records as a hash table. Each record has an integer key. Key can have values from 0 through 65,536 and no two records can have the same key values. In addition to the key, each record has following information.

Name:

GPA:

Academic level:

Even though the key can take a value between 0 and 65536, this university can have max 10000 students at a given time.

Hash Table Implementation Details:

Assume that the hash key is k mod m and using chaining in case of a collision. The size (m) of the hash table (T) is 1000. Also, you can assume that keys for student are generated using a random uniform distribution function and each key is unique.

Write a C or C++ program that Implements the hash table construction for the above scenario and then implement the following three functions

1. INSERT(T, x) // insert the student record x to the table
2. DELETE(T, x) // delete the student record x from the table
3. SEARCH(T, k) //search key k in the hash table

Q.2 [20 Pts] Graph Representation: Consider the following graph G and answer questions given below.

1. [10 Points] Represent the above graph using adj-matrix and adj-list techniques.

1. [10 Points] The following table shows all the graph algorithms that we have discussed in the class. Fill the second and third column indicating running time and the space requirement for each algorithm

Algorithm	Running Time	Space Requirements
BFS
DFS
Prim’s
Kruska’s
Dijkstra
Bellman-Ford

3. (15 points) Consider the graph G given below. Compute an MST of G using Prim’s algorithm. Specifically, list the edges selected into the tree in the correct order, and then draw the final MST. Must show all the intermediate steps for full credit

4. (15 points) Consider the graph G given in Problem 3 above. Compute an MST of G using Kruskal’s algorithm. Specifically, list the edges selected into the tree in the correct order, and draw the final MST. (You are encouraged to include all intermediate work, such as the results after doing each UNION operation, so that you can still receive partial credit if your final answer is incorrect.)
5. (20 Points) Consider the following Dijkstra’s algorithm discussed in the class and answer questions given below

DIJKSTRA(G, w, s) //G: directed with nonnegative edge weights INIT-SINGLE-SOURCE(G, s)

S = Ø

Q = G.V // Q is a priority queue which we

// initialize with all the nodes in V[G]

while Q is not empty do

u = EXTRACT-MIN(Q) S = S  {u}

for each v  Adj[u] do

RELAX(u, v, w

1. Use the algorithm above to find the shortest path from vertex 5 to all other vertices in the graph given below as using adjacency matrix. First draw the graph for the given matrix and the show each step clearly in finding the shortest path. Value 0 indicate that there is no direct path.

1 2 3 4 5 6

0 0 5 0 6 0 3 0 0 0 14 0 0 0 0 4 0 0 0 8 0 0 0 0 12 0 6 0 0 4 2 0 9 7 0 0

1. Now modify the Dijkstra’s so that it finds not only shortest paths, but also the compute the length of shortest paths and store them in a suitable data structure. Your data structure should return the shortest path distance from the source to any given node in O(1) time.
2. Can we use Dijkstra’s algorithm to find the shortest paths in a graph with negative edges? Explain your answer clearly.

SUBMISSION INSTRUCTIONS

Your C or C++ program for question 1 under the HW5 Q1 submission link a single PDF document with solutions to Questions 2- 5 under HW5 Q2-5 submission link