GATE CSE topic:algorithms PYQs & Answers — Page 8

Questions 71–80 of 84. Imported answers require independent review unless marked reviewed.

Let

be any connected, weighted, undirected graph. I.

has a unique minimum spanning tree, if no two edges of

have the same weight. II.

has a unique minimum spanning tree, if, for every cut of

, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?

Your answerChoose one option.

I only

II only

Both I and II

Neither I nor II

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in T_B, then

. Which of the statements above must necessarily be true?

Your answerChoose one option.

I only

II only

Both I and II

Neither I nor II

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Assume that multiplying a matrix G_i of dimension p × q with another matrix G_j of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G_1G_2G_3...G_n can be done by parenthesizing in different ways. Define G_iG_ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G_1G_2G_3G_4G_5G_6 using parenthesization (G_1(G_2G_3))(G_4(G_5G_6)), G_2G_3 and G_5G_6 are the only explicitly computed pairs. Consider a matrix multiplication chain F_1F_2F_3F_4F_5, where matrices F_1, F_2, F_3, F_4 and F_5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F_1F_2F_3F_4F_5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Your answerChoose one option.

F_1F_2 and F_3F_4 only

F_2F_3 only

F_3F_4 only

F_1F_2 and F_4F_5 only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following directed graph G:

Diagram for Computer Science and Information Technology question 47

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _____.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the weights and values of items listed below. Note that there is only one unit of each item.

Item number	Weight (in Kgs)	Value (in Rupees)
1	10	60
2	7	28
3	4	20
4	2	24

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by

. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by

The value of

is __________.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Match the algorithms with their time complexities:

Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n²) (Q) Binary search given n sorted numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2ⁿ) (S) Addition of two n × n matrices (iv) Θ(log n)

Your answerChoose one option.

P → (iii), Q → (iv), R → (i), S → (ii)

P → (iv), Q → (iii), R → (i), S → (ii)

P → (iii), Q → (iv), R → (ii), S → (i)

P → (iv), Q → (iii), R → (ii), S → (i)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following functions from positive integers to real numbers:

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following table:

Algorithms	Design Paradigms
(P) Kruskal	(i) Divide and Conquer
(Q) Quicksort	(ii) Greedy
(R) Floyd-Warshal	(iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

Your answerChoose one option.

(P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i)

(P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii)

(P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)

(P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

Diagram for Computer Science and Information Technology question 15

Your answerChoose one option.

MNOPQR

NQMPOR

QMNROP

OQNMR

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be any connected undirected edge-weighted graph. The weights of the edges in

are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of

is always unique. (II) Shortest path between any two vertices of

is always unique.

Which of the above statements is/are necessarily true?

Your answerChoose one option.

(I) only

(II) only

both (I) and (II)

neither (I) nor (II)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE topic:algorithms PYQs

Question 38

Question 30

Question 31

Question 47

Question 48

Question 3

Question 4

Question 5

Question 15

Question 26