GATE CS Algorithms questions

Consider the following recursive C function that takes two arguments. unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; } What is the return value of the function

\text{foo}

when it is called as

\text{foo(513, 2)}

?

An undirected graph

G(V,E)

contains

n \: (n>2)

nodes named

v_1,v_2, \dots, v_n

. Two nodes

v_i, v_j

are connected if and only if

0 < \mid i-j\mid \leq 2

. Each edge

(v_i,v_j)

is assigned a weight

i+j

. A sample graph with

n=4

is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with

n

…

Consider the following recursive C function that takes two arguments. unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; } What is the return value of the function

\text{foo}

when it is called as

\text{foo(345, 10)}

?

Four Matrices

M_1, M_2, M_3

and

M_4

of dimensions

p \times q, \:\:q \times r, \:\:r \times s

and

s \times t

respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as

((M_1 \times M_2) \times (M_3 \times M_4))

, the total number of scalar multiplications is …

Which of the given options provides the increasing order of asymptotic complexity of functions

f_1, f_2, f_3

and

f_4

?

f_1(n) = 2^n

f_2(n) = n^{3/2}

f_3(n) = n \log_2 n

f_4(n) = n^{\log_2 n}

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array

A[0:n-1]

is given below. Let

L_i

, denote the length of the longest monotonically increasing sequence starting at index

i

in the array. Initialize

L_{n-1} = 1

. For all

i

such that

0 \leq i \leq n-2

…

Consider a complete undirected graph with vertex set

\{0, 1, 2, 3, 4\}

. Entry

W_{ij}

in the matrix

W

below is the weight of the edge

\{i, j\}

…

Consider a complete undirected graph with vertex set

\{0, 1, 2, 3, 4\}

. Entry

W_{ij}

in the matrix

W

below is the weight of the edge

\{i, j\}

…

What is the value printed by the following C program? #include<stdio.h> int f(int *a, int n) { if (n <= 0) return 0; else if (*a % 2 == 0) return *a+f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = {12, 7, 13, 4, 11, 6}; printf("%d", f(a, 6)); return 0; }

The weight of a sequence

a_0,a_1, \dots, a_{n-1}

of real numbers is defined as

a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}

. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let

X

denote the maximum possible weight of a subsequence of

a_o,a_1, \dots, a_{n-1}

and …

Two alternative packages

A

and

B

are available for processing a database having

10^k

records. Package

A

requires

0.0001 n^2

time units and package

B

requires

10n\log_{10} n

time units to process

n

records. What is the smallest value of

k

for which package

B

will be preferred over

A

?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences

X[m]

and

Y[n]

of lengths

m

and

n

, respectively with indexes of

X

and

Y

starting from

0

. We wish to find the length of the longest common sub-sequence (LCS) of

X[m]

and

Y[n]

as …

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences

X[m]

and

Y[n]

of lengths

m

and

n

, respectively with indexes of

X

and

Y

starting from

0

. We wish to find the length of the longest common sub-sequence (LCS) of

X[m]

and

Y[n]

as …

In quick-sort, for sorting

n

elements, the

\left(n/4\right)^{th}

smallest element is selected as pivot using an

O(n)

time algorithm. What is the worst case time complexity of the quick sort?

Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

The running time of an algorithm is represented by the following recurrence relation:

T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}

Which one of the following represents the time complexity of the algorithm?

Consider the program below: #include <stdio.h> int fun(int n, int *f_p) { int t, f; if (n <= 1) { *f_p = 1; return 1; } t = fun(n-1, f_p); f = t + *f_p; *f_p = t; return f; } int main() { int x = 15; printf("%d/n", fun(5, &x)); return 0; } The value printed is:

Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source.

What is the number of swaps required to sort

n

elements using selection sort, in the worst case?

Consider the following C program that attempts to locate an element

x

in an array

Y[ \ ]

using binary search. The program is erroneous. f (int Y[10] , int x) { int i, j, k; i= 0; j = 9; do { k = (i + j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] == x) printf(" x is in the array ") ; else printf(" x is …