# CS GATE 2015 (Test 3)

Tag: cs gate 2015
Topic: Algorithms Tag: CS GATE 2015
Q.1
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 2015
Q.2
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 2015
Q.3
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.4
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
Topic: Algorithms Tag: CS GATE 2015
Q.5
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.6
Let R be the relation on the set of positive integers such that a aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
A. R is symmetric and reflexive but not transitive
B. R is reflexive but not symmetric and not transitive
C. R is transitive but not reflexive and not symmetric
D. R is symmetric but not reflexive and not transitive
Answer : Option D
Explaination / Solution:

R is not reflexive as each element can‟t be related to itself.
R is symmetric
Let a = 3, b = 6 and c = 10 then 3 and 6 have a common division other than 1
6 and 10 have a common division other than 1
but 3 &10 have no common division other than 1
3R6 and 6R10 but 3R10
R is not transitive

Workspace
Report
Q.7
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
A. In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding in N1.
B. For any input program, neither AST nor CFG will contain a cycle
C. The maximum number of successors of a node in an AST and a CFG depends on the input program
D. 4Each node is AST and CFG corresponds to at most one statement in the input program
Answer : Option C
Explaination / Solution:

Optional (A) is not true when CFG contains cycle Option (B) is false as CFG can contain cycle Option (D) is false as a single node can contain block of statements.

Workspace
Report
Q.8
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
A. Q1 is in NP, Q2 in NP hard
B. Q2 is in NP, Q1 is NP hard
C. Both Q1 and Q2 are in NP
D. Both Q1 and Q2 are NP hard
Answer : Option A
Explaination / Solution:

Workspace
Report
Q.9
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A. A tree has no bridges
B. A bridge cannot be part of a simple cycle
C. Every edge of a clique with size ≥ 3 is a bridge (A clique is any compete sub graph of a graph)
D. A graph with bridges cannot have a cycle
Answer : Option B
Explaination / Solution:

Since, every edge in a tree is bridge
(A) is false
Since, every edge in a complete graph kn (n ≥ 3) is not a bridge (c) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge „e‟ and a cycle of length „3‟
(D) is false
Since, in a cycle every edge is not a bridge
(B) is true

Workspace
Report
Q.10
Which one of the following assertions concerning code inspection and code walkthrough is true?
A. Code inspection is carried out once the code has been unit tested
B. Code inspection and code walkthrough are synonyms
C. Adherence to coding standards is checked during code inspection
D. Code walkthrough is usually carried out by an independent test team
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report