GATE PYQ

Algorithms

Q21.
Consider a carry lookahead adder for adding two n-bit integers,built using gates of fan-in at most two. The time to perform addition using this adder is

Q22.
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)); }

Q23.
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls,have O(1) Asymptotic Notation. If the worst case Asymptotic Notation of this functionis O(n^{\alpha }), then the least possible value(accurate upto two decimal positions) of \alpha is .

Q24.
Consider the equality \sum_{i=0}^{n}i^{3}=X and the following choices for X I. \Theta (n^{4}) II. \Theta (n^{5}) III. O (n^{5}) IV. \Omega (n^{3}) The equality above remains correct if X is replaced by

Q25.
Let f(n)=n and g(n)=n^{1+sin \; n} where n is a positive integer. Which of the following statements is/are correct? I. f(n)=O(g(n)) II. f(n)= \Omega (g(n))

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

Q27.
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is

Q28.
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

Q29.
Which of the given options provides the increasing order of asymptotic complexityoffunctions f1, f2, f3 and f4? f_{1}(n)=2^{n}; f_{2}(n)=n^{3/2}; f_{3}(n)=nlog_{2}n; f_{4}(n)=n^{log_{2}n}

Q30.
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