Time Left - 10:00 mins
GATE 2020 : Algorithms Quiz 6
Attempt now to get your rank among 510 students!
Question 1
Maximum Spanning tree problem (MaxST) defined for a weighted Undirected Graph aims to compute the spanning tree of maximum weight. Longest path Problem (longP) in a weighted directed graph aims to compute path of maximum weight from a given source to given destination. Which of the following is correct?
Question 2
Assume priority queue in Dijkstra’s algorithm is implemented using a sorted link list and graph G (V, E) is represented using adjacency matrix. What is the time complexity of Dijkstra’s algorithm (Assume graph is connected)?
Question 3
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
Question 4
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
Question 5
Which among the following statements are incorrect in terms of Greedy approach?
Question 6
Consider the following weighted graph
Selection of edges using kruskals algorithm would be
- 510 attempts
- 2 upvotes
- 2 comments
Tags :
GATE & PSU CSAlgorithmsJun 25GATE & PSU CS