Question 2 A) Given the graph G = (V,E) show (highlight on the graph) the Minimum Cost Spanning Tree and give its costs. Answer: Cost = Is it a unique MCST (Yes/No)? 8 11 - 3 1 2 5 1 2 4 3 2 B) Suppose you have a dense graph G with n vertices and m edges, where m >> n. The problem of finding the shortest path from every vertex to every other vertex (all-pairs shortest paths) can be solved either: i) By running Dijkstra's Greedy algorithm n times, each time starting from a different vertex, or ii) By running Floyd's Dynamic Programming algorithm once. Choose the most suitable algorithm(s) and data structure(s), and fill in the following table to justify your choice. Answer: Algorithm / Data structure n times Dijkstra with arrays In times Dijkstra with heaps One time Floyd Time complexity in terms of n (dense graph)

Question 2 A) Given the graph G = (V,E) show (highlight on the graph) the Minimum Cost Spanning Tree and give its costs. Answer: Cost = Is it a unique MCST (Yes/No)? 8 11 - 3 1 2 5 1 2 4 3 2 B) Suppose you have a dense graph G with n vertices and m edges, where m >> n. The problem of finding the shortest path from every vertex to every other vertex (all-pairs shortest paths) can be solved either: i) By running Dijkstra's Greedy algorithm n times, each time starting from a different vertex, or ii) By running Floyd's Dynamic Programming algorithm once. Choose the most suitable algorithm(s) and data structure(s), and fill in the following table to justify your choice. Answer: Algorithm / Data structure n times Dijkstra with arrays In times Dijkstra with heaps One time Floyd Time complexity in terms of n (dense graph)