ALGORITHMS |Gate-2020|
1. For parameters a and b, both of which are Then T(n) is : [GATE – 2020]
a.
b.
c.
d.
Answer : a )
2. Let G = (V,E) be a directed, weighted graph with weight function w:E–> R. For some function f:V–> R, for each edge (u,v)E, define w'(u,v) as w(u,v)+f(u)-f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”. [GATE – 2020]
a. if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex
s to G and edges of zero weight from s to every vertex of G
b.
c.
d. for every f:V–> R
Answer : d)
ALGORITHMS |Gate-2020|
3. Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ε V x V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is : [GATE – 2020]
a.
b.
c.
d.
Answer : d)
4. Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is ______. [GATE – 2020]
a. 98
b. 99
c. 100
d. 101
Answer : b)
OS – GATE Previous Year Questions
DS – GATE Previous Year Questions