Consider the following functions
$$f(n) = 3{n^{\sqrt n }}$$
$$g(n) = {2^{\sqrt n {{\log }_2}n}}$$
$$h(n) = n!$$
Which of the following is true?

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true?

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?

The number of tokens in the following C statement is:

printf("i = %d, &i = %x",i, &i);

Comparing the time $$T1$$ taken for a single instruction on a pipelined $$CPU$$ with time $$T2$$ taken on a non-pipelined but identical $$CPU,$$ we can say that

An instruction pipeline has five stages where each stage takes $$2$$ nanoseconds and all instructions use all five stages. Branch instructions are not overlapped, i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ideal conditions.

(a) Calculate the average instruction execution time assuming that $$20$$% of all instruction executed are branch instructions. Ignore the fact that some branch instructions may be conditional.

(b) If a branch instruction is a conditional branch instruction, the branch need not be taken. If the branch is not taken, the following instructions can be overlapped. When $$80$$% of all branch instructions are conditional branch instructions, and $$50$$% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.

The most appropriate matching for the following pairs
$$X:$$ Indirect addressing
$$Y:$$ Immediate addressing
$$Z:$$ Auto decrement addressing is

$$1:$$ Loops
$$2:$$ Pointers
$$3.$$ Constants

A graphics card has on board memory of $$1$$ $$MB.$$ Which of the following modes can the card not support?

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverse the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where $$1 \le k < n:$$ reverse (s, 1, k);
reverse (s, k+1, k);
reverse (s, 1, n);

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

An n $$\times$$ n array v is defined as follows V [i, j] = i - j for all i, j, $$1 \le i \le n,\,1 \le j \le n$$ The sum of the elements of the array v is

In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

Given relations r( w, x ) and s( y, z ), the result of

select distinct w,x
from r, s;

is guaranteed to be same as r, provided

Given the relations

employee (name, salary, deptno), and
department (deptno, deptname, address)

Which of the following queries cannot be expressed using the basic relational algebra operations $$\left(\sigma, \pi,\times ,\Join, \cup, \cap,-\right)$$?

B⁺-trees are preferred to binary trees in databases because

Given the following relation instance
$$\eqalign{ & X\,\,\,\,\,Y\,\,\,\,\,Z \cr & \,\,1\,\,\,\,\,\,4\,\,\,\,\,\,2 \cr & \,\,1\,\,\,\,\,\,5\,\,\,\,\,\,3 \cr & \,\,1\,\,\,\,\,\,6\,\,\,\,\,\,3 \cr & \,\,3\,\,\,\,\,\,2\,\,\,\,\,\,2 \cr} $$

Which of the following functional dependencies are satisfied by the instance?

The following arrangement of master-slave flip-flop

Has the initial state of $$P, Q$$ as $$0, 1$$ (respectively). After three clock cycles the output states $$P, Q$$ is (respectively).

The number $$43$$ in $$2's$$ complement representation is

The simultaneous equations on the Boolean variables $$x, y, z$$ and $$w,$$ $$$x+y+z=1$$$ $$$xy=0$$$ $$$xz+w=1$$$ $$$xy + \overline z \overline w = 0$$$
have the following for $$x, y, z$$ and $$w,$$ respectively.

Which function does NOT implement the Karnaugh map given below?

A relation R is defined on the set of integers as zRy if f (x + y) is even. Which of the following statements is true?

Let P(S) denote the power set of a set S. Which of the following is always true?

$${{E_1}}$$ and $${{E_2}}$$ are events in a probability space satisfying the following constraints:
$$ \bullet $$ $$\Pr \,\,({E_1}) = \Pr \,({E_2})$$
$$ \bullet $$ $$\Pr \,\,({E_1}\, \cup {E_2}) = 1$$
$$ \bullet $$ $${E_1}$$ & $${E_2}$$ are independent

The value of Pr ($${E_1}$$), the probability of the event $${E_1}$$, is

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

The solution to the recurrence equation
$$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$,
$$T\left( 1 \right) = 1$$ is:

The determinant of the matrix $$$\left[ {\matrix{ 2 & 0 & 0 & 0 \cr 8 & 1 & 7 & 2 \cr 2 & 0 & 2 & 0 \cr 9 & 0 & 6 & 1 \cr } } \right]\,\,is$$$

An $$n\,\, \times \,\,n$$ array v is defined as follows v[i, j] = i - j for all i, j, $$1\,\, \le \,\,i\,\, \le \,\,n,\,1\,\, \le \,\,j\,\, \le \,\,n$$ The sum of elements of the array v is

A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it counting repetitions.

(a) what is the number of multisets of size 4 that can be constructed from n distinct elements so that at least one element occurs exactly twice?
(b) How many multisets can be constructed from n distinct elements?

Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otimes y = \left( {xy} \right)$$ mod $$8$$

(a) Prove that $$\left( {0,\,1,\, \otimes } \right)$$ is not a group.
(b) Write $$3$$ distinct groups $$\left( {G,\,\, \otimes } \right)$$ where $$G \subset s$$ and $$G$$ has $$2$$ $$\,\,\,\,\,\,$$elements.

Let $$a, b, c, d$$ be propositions. Assume that the equivalences $$a \leftrightarrow \left( {b \vee \neg b} \right)$$ and $$b \leftrightarrow c$$ hold. Then the truth value of the formulae $$\left( {a\, \wedge \,b} \right) \to \left( {\left( {a \wedge c} \right) \vee d} \right)$$ is always

Suppose the time to service a page fault is on the average $$10$$ milliseconds, while a memory access takes $$1$$ microsecond. Then a $$99.99$$% hit ratio results in average memory access time of.

Which of the following is NOT a valid deadlock prevention scheme?

Let m[0] ..m[4] be mutexes (binary semaphores) and P[0] ...P[4] be processes. Suppose each process P[i] executes the following:

wait (m[i]); wait (m(m[(i+1) mod 4]))0;
.......
release (m[i]); release (m[(i+1) mod 4]);

This could cause

The following C declarations

struct node{
  int i:
  float j;
};
struct node *s[10];

define s to be

The most appropriate matching for the following pairs

X: m=malloc(5); m= NULL;
Y: free(n); n->value = 5;
Z: char *p; *p='a';

1: using dangling
2: using uninitialized pointers
3. lost memory
is:

Consider the following C declaration

struct {
      short s[5];
      union {
      float y;
      long z;
      } u;
}t;

Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is

The value of j at the end of the execution of the following C program

int incr (int i)
{
     static int count = 0;
     count = count + i;
     return (count);
}
main () {
   int i,j;
   for (i = 0; i <= 4; i++)
   j = incr(i);
}

is

Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?

Let $$S$$ and $$T$$ be languages over $$\sum { = \left\{ {a,b} \right\}} $$ represented by the regular expressions $${\left( {a + {b^ * }} \right)^ * }$$ and $$\,{\left( {a + b} \right)^ * },$$ respectively. Which of the following is true?

What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has two states?

Consider the following decision problems :

$${P_1}$$ Does a given finite state machine accept a given string

$${P_2}$$ Does a given context free grammar generate an infinite number of stings.

Which of the following statements is true?