Test: Greedy Method - Computer Science Engineering (CSE) MCQ

Since the access is sequential, greater the distance, greater will be the access time. Since all the files are referenced with equal frequency, overall access time can be reduced by arranging them as then ascending order of record as in option (a).

Dijkstra’s algorithm solves single source shortest path problem.
Warshall’s algorithm finds transitive closure of a given graph.
Prim’s algorithm constructs a minimum cost spanning tree for a given weighted graph.

In topological sorting we have to list out all the nodes in such a way that whenever there is an edge connecting i and j, i should precede j in the listing, For some graphs, this is not at all possible, for some this can be done in more than one way.

Kruskal’s algorithm time complexity
= O(e log v)
= O(m log n)

All edges are distinct weights.
Removal of e_max may not disconnect G, because other edges may cover the vertices incident with e_max.

Prim’s algorithm having special property which is, while finding minimum cost spanning tree, graph always be connected.

Now for correct options, we need to check while entry for any edge except for 1st edge only one vertex match from all left side (i.e. visited edges) edges.
(a) (E, G), (C, F ) : here for edge (C, F) no vertex match to (E, G). So not possible using Prim’s.
(b) (A, D), (A, B), (A, C), (C, F), (G, E ) : here for edge (G, E) no vertex match to any edge present left side of it so not possible using Prim’s.
(c) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) not violated rule i.e. always connected in construction of MST.
So True.

Bellman-Ford algorithm: O{nm)
Kruskal’s algorithm : O(mlog n)
Floyd-Warshall algorithm: O(n³)   

Topological sorting : O(n + m)

Correct answer is B. 
O ( ( | E | + |V| ) log |V I )

So, 3 minimum number of multiplications needed to evaluate p on an input x.

In the case of minimum spanning tree of a graph G we will add up to ( n - 1) vertices, so the weight of a minimum spanning tree of G