GATE CS 2022: Algorithm 4

Consider the following statement regarding Kruskal and Prim’s Algorithm for generating minimum spanning tree:

S1: While generating MST, it is possible to obtain forest during execution of the algorithm.

S2: The time complexity for generating MST is O (ElogE).

Which of the following is true for Kruskal algorithm but not Prim’s algorithm?

Which of the following is correct statement?

Consider a job scheduling problem with 4 jobs J₁, J₂, J₃, J₄ and with corresponding deadlines: ( d₁, d₂, d₃, d₄) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?

Huffman and other coding schemes tend to devote more bits to the coding of

Consider the following statements:

(i). Any Dynamic Programming algorithm with n subproblems will run in O(n) time.

(ii). Dynamic programming solves a problem faster then greedy method.

(iii). Unlike greedy algorithms, dynamic programming methods always provide correct/optimal solution.

Which of the above statement/s is/are correct?

The problem of 0/1 Knapsack can be solved using