# Topic: Algorithms (Test 3)

Topic: Algorithms
Q.1
Consider the following two functions.
void funl (int n) {                        void fun2 (int n) {
if (n = =0 ) return;                            if (n = = 0) return ;
printf (“%d” , n);                               printf (“%d” , n);
fun2 (n - 2);                                     fun1(++n) ;
printf (“%d” , n);                               printf (“%d” , n);
}                                                       }
The output printed when fun1 (5) is called is
A. 53423122233445
B. 53423120112233
C. 53423122132435
D. 53423120213243
Explaination / Solution:

In this the fun1() is calling fun2() after printing value and after returning from fun2(),it prints the same value. In the fun2() also the same thing happens So by looking options we can judge the correct sequence of output.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.2
Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1;            /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2;               /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);

What output will be generated by the given code segment if:
Line 1 is replaced by auto int a = 1;
Line 2 is replaced by register int a = 2;
A. 3 1
4 1
4 2
B. 4 2
6 1
6 1
C. 4 2
6 2
2 0
D. 4 2
4 2
2 0
Explaination / Solution:

Static local variables: Scope is limited to function/block but life time is entire program.
Automatic local variables: Storage allocated on function entry and automatically deleted or freed when the function is exited. Register variables: Same as automatic variables except that the register variables will not have addresses Hence may not take the address of a register variable.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.3
Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1;            /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2;               /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);
What output will be generated by the given code segment?
A. 3 1
4 1
4 2
B. 4 2
6 1
6 1
C. 4 2
6 2
2 0
D. 3 1
5 2
5 2
Explaination / Solution:

Workspace
Report
Topic: Algorithms Tag: CS GATE 2010
Q.4
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};
print f ("%d", f(a, 6));
return 0;
}
A. -9
B. 5
C. 15
D. 19
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2013
Q.5
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
A. Θ(n2)
B. Θ(nlog n)
C. Θ(n3)
D. Θ(nlog n)
Explaination / Solution:

Bellman-ford time complexity: Θ(|V| × |E|)
For complete graph:  |E| = n(n - 1)/2
|V| = n
Θ(n × (n(n - 1)/2) = Θ(n3)

Workspace
Report
Topic: Algorithms Tag: CS GATE 2013
Q.6
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero(the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?
A. This algorithm is equivalent to the first-come-first-serve algorithm
B. This algorithm is equivalent to the round-robin algorithm
C. This algorithm is equivalent to the shortest-job-first algorithm
D. This algorithm is equivalent to the shortest-remaining-time-first algorithm