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)

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

Workspace

Report

Consider the following function written the C programming language.

**A. ** ABCD EFGH

**B. ** ABCD

**C. ** HGFE DCBA

**D. ** DCBA

**Answer : ****Option D**

**Explaination / Solution: **

void foo (char *a) {

if (*a && *a ! = ' ') {

putchar (*a) ;

}

}

The output of the above function on input “ABCD EFGH” is

if condition fails
& returns controls

DCBA will be pointed

Workspace

Report

Given below are some algorithms, and some algorithm design paradigms

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

Match the above algorithms on the left to the corresponding design paradigm they follow.

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

Suppose you are provided with the following function declaration in the C programming
language **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.

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 K^{th} 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

No Explaination.

Workspace

Report

The secant method is used to find the root of an equation f(x) = 0. It is started from
two distinct estimates x_{a} and x_{b} for the root. It is an iterative procedure involving
linear interpolation to a root. The iteration stops if f(x_{b}) is very small and then x_{b} 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?

**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

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

Secant method direct formula

Workspace

Report

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

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, N_{2} be the successor of node N_{1}. In the input program, the
code corresponding to N_{2} is present after the code corresponding in N_{1}.

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

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

Consider two decision problems Q_{1}, Q_{2} such that Q_{1} reduces in polynomial time to 3-SAT
and 3 -SAT reduces in polynomial time to Q_{2}. Then which one of following is consistent with
the above statement?

**A. ** Q_{1} is in NP, Q_{2} in NP hard

**B. ** Q_{2} is in NP, Q_{1} is NP hard

**C. ** Both Q_{1} and Q_{2} are in NP

**D. ** Both Q_{1} and Q_{2} are NP hard

**Answer : ****Option A**

**Explaination / Solution: **

Workspace

Report

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

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

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.

No Explaination.

Workspace

Report