Time Left - 15:00 mins

GATE CS 2022: Algorithm 4

Attempt now to get your rank among 241 students!

Question 1

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?

Question 2

Which of the following is correct statement?

Question 3

Consider a job scheduling problem with 4 jobs J1, J2, J3, J4 and with corresponding deadlines: ( d1, d2, d3, d4) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?

Question 4

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

Question 5

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?

Question 6

The problem of 0/1 Knapsack can be solved using
  • 241 attempts
  • 0 upvotes
  • 2 comments
Jun 29GATE & PSU CS

Posted by:

Priya UpadhyayPriya UpadhyayMember since Sep 2020
Priya Upadhyay
Share this quiz   |