GATE CS 2018 - Algorithms Quiz 5 (Greedy Algorithms-1)

Attempt now to get your rank among 646 students!

Question 1

Dijkstra’s single source shortest path algorithm when run from vertex 'a' in the above graph, computes the correct shortest path distance to

• Aonly vertex a
• Bonly vertices a, e, f, g, h
• Conly vertices a, b, c, d
• Dall the vertices

Question 2

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

• ADijkstra’s algorithm starting from S
• BWarshall’s algorithm
• CPerforming a DFS starting from S
• DPerforming a BFS starting from S

Question 3

Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm?
P. Always finds a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

• AP only
• BQ only
• CBoth P and Q
• DNeither P nor Q

Question 4

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?

• AThere is a minimum spanning tree containing e.
• BIf e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
• CEvery minimum spanning tree has an edge of weight w .
• De is present in every minimum spanning tree.

Question 5

Which among the following statements are incorrect in terms of Greedy approach?

• AIt builds up a solution piece by piece and chooses the next piece.
• BIt is used for optimization problems.
• CIt is the best method of problem solving provided the algorithm can solve.
• DThe solution to the particular problem depends on solutions to smaller instances of the similar problem

• 646 attempts
• 4 upvotes
• 11 comments