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 J

_{1}, J_{2}, J_{3}, J_{4}and with corresponding deadlines: ( d_{1}, d_{2}, d_{3}, d_{4}) = (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

Tags :

GATE & PSU CSAlgorithmsJun 29GATE & PSU CS

Posted by: