1 Crore+ students have signed up on EduRev. Have you? 
6 files F1, F2, F3, F4, F5and F6 have 100, 200, 50, 80, 120, 150 records respectively. In what order should they be stored so as to optimize act. Assume each file is accessed with the same frequency.
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).
Which of the following algorithms solves the all pair shortest path problem?
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.
Consider the graph in figure:
Which of the following is a valid topological sorting?
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 for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of
Kruskal’s algorithm time complexity
= O(e log v)
= O(m log n)
Let G be an undirected connected graph with distinct edge weights. Let e_{max} be the edge with maximum weight and e_{min} the edge with minimum weight. Which of the following statements is false?
All edges are distinct weights.
Removal of e_{max} may not disconnect G, because other edges may cover the vertices incident with e_{max}.
Consider the undirected graph below:
Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
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.
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
BellmanFord algorithm: O{nm)
Kruskal’s algorithm : O(mlog n)
FloydWarshall algorithm: O(n^{3})
Topological sorting : O(n + m)
Let G{V, E) an undirected graph with positive edge weights. Dijkstra’s single sourceshortest path algorithmn can be implemented using the binary heap data structure with time complexity?
Dijkstra’s implementation for single source shortest path
(i) Using binary heap takes
(ii) .Using Fibonacci heap takes
Consider the polynominal p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3}, where The minimum number of multiplications needed to evaluate p on an input x is
So, 3 minimum number of multiplications needed to evaluate p on an input x.
Consider a weighted complete graph G on the vertex set {v_{1}, v_{2}, .... v_{n}} such that the weight of the edge (v_{i}, v_{j}) is 2  i  j  .The weight of a minimum
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
61 videos7 docs102 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
61 videos7 docs102 tests





