Topic: Algorithms (Test 2)



Topic: Algorithms
Topic: Algorithms Tag: CS GATE 2015
Q.1
The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method?
Initialize: xa, xb, ε, N                                 // ε = convergence indicator
fb = f(xb)
i = 0
while (i < N and | fb | > ε) do
i = i + 1                                                     // update counter
xt = ?                                                        // missing expression for // intermediate value
xa= xb                                                      // reset xa
xb = xt                                                      // reset xb
fb = f(xb)                                                  // function value at new xb
end while
if |fb| > ε then                                          // loop is terminated with i = N
write “Non-convergence”
else 
write “return xb” 
end if

A.  xb – (fb – f(xa)) fb / (xb – xa)
B. xa – (fa – f(xa)) fa / (xb – xa)
C. xb – (fb – xa) fb / (xb – fb (xa))
D.  xa – (xb – xa) fa / (fb – f (xa))
Answer : Option D
Explaination / Solution:

Secant method direct formula

Workspace
Report
Q.2
Consider the following C program.
void f(int, short);
void main()
{
int i = 100; 
short s = 12; 
short *p = &s; 
____________;        // call to f()  
}
Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error? 
A. f(s,*s)
B. i = f(i,s)
C. f(i,*s)
D. f(i,*p)
Answer : Option D
Explaination / Solution:

Here function f takes two arguments one is int and the other is short and its return type is void. So, in main function ‘P’ is a pointer to short and when we call f (i,*p) there won’t be any type checking error.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2011
Q.3
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 foo when it is called as foo (513, 2)? 
A. 8
B. 9
C. 5
D. 2
Answer : Option D
Explaination / Solution:



Workspace
Report
Topic: Algorithms Tag: CS GATE 2011
Q.4
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 foo when it is called as foo (345, 10) ?
A. 345
B. 12
C. 5
D. 3
Answer : Option B
Explaination / Solution:



Workspace
Report
Q.5
What will be the output of the following C program?
void count(int n){
static int d=1;
printf("%d ", n); printf("%d ", d); d++;
if(n>1) count(n-1);
printf("%d ", d);
}
void main(){
count(3);

A. 3 1 2 2 1 3 4 4 4
B. 3 1 2 1 1 1 2 2 2
C. 3 1 2 2 1 3 4
D. 3 1 2 1 1 1 2
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.6
Consider the following table:

Match the algorithms to the design paradigms they are based on.
A. P-(ii), Q-(iii),R-(i)
B. P-(iii), Q-(i), R-(ii)
C. P-(ii), Q-(i), R-(iii)
D. P-(i), Q-(ii), R-(iii)
Answer : Option C
Explaination / Solution:

Kruskal’s algorithm follows greedy approach in order to find MST of a connected graph. Quick sort follows divide and conquer strategy. Floyd Warshal algorithm is used to find the shortest path between every pair of vertices and it follows dynamic programming strategy.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.7
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?
A. A(n) = Ω(W(n))
B. A(n) = Θ(W(n))
C. A(n) = O(W(n))
D. A(n) = o(W(n))
Answer : Option C
Explaination / Solution:

The average case time can be lesser than or even equal to the worst case. So A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort). ∴A(n) = O(W(n))

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.8
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
A. T(n) = 2T(n - 2) + 2
B. T(n) = 2T(n - 1) + n
C. T(n) = 2T(n/2) + 1
D. T(n) = 2T(n - 1) + 1
Answer : Option D
Explaination / Solution:

Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1.move n−1 discs from A to B. This leaves disc n alone on peg A --- T(n-1) 2.move disc n from A to C---------1 3.move n−1 discs from B to C so they sit on disc n----- T(n-1) So, T(n) = 2T(n-1) +1

Workspace
Report
Q.9
Consider the C functions foo and bar given below:
int foo (int val ) {
int x = 0;
while (val > 0) {
x = x + foo ( val --);
}
return val ;
}
int bar (int val ) {
int x = 0;
while (val > 0) {
x = x + bar (val – 1) ;
}
return val ; 
}
Invocations of foo (3) and bar (3) will result in:  
A. Return of 6 and 6 respectively
B. Infinite loop and abnormal termination respectively.
C. Abnormal termination and infinite loop respectively.
D. Both terminating abnormally
Answer : Option B
Explaination / Solution:

Foo (3) calls foo (3) which in turn calls foo(3). This goes on infinite number of times which causes memory overflow and causes abnormal termination. Bar(3) → bar (2) →bar (1) →bar (0) (return 0) from here onwards bar (1) will call bar (0) and bar (0) will return 0 to bar (1) & this goes on forever without causing memory overflow.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.10
What will be the output of the following C program segment?
Char inChar = ‘A’ ;
switch (inChar ) {
case ‘A’ : printf (“Choice A\ n”);
case ‘B’ :
case ‘C’ : print f(“Choice B”);
case ‘D’ :
case ‘E’ :
default : printf (“No Choice”) ; }
A. No choice
B. Choice A
C. Choice A Choice B No choice
D. Program gives no output as it is erroneous
Answer : Option C
Explaination / Solution:

Since there is no ‘break’ statement , the program executes all the subsequent case statements after printing “choice A”

Workspace
Report