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

s

t

be two vertices in a undirected graph

G=(V,E)

having distinct positive edge weights. Let

[X,Y]

be a partition of

V

s \in X

t \in Y

. Consider the edge

e

having the minimum weight amongst all those edges that have one vertex in

X

and one vertex in

Y

. Let the weight of an edge

e

9

T_1, T_2, \dots, T_9

. The execution of each task requires one unit of time. We can execute one task at a time. Each task

T_i

P_i

d_i

P_i

is earned if the task is completed before the end of the

d_i^{th}

unit of time. …

s

t

be two vertices in a undirected graph

G=(V,E)

having distinct positive edge weights. Let

[X,Y]

be a partition of

V

s \in X

t \in Y

. Consider the edge

e

having the minimum weight amongst all those edges that have one vertex in

X

and one vertex in

Y

e

must definitely belong to:

double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } } The space complexity of the above code is?

G(V,E)

be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

T(n) =2T (\frac{n}{2}) + n

T(0) = T(1) =1

Which one of the following is FALSE?

Consider the following C-program: void foo (int n, int sum) { int k = 0, j = 0; if (n == 0) return; k = n % 10; j = n/10; sum = sum + k; foo (j, sum); printf ("%d,",k); } int main() { int a = 2048, sum = 0; foo(a, sum); printf("%d\n", sum); } What does the above program print?

An undirected graph

G

n

nodes. its adjacency matrix is given by an

n \times n

square matrix whose (i) diagonal elements are 0’s and (ii) non-diagonal elements are 1’s. Which one of the following is TRUE?

Suppose there are

\lceil \log n \rceil

sorted lists of

\lfloor n /\log n \rfloor

elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

The recurrence equation

T(1) = 1

T(n) = 2T(n-1) + n, n \geq 2

A[1,\ldots,n]

be an array storing a bit (

1

0

) at each location, and

f(m)

is a function whose time complexity is

\Theta(m)

. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if (a[i] == 1) counter++; else {f (counter); counter = 0;} } The complexity of this program fragment …

The time complexity of the following C function is (assume

n > 0

) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex

P

as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

Consider the following C program main() { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x>0 and y>0*/ m = x; n = y; while(m != n) { if (m > n) m = m-n; else n = n-m; } printf("%d", n); } The program computes

What does the following algorithm approximate? (Assume

m > 1, \epsilon >0

). x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x);

M_1

M_2

are to be stored in arrays

A

B

respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute

M_1 \times M_2

\text{3-SAT}

\text{2-SAT}

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

In a permutation

a_1\ldots a_n

n

distinct integers, an inversion is a pair

(a_i, a_j)

i < j

a_i > a_j.

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of

1. . . n

n

In the following

C

program fragment,

j

k

n

and TwoLog_n are integer variables, and

A

is an array of integers. The variable

n

is initialized to an integer

\geqslant 3

, and TwoLog_n is initialized to the value of

2^*\lceil \log_2(n) \rceil

for (k = 3; k <= n; k++) A[k] = 0; for (k = 2; k <= TwoLog_n; k++) for (j = k+1; j …