Time Left - 15:00 mins

GATE 2019 - Algorithms Quiz-5 (Greedy Algo ) (App update required to attempt this test)

Attempt now to get your rank among 752 students!

Question 1

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

Question 2

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?

Question 3

Consider the already built heap (Max-Heap).
24, 20, 20, 7, 8, 9, 19, 1, 2
After root deletion operation, which of the following Max Heaps are valid.
1. 20, 8, 20, 7, 2, 9, 19, 1
2. 20, 20, 19, 7, 8, 9, 2, 1
3. 20, 20, 9, 7, 8, 2, 19, 1
4. 20, 7, 20, 2, 8, 9, 19, 1

Question 4

aaaabbbccddddddddee

What will be the maximum length of prefix code used for above sequence of letter in Huffman coding?

Question 5

What is time complexity of job sequencing with deadline(Using Greedy approach)?

Question 6

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
  • 752 attempts
  • 2 upvotes
  • 16 comments
Apr 5GATE & PSU CS