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

An algorithm performs

(\log N)^{\frac{1}{2}}

find operations ,

N

insert operations,

(\log N)^{\frac{1}{2}}

delete operations, and

(\log N)^{\frac{1}{2}}

decrease-key operations on a set of data items with keys drawn from a linearly ordered set . For a delete operation, a pointer is provided to the record that must be deleted . For the …

Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2) ++q; } return q; } Which one of the following most closely approximates the return value of the function

\text{fun1}

Match the following: …

Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting

n\;( \geq 2)

numbers? In the recurrence equations given in the options below,

c

Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of

a[\:]

as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right …

Given below are some algorithms, and some algorithm design paradigms. …

An unordered list contains

n

distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Consider the following C function. int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; } The return value of

fun(5)

c = \langle c[0], \dots, c[k-1]\rangle

is an array of length

k

, where all the entries are from the set

\{0, 1\}

. For any positive integers

a \text{ and } n

, consider the following pseudocode. DOSOMETHING (c, a, n) z ← 1 for i ← 0 to k-1 do z ← z² mod n if c[i]=1 then z ← (z × a) mod n return z If …

f(n) = n

g(n) = n^{(1 + \sin \: n)}

n

is a positive integer. Which of the following statements is/are correct?

f(n) = O(g(n))

f(n) = \Omega(g(n))

G

be a connected undirected graph of

100

300

edges. The weight of a minimum spanning tree of

G

500

. When the weight of each edge of

G

is increased by five, the weight of a minimum spanning tree becomes ______.

Consider the following recursive C function. void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); } If

get(6)

function is being called in

main()

then how many times will the

get()

function be invoked before returning to the

main()

Assume that a mergesort algorithm in the worst case takes

30

seconds for an input of size

64

. Which of the following most closely approximates the maximum input size of a problem that can be solved in

6

Consider the equality

\displaystyle{\sum_{i=0}^n} i^3 = X

and the following choices for

X

\Theta(n^4)

\Theta(n^5)

O(n^5)

\Omega(n^3)

The equality above remains correct if

X

Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3

Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i< size; i++) Y = Y + E[i]; for(i=0; i < size; i++) for(j = i; j < size; j++) { Z = 0; for(k = i; k <= j; k++) Z = Z + E[k]; if(Z > Y) Y = Z; } return Y; } The value returned …

The minimum number of comparisons required to find the minimum and the maximum of

100

numbers is ________

5

1

5

. All the coins in a given bag have the same weight. Some bags have coins of weight

10

gm, others have coins of weight

11

1, 2, 4, 8, 16

coins respectively from bags

1

5

Their total weight comes out to

323

gm. Then the product of the labels of the bags having

11

gm coins is …

Consider the directed graph below given. Which one of the following is TRUE?

P

be quicksort program to sort numbers in ascending order using the first element as the pivot. Let

t_1

t_2

be the number of comparisons made by P for the inputs

[1 \ 2 \ 3 \ 4 \ 5]

[4 \ 1 \ 5 \ 3 \ 2]

respectively. Which one of the following holds?