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 functions

f(n) = 3n^{\sqrt{n}}

g(n) = 2^{\sqrt{n}{\log_{2}n}}

h(n) = n!

Which of the following is true?

Suppose you are given an array

s[1....n]

and a procedure reverse

(s, i, j)

which reverses the order of elements in

s

between positions

i

j

(both inclusive). What does the following sequence do, where

1 \leqslant k \leqslant n

: reverse (s, 1, k); reverse (s, k+1, n); reverse (s, 1, n);

S

be a sorted array of

n

T(n)

denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than

1000

S

. Which of the following statement is true?

The most appropriate matching for the following pairs

\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\ \hline \text{Y: breadth first search} & \text{2: queue} \\ \hline \text{Z: sorting} & \text{3: stack} \\ \hline \end{array}

Consider the following

C

function definition int Trial (int a, int b, int c) { if ((a>=b) && (c<b)) return b; else if (a>=b) return Trial(a, c, b); else return Trial(b, a, c); } The functional Trial:

T_1 = O(1)

, give the correct matching for the following pairs: …

n

2

, then the minimum number of multiplications needed to compute

a^n

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17

then the order of these elements after second pass of the algorithm is:

Suppose we want to arrange the

n

numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

A sorting technique is called stable if

The minimum number of record movements required to merge five files A (with

10

records), B (with

20

records), C (with

15

records), D (with

5

records) and E (with

25

What value would the following function return for the input

x=95

? Function fun (x:integer):integer; Begin If x > 100 then fun = x – 10 Else fun = fun(fun (x+11)) End;

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Give the correct matching for the following pairs: …

T(n)

be the function defined by

T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}

n \geq 2

. Which of the following statements is true?

The correct matching for the following pairs is …

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

1, 2, 3, \dots n

n, n-1, n-2, \dots, 2, 1

C_1

C_2

be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

The average number of key comparisons required for a successful search for sequential search on

n

The recurrence relation

T(1) = 2

T(n) = 3T (\frac{n}{4}) +n

has the solution

T(n)

Which of the following is false?