Algorithms

Algorithms

Algorithms
| Algorithms |
Topic: Algorithms Tag: CS GATE 2009
Q.1
Let πbe a problem that belongs to the class NP. Then which one of the following is TRUE?
A. There is no polynomial time algorithm for πA
B. If πcan be solved deterministically in polynomial time, then P = NP
C. If πis NP-hard, then it is NP complete
D. πmay be undecidable
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.2
Consider the program below:
#include<stdio.h>
int fun (int n, int *fp)
{
int t, f;
if ( n<= 1)
{
*fp = 1;
return 1;
}
t = fun(n - 1, fp);
f = t+ * fp;
*fp = t;
return f;
}
int main( )
{
int x = 15;
printf (“%d\n”, fun (5, &x));
return 0;
}
The value printed is 
A. 6
B. 8
C. 14
D. 15
Answer : Option B
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.3
The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.4
In quick sort, for sorting n elements, the (n/4)th the smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Answer : Option B
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2015
Q.5
An unordered list contain n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
A. ϴ(nlog n)
B. ϴ(n)
C. ϴ(log n)
D. ϴ(1)
Answer : Option D
Explaination / Solution:

Consider first three element of the list, atleast one of them will be neither minimum nor maximum ϴ(1)

Workspace
Report
Topic: Algorithms Tag: CS GATE 2010
Q.6
What does the following program print? 
#include <stdio.h>
void f (int * p, int * g) {
p = q;
* p = 2;
}
int i = 0, j = 1;
int main ( ){
f(&i, & j);
print f ("%d %d \ n", i, j);
return 0;
}
A. 2 2
B. 2 1
C. 0 1
D. 0 2
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2015
Q.7
Consider the following function written the C programming language.
void foo (char *a) {
if (*a && *a ! = ' ') {
putchar (*a) ;
}
}
The output of the above function on input “ABCD EFGH” is
A. ABCD EFGH
B. ABCD
C. HGFE DCBA
D. DCBA
Answer : Option D
Explaination / Solution:


 if condition fails & returns controls 
DCBA will be pointed

Workspace
Report
Topic: Algorithms Tag: CS GATE 2011
Q.8
What does the following fragment of C-program print? char c[ ] = "GATE2011"; char *p =c; printf ("%s", p+p[3] - p[1]);
A. GATE2011
B. E2011
C. 2011
D. 011
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2015
Q.9
Given below are some algorithms, and some algorithm design paradigms

Match the above algorithms on the left to the corresponding design paradigm they follow. 
A. 1 - i, 2 - iii, 3 - i, 4 - v
B. 1 - iii, 2 - iii, 3 - i, 4 - v
C. 1 - iii, 2 - ii, 3 - i, 4 - iv
D. 1 - iii, 2 - ii, 3 - i, 4 - v
Answer : Option C
Explaination / Solution:

Dijkstra shortest path algorithm find next node by choosing minimum distance hence greedy approach. Floyd warshall always apply dynamic programming, once it saves a cost and in the next iteration it will change if this is minimum hence dynamic. Binary search always divide on two parts .Hence divide and conquer. Backtracking uses by DFS, one it will reach to dead end it will take back track.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2015
Q.10
 Suppose you are provided with the following function declaration in the C programming language 
int partition (int a [ ], int n); 
The function treats the first element of a [ ] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array , and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last elements of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the Kth smallest element in an array a [ ] of size n using the partition function We assume k ≤ n.
int kth _smallest (int a [ ], int n, int k)
{
int left _ end = partition (a,n);
if (left _ end + 1 == k) {
return a [left _ end];
}
if (left _ end + 1 > k) {
return kth _ smallest (__________________);
}else {
return kth_smallest (_______________________);
}
}
The missing argument lists are respectively
A. (a, left _ end,k) and (a + left _ end + 1, n - left _ end - 1, k - left _ end - 1)
B. (a, left _ end,k) and (a, n - left _ end - 1, k - left _ end - 1)
C. (a + left _ end + 1,n - left end - 1, k - left _ end - 1) and (a, left _ end, k)
D. (a, n - left_ end - 1, k - left _ end - 1) and (a, left _ end,k)
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report