GATE PYQ

Algorithms

Q21.
Consider the following C functions: int f1(int n) { if(n == 0 || n == 1) return n; else return (2f1(n-1) + 3f1(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] = 2X[i]; Z[i] = 3X[i]; } return X[n] ; } The running time of f1(n) and f2(n) are

Q22.
Arrange the following functions in increasing asymptotic order: a. n^{1/3} b. e^n c. n^{7/4} d. n \log^9n e. 1.0000001^n

Q23.
Consider the following functions: f(n)=2^{n} g(n)=n! h(n)=n^{log n} Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Q24.
The time taken by binary search algorithm to search a key in a sorted array of n elements is

Q25.
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute b^n \bmod{m}, 0 \leq b, n \leq m ?

Q26.
Consider the following C code segment: int IsPrime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf("Not Primen"); return 0;} return 1; } Let T(n)denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

Q27.
In the following C function, let n\geqm. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?

Q28.
What is the Asymptotic Notation of the following recursive function: int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }

Q29.
Consider the following C-function: 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; } } Suppose we modify the above function foo() and store the values of foo (i), 0\leq i \lt n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:

Q30.
The Asymptotic Notation of computing the transitive closure of a binary relation on a set of n elements is known to be: