CSE ku CS homework

Pdf explains. use submission template

Homework 6
Due: Wednesday, July 5th by 11:59 pm Online.
50 Points
Submission: A Single PDF document with solutions to Questions 1- 4
Note: This is an individual submission, please do not collaborate
Q.1 [20 Pts] Graph Representation: Consider the following graph G and answer questions given below.
a) [10 Points] Represent the above graph using adj-matrix and adj-list techniques.
b) [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
BFS
DFS
Prim’s
Kruska’s
Dijkstra
Bellman-Ford
Running Time
Space Requirements
2. (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
3. (15 points) Consider the graph G given in Problem 2 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 must show all intermediate work, such as the results after doing each UNION operation, receive
full credit.)
SUBMISSION INSTRUCTIONS
Create a single PDF document with solutions to Questions 1- 4 under HW6 submission link
Homework 6: Submission Template
1. Your answer to question 1 part (a) here. Complete and correct
answer is needed to earn credit
Your answer to question 1 part (b) here. Complete and correct
answer is needed to earn credit.
2. Your answer to question 2 here. Must show all the intermediate
steps for full credit.
3. Your answer to question 3 here. Must show all the intermediate
steps for full credit.