Time Left - 15:00 mins

GATE 2022: Algorithms Quiz-6

Attempt now to get your rank among 259 students!

Question 1

In Prim's Algorithm we use heap data structure to know the order of vertices that should be visited and the time complexity is O((E+V)logE). But now consider modified Prim's algorithm in which sorted array is used as data structure, instead of heap to find minimum cost spanning tree. What will be time complexity for modified Prim's Algorithm, considering worst case ?

Question 2

Consider the following statements regarding Dijkstra's shortest path algorithm :
S1 : Dijkstra's Algorithm can be implemented on both directed and undirected graphs.
S2 : Dijkstra Algorithm provides shortest distance from every node to every other node.
S3 : Dijkstra Algorithm just provide the shortest distance , it doesn’t provide the path information.
Which of the above statements are correct ?

Question 3

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized Let G be a graph with V vertices and E edges. Let X be the time complexity of prim’s algorithm using array and y be the time complexity of prism algorithm using binary heap. What is the value of X and Y respectively?

Question 4

Consider the following graph:

Which one of the following represents the sequence of edges added in order to make a minimum spanning tree using Prim’s algorithm?

Question 5

What will be the change in the maximum time taken to sort the edges for ﬁnding MST using Kruskal’s algorithm when quick sort is used over heap sort. The number of edges in the graph are 32.

Question 6

Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights x, y
and z.

What is the maximum value of x+y+z?

259 attempts
0 upvotes
0 comments

Tags :

GATE & PSU CS Algorithms

Aug 10GATE & PSU CS