GATE CS Algorithms questions

Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ X[i] = Y[i-1] + Z[i-2]; Y[i] = 2 * X[i]; Z[i] = 3 * X[i]; } return X[n]; }

f1(8)

and

f2(8)

return …

Let

x_n

denote the number of binary strings of length

n

that contain no consecutive

0

s. The value of

x_5

is

The subset-sum problem is defined as follows. Given a set of

n

positive integers,

S = \{ a_1, a_2, a_3, \dots , a_n \}

, and positive integer

W

, is there a subset of

S

whose elements sum to

W

? A dynamic program for solving this problem uses a

\text{2-dimensional}

Boolean array,

X

, with

n

rows and

W+1

columns. …

The subset-sum problem is defined as follows. Given a set of

n

positive integers,

S = \{ a_1, a_2, a_3, \dots , a_n \}

, and positive integer

W

, is there a subset of

S

whose elements sum to

W

? A dynamic program for solving this problem uses a

\text{2-dimensional}

Boolean array,

X

, with

n

rows and

W+1

columns. …

Let

x_n

denote the number of binary strings of length

n

that contain no consecutive

0

s. Which of the following recurrences does

x_n

satisfy?

Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ X[i] = Y[i-1] + Z[i-2]; Y[i] = 2 * X[i]; Z[i] = 3 * X[i]; } return X[n]; } The running time of

f1(n)

…

We have a binary heap on

n

elements and wish to insert

n

more elements (not necessarily one after another) into this heap. The total time required for this is

Dijkstra's single source shortest path algorithm when run from vertex

a

in the above graph, computes the correct shortest path distance to

The subset-sum problem is defined as follows: Given a set

S

of

n

positive integers and a positive integer

W

, determine whether there is a subset of

S

whose elements sum to

W

. An algorithm

Q

solves this problem in

O(nW)

time. Which of the following statements is false?

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let

T(n)

be the number of comparisons required to sort

n

elements. Then

The minimum number of comparisons required to determine if an integer appears more than

\frac{n}{2}

times in a sorted array of

n

integers is

Consider the following functions:

f(n) = 2^n

g(n) = n!

h(n) = n^{\log n}

Which of the following statements about the asymptotic behavior of

f(n)

,

g(n)

and

h(n)

is true?

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:

The most efficient algorithm for finding the number of connected components in an undirected graph on

n

vertices and

m

edges has time complexity

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 …

Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any

n > 0

is:

Suppose the letters

a, \,b, \,c, \,d, \,e, \,f

have probabilities

\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}

, respectively. What is the average length of the Huffman code for the letters

a, \,b, \,c, \,d, \,e, \,f

?

Consider the DAG with

V = \{1,2,3,4,5,6\}

shown below. Which of the following is not a topological ordering?

Suppose the letters

a, \,b, \,c, \,d, \,e, \,f

have probabilities

\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}

, respectively. Which of the following is the Huffman code for the letter

a, \,b, \,c, \,d, \,e, \,f

?

Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let

T(n)

denote number of times the

for

loop is executed by the program on input

n

. Which of the following is TRUE?