GATE CSE Algorithms PYQs & Answers — Page 7

Questions 61–70 of 84. Imported answers require independent review unless marked reviewed.

Consider a double hashing scheme in which the primary hash function is

, and the secondary hash function is

. Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value

is ________.

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

Let

be a weighted, undirected graph and let

be a Minimum Spanning Tree (MST) of

maintained using adjacency lists. Suppose a new weighted edge

is added to

. The worst case time complexity of determining if

is still an MST of the resultant graph 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

Let

be a directed, weighted graph with weight function

. For some function

, for each edge

, define

. Which one of the options completes the following sentence so that it is TRUE? “The shortest paths in

under

are shortest paths under

too, ________.”

Your answerChoose one option.

for every

if and only if

is positive

if and only if

is negative

if and only if

is the distance from

in the graph obtained by adding a new vertex

and edges of zero weight from

to every vertex of $G

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

In a balanced binary search tree with

elements, what is the worst case time complexity of reporting all elements in range

? Assume that the number of reported elements 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 a graph

where

, and weight of the edge

. The weight of minimum spanning tree of

is ______.

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

Graph

is obtained by adding vertex

and making

adjacent to every vertex of

. The minimum number of colours required to edge-colour

is ______.

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

Let

be an undirected complete graph on

vertices, where

. Then the number of different Hamiltonian cycles in

is equal to

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

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ________.

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

Consider a sequence of 14 elements:

. The subsequence sum

. Determine the maximum of

, where

. (Divide and conquer approach may be used.)

Answer: ________.

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

There are

unsorted arrays:

. Assume that

is odd. Each of

contains

distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of

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

GATE CSE Algorithms PYQs

Question 23

Question 31

Question 40

Question 41

Question 49

Question 52

Question 12

Question 20

Question 25

Question 37