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

G=\left ( V,E \right )

any

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

E

are positive and distinct. Consider the following statements: Minimum Spanning Tree of

G

is always unique. Shortest path between any two vertices of

G

is always unique. Which of the above statements is/are necessarily true?

Consider the recurrence function

T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}

T(n)

\Theta

A message is made up entirely of characters from the set

X=\{P, Q, R, S, T\}

. The table of probabilities for each of the characters is shown below: …

Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } } Time complexity of

fun

\Theta

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?

Match the algorithms with their time complexities: …

G=(V, E)

is an undirected simple graph in which each edge has a distinct weight, and

e

is a particular edge of

G

. Which of the following statements about the minimum spanning trees

(MSTs)

G

is/are TRUE? If

e

is the lightest edge of some cycle in

G

, then every MST of

G

e

e

is the heaviest edge of some …

G

be a complete undirected graph on

4

vertices, having

6

edges with weights being

1, 2, 3, 4, 5,

6

. The maximum possible weight that a minimum weight spanning tree of

G

can have is __________

G

be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P

: Minimum spanning tree of

G

does not change.

Q

: Shortest path between any pair of vertices does not change.

Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.

The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are:

In an adjacency list representation of an undirected simple graph

G=(V, E)

(u, v)

has two adjacency list entries:

[v]

in the adjacency list of

u

[u]

in the adjacency list of

v

. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If

|E|=m

|V|=n

A_{1}, A_{2}, A_{3}

A_{4}

be four matrices of dimensions

10 \times 5, 5 \times 20, 20 \times 10

10 \times 5

, respectively. The minimum number of scalar multiplications required to find the product

A_{1}A_{2}A_{3}A_{4}

using the basic matrix multiplication method is _________.

The given diagram shows the flowchart for a recursive function

A(n)

. Assume that all statements, except for the recursive calls, have

O(1)

time complexity. If the worst case time complexity of this function is

O(n^{\alpha})

, then the least possible value (accurate up to two decimal positions) of

\alpha

is ________. Flow chart for Recursive …

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex

t

at a distance four from the root. If

t

n^{\text{th}}

vertex in this BFS traversal, then the maximum possible value of

n

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in

\Theta (n^2)

time Bubblesort runs in

\Theta (n^2)

time Mergesort runs in

\Theta (n)

time Insertion sort runs in

\Theta (n)

_{n}

represent the number of bit strings of length n containing two consecutive

1

s. What is the recurrence relation for

a_{n}

G = (V, E)

be a simple undirected graph, and

s

be a particular vertex in it called the source. For

x \in V

d(x)

denote the shortest distance in

G

s

x

. A breadth first search (BFS) is performed starting at

s

T

be the resultant BFS tree. If

(u, v)

G

T

, then which …

The graph shown below has

8

edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight

36

and contains the edges:

\{(A, C), (B, C), (B, E), (E, F), (D, F)\}

. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all

8

edges of this …