GATE CS Algorithms questions

Practise Algorithms questions for GATE CS. Explore official PYQs and original subject-wise quizzes, check answers and view available solutions. Free, no sign-in.

Compare greedy choices, dynamic-programming states and graph algorithms. Identify the input size before analysing the time and space complexity of each solution.

20 on this page

SubjectTopicYearType

Consider the following recurrence relations: For all

n>1

\begin{array}{c} T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\ T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\Theta\left(\log _{2} n\right) \end{array}

Assume that for all

n \leq 1, T_{1}(n)=1

T_{2}(n)=1

. Which one of the following options is correct?

n

be an odd number greater than

100

. Consider a binary minheap with

n

elements stored in an array

P

whose index starts from

1

. Which of the following indices of

P

do/does NOT correspond to any leaf node of the minheap?

Consider a hash table

P[0,1, \ldots, 10]

that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is

h(x)=(x+7) \bmod 11

. Consider the following sequence of insertions performed on

P

\text{ 1,13, 22, 15, 11, } 24

Which of the following positions in the hash table is/are empty …

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with

23

\_\_\_\_

.(answer in integer)

P

be the set of all integers from

1

15

. Consider any order of insertion of the elements of

P

into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

G(V, E)

be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let

s \in V

G

u \in V

k \geq 0

d_{k}(u)

denote the weight of a shortest path (in terms …

G(V, E)

be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of

G

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph

G(V, E)

as input, where

d[v]

f[v]

are the discovery time and finishing time, respectively, of the vertex

v \in V

Consider the recursive functions represented by the following code segment: int bar(int n) { if (n == 1) return 0; else return 1 + bar(n/2); } int foo(int n) { if (n == 1) return 1; else return 1 + foo(bar(n)); } The smallest positive integer n for which

\mathrm{f} \circ \circ(\mathrm{n})

5

\_\_\_\_

. (answer in integer) Note: Ignore …

The following sequence corresponds to the preorder traversal of a binary search tree

T

50,25,13,40,30,47,75,60,70,80,77

The position of the element

60

in the postorder traversal of

T

\_\_\_\_

. (answer in integer) Note: The position begins with

1

Consider the following functions, where

n

is a positive integer.

n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)}

Which one of the following options lists the functions in increasing order of asymptotic growth rate? Note: Assume the base of log to be

2

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity

\Theta(n)

5,28,19,15,26,33,12,17,10

are inserted into a hash table using the hash function

h(k)=k \bmod 9

. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is

\_\_\_\_

. (answer in integer)

Consider an array

A=[10,7,8,19,41,35,25,31]

. Suppose the merge sort algorithm is executed on array

A

to sort it in increasing order. The merge sort algorithm will carry out a total of

7

merge operations. A merge operation on sorted left array

L

and sorted right array

R

is said to be void if the output of the merge operation is the …

G

be a weighted directed acyclic graph with

m

n

vertices. Given

G

and a source vertex

s

G

, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from

s

to all vertices that are reachable from

s

{G}?

Consider an array

A

of integers of size

n

. The indices of

A

1

n

. An algorithm is to be designed to check whether

A

satisfies the condition given below.

\forall i, j \in\{1, \ldots, n-1\}

i>j,(A[i+1]-A[i])>(A[j+1]-A[j])

Which one of the following gives the worst case time complexity of the fastest …

Consider a table

T

, where the elements

T[i][j], 0 \leq i, j \leq n

, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows: …

Consider a binary search tree (BST) with

n

(n>0)

. Given any node

V

, the key present in the node is denoted as

\operatorname{Val}(V)

. All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node

V

\operatorname{Suc}(V)

denote the node that is its inorder successor. If a …

G

be any undirected graph with positive edge weights, and

T

be a minimum spanning tree of

G

. For any two vertices,

u

v

d_{1}(u, v)

d_{2}(u, v)

be the shortest distances between

u

v

G

T

, respectively. Which ONE of the options is CORRECT for all possible

G, T, u

v

Consider the following recurrence relation:

T(n)=2 T(n-1)+n 2^{n} \text{ for } n>0, \quad T(0)=1

Which ONE of the following options is CORRECT?