A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?

A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P(A') = 1/3, P(B') = 1/3. What is P(A ∪ B)?

What is the chromatic number of the following graph?

What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?

Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1’s?

Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

The following bit pattern represents a floating point number in IEEE 754 single precision format

 110000011101000000000000000000000

Consider the following Boolean function of four variables

 f(A,B,C,D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)

What Boolean function does the circuit below realize ?

Arrange the following functions in increasing asymptotic order:

A. n1/3
B. en
C. n7/4
D. n log9n
E. 1.0000001n

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

Which of the following is TRUE?

Match the programming paradigms and languages given in the following table.

Consider the execution of the following commands in a shell on a linux operating system.

system
bash$cat alpha
Mathematics
bash$in alpha beta
bash$ rm alpha
bash$cat >> beta << SAME
Information Technology
SANE
bash$ cat beta

A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be:

A paging scheme uses a Translation Look-aside Buffer (TLB). A TLB-access takes 10 ns and a main memory access takes 50 ns. What is the effective access time(in ns) if the TLB hit ratio is 90% and there is no page-fault?

Find if the following statements in the context of software testing are TRUE or FALSE.
(S1) Statement coverage cannot guarantee execution of loops in a program under test.
(S2) Use of independent path testing criterion guarantees execution of each loop in a program under test more than once.

How many bytes of data can be sent in 15 seconds over a serial link with baud rate of 9600 in asynchronous mode with odd parity and two stop bits in the frame?

Which of the following is TRUE only of XML but NOT HTML?

Provider the best matching between the entries in the two columns given in the table below:

Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.

Which of the following is the negation of [∀x, α →(∃y, β →(∀ u, ∃v, y))]

What is the probability that in a randomly chosen group of r people at least three people have the same birthday?

The exponent of 11 in the prime factorization of 300! is

In how many ways can b blue balls and r red balls be distributed in n distinct boxes?

Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication?

(S1) the set of real numbers
(S2) {(a+ib) | a and b are rational numbers}
(S3) {a+ib | (a2 + b2) ≤ 1}
(S4) {ia | a is real}

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be

Consider the following Hasse diagrams.

If M is a square matrix with a zero determinant, which of the following assertion(s) is(are) correct?

• (S1) Each row of M can be represented as a linear combination of the other rows

• (S2) Each column of M can be represented as a linear combination of the other columns

• (S3) MX = 0 has a nontrivial solution

(S4) M has an inverse

Consider the function f(x) = x² - 2x - 1. Suppose an execution of the Newton-Raphson method to find a zero of f(x) starts with an approximation x₀ = 2 0f x. What is the value of x₂, 'the approximation of x' that the algorithm produces after two iterations, rounded to three decimal places?

If f(x) is defined as follows, what is the minimum value of f(x) for x∊(0,2] ?

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?

Consider the following languages.

L1 = {ai bj ck | i = j, k ≥ 1}
L1 = {ai bj | j = 2i, i ≥ 0}

Consider a CFG with the following productions.

S → AA | B 
A → 0A | A0 | 1 
B → 0B00 | 1

Which of the following languages is (are) non-regular? L₁ = {0^m1ⁿ | 0 ≤ m ≤ n ≤ 10000} L₂ = {w | w reads the same forward and backward} L₃ = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

Consider the following two finite automata. M₁ accepts L₁ and M₂ accepts L₂.

Consider the following state diagram and its realization by a JK flip flop The combinational circuit generates J and K in terms of x, y and Q. The Boolean expressions for J and K are:

Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.

Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?

A non pipelined single cycle processor operating at 100 MHz is converted into a synchro­nous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is

Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.

The two numbers given below are multiplied using the Booth's algorithm.

Multiplicand : 0101 1010 1110 1110 
Multiplier: 0111 0111 1011 1101

If we use Radix Sort to sort n integers in the range [n^k/2, n^k], for some k>0 which is independent of n, the time taken would be?

When n = 2^2k for some k ≥ 0, the recurrence relation

 T(n) = √(2)T(n/2) + √n, T(1) = 1

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree?

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.

MBCAFHPYK
KAMCBYPFH
MABCKYFPH

Consider the following sequence of nodes for the undirected graph given below.

a b e f d g c
a b e f c g d
a d g e b c f
a d b c g e f

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys

 43 36 92 87 11 4 71 13 14

What is the output printed by the following C code?

# include 
int main ()
{
    char a [6] = "world";
    int i, j;
    for (i = 0, j = 5; i < j; a [i++] = a [j--]);
    printf ("%s\n", a);
}

Consider the C program below. What does it print?

# include 
# define swapl (a, b) tmp = a; a = b; b = tmp
void swap2 ( int a, int b)
{
        int tmp;
        tmp = a; a = b; b = tmp;
 }
void swap3 (int*a, int*b)
{
        int tmp;
        tmp = *a; *a = *b; *b = tmp;
}
int main ()
{
        int num1 = 5, num2 = 4, tmp;
        if (num1 < num2) {swap1 (num1, num2);}
        if (num1 < num2) {swap2 (num1 + 1, num2);} if (num1 >= num2) {swap3 (&num1, &num2);}
        printf ("%d, %d", num1, num2);
}

Consider the C program given below. What does it print?

#include 
int main ()
{
        int i, j;
        int a [8] = {1, 2, 3, 4, 5, 6, 7, 8};
        for(i = 0; i < 3; i++) { a[i] = a[i] + 1; i++; } i--; for (j = 7; j > 4; j--) {
              int i = j/2;
              a[i] = a[i] - 1;
        }
        printf ("%d, %d", i, a[i]);
}

C program is given below:

# include 
int main ()
{
        int i, j;
        char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}};
        char b [3] [2];
        char *p = *b;
        for (i = 0; i < 2; i++) {
              for (j = 0; j < 3; j++) {
              *(p + 2*j + i) = a [i] [j];
              }
        }
}

The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores equipped with the standard P and V operations.

semaphore S = 1, Q = 0; 
integer x; 
producer:                            consumer:
while(true) do                      while(true) do 
     P(S);                               P(Q); 
     x = produce ();                     consume (x); 
     V(Q);                               V(S); 
done                                done

An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:

If the time-slice used in the round-robin scheduling policy is more than the maximum time required to execute any process, then the policy will

Match the following flag bits used in the context of virtual memory management on the left side with the different purposes on the right side of the table below.

Which of the following are NOT considered when computing function points for a software project?

(O1) External inputs and outputs
(O2) Programming language to be used for the implementation
(O3) User interactions
(O4) External interfaces
(O5) Number of programmers in the software project
(O6) Files used by the system

A software project plan has identified ten tasks with each having dependencies as given in the following table:

         Task            Depends On 
          T1                 - 
          T2                T1 
          T3                T1 
          T4                T1 
          T5                T2 
          T6                T3 
          T7                T3, T4 
          T8                T4 
          T9                T5, T7, T8 
          T10               T6, T9 

Answer the following questions:
(Q1) What is the maximum number of tasks that can be done concurrently?
(Q2) What is the minimum time required to complete the project, assuming that each task requires one time unit and there is no restriction on the number of tasks that can be done in parallel?

A software engineer is required to implement two sets of algorithms for a single set of matrix operations in an object oriented programming language; the two sets of algo­rithms are to provide precisions of 10^-3 and 10^-6, respectively. She decides to implement two classes, Low Precision Matrix and High Precision Matrix, providing precisions 10^-3 and 10^-6 respectively. Which one of the following is the best alternative for the imple­mentation?

(S1) The two classes should be kept independent.
(S2) Low Precision Matrix should be derived from High Precision Matrix.
(S3) High Precision Matrix should be derived from Low Precision Matrix.
(S4) One class should be derived from the other; the hierarchy is immaterial.

Which of the following requirement specifications can be validated?

(S1) If the system fails during any operation, there should not be any loss of data
(S2) The system must provide reasonable performance even under maximum load conditions
(S3) The software executable must be deployable under MS Windows 95, 2000 and XP
(S4) User interface windows must fit on a standard monitor's screen

Let R (A, B, C, D) be a relational schema with the following functional dependencies: A → B, B → C, C → D and D → B.

The decomposition of R into (A, B), (B, C), (B, D)

Let R (A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies are known to hold:

AB → CD, DE → P, C → E, P → C and B → G.

Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following NYO represents the action Y (R for read, W for write) performed by transac­tion N on object O.]

(S1)	2RA	2WA	3RC	2WB	3WA	3WC	1RA	1RB	1WA	1WB
(S2)	3RC	2RA	2WA	2WB	3WA	1RA	1RB	1WA	1WB	3WC
(S3)	2RA	3RC	3WA	2WA	2WB	3WC	1RA	1RB	1WA	1WB

A 1Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is 3 × 10⁸ m/s. What should be the packet size for a channel utilization of 25% for a satellite link using go-back-127 sliding window protocol? Assume that the acknowledgment packets are negligible in size and that there are no errors during communication.

The minimum frame size required for a CSMA/CD based computer network running at 1 Gbps on a 200 m cable with a link speed of 2 × 10⁸ m/s is

Data transmitted on a link uses the following 2D parity scheme for error detection: Each sequence of 28 bits is arranged in a 4×7 matrix (rows r₀ through r₃, and columns d₇ through d₁) and is padded with a column d₀ and row r₄ of parity bits computed using the Even parity scheme. Each bit of column d₀ (respectively, row r₄) gives the parity of the corresponding row (respectively, column). These 40 bits are transmitted over the data link. The table shows data received by a receiver and has n corrupted bits. What is the minimum possible value of n?

Two popular routing algorithms are Distance Vector(DV) and Link State (LS) routing. Which of the following are true?

• (S1) Count to infinity is a problem only with DV and not LS routing

• (S2) In LS, the shortest path algorithm is run only at one node

• (S3) In DV, the shortest path algorithm is run only at one node

(S4) DV requires lesser number of network messages than LS

Which of the following statements are TRUE?

• (S1) TCP handles both congestion and flow control

• (S2) UDP handles congestion but not flow control

• (S3) Fast retransmit deals with congestion but not flow control

(S4) Slow start mechanism deals with both congestion and flow control

The three way handshake for TCP connection establishment is shown below.

Which of the following statements are TRUE? (S1) Loss of SYN + ACK from the server will not establish a connection (S2) Loss of ACK from the client cannot establish the connection (S3) The server moves LISTEN → SYN_RCVD → SYN_SENT → ESTABLISHED in the state machine on no packet loss (S4) The server moves LISTEN → SYN_RCVD → ESTABLISHED in the state machine on no packet loss.

The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key crypto-systems, respectively are:

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

 I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Which of the following statements is TRUE?

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

 I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

How many distinct BSTs can be constructed with 3 distinct keys?

Consider the following relational schema:

Student (school-id, sch-roll-no, sname, saddress)
School (school-id, sch-name, sch-address, sch-phone)
Enrolment(school-id, sch-roll-no, erollno, examname)
ExamResult(erollno, examname, marks)

What does the following SQL query output?

SELECT  sch-name, COUNT (*)
FROM    School C, Enrolment E, ExamResult R
WHERE   E.school-id = C.school-id
        AND
        E.examname = R.examname AND E.erollno = R.erollno
        AND
        R.marks = 100 AND S.school-id IN (SELECT school-id
                                FROM student
                                GROUP BY school-id
                                HAVING COUNT (*) > 200)
GROUP By school-id

Consider the following relational schema:

Student (school-id, sch-roll-no, sname, saddress)
School (school-id, sch-name, sch-address, sch-phone)
Enrolment(school-id, sch-roll-no, erollno, examname)
ExamResult(erollno, examname, marks)

Consider the following tuple relational calculus query:

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n₃ can be expressed as

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S → aS∣A
A → aAb∣bAa∣ϵ

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S → aS∣A
A → aAb∣bAa∣ϵ

Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. The number of bits in the TAG, SET and WORD fields, respectively are:

Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. While accessing the memory location 0C795H by the CPU, the contents of the TAG field of the corresponding cache line is

Consider the code fragment written in C below :

void f (int n)
{ 
  if (n <=1)  {
   printf ("%d", n);
  }
  else {
   f (n/2);
   printf ("%d", n%2);
  }
}

What does f(173) print?

Consider the code fragment written in C below :

void f (int n)
{
    if (n <= 1)  {
        printf ("%d", n);
    }
    else {
        f (n/2);
        printf ("%d", n%2);
    }
}

Which of the following implementations will produce the same output for f(173) as the above code?

P1
void f (int n)
{
    if (n/2)  {
        f(n/2);
    }
    printf ("%d", n%2);
}

P2 
void f (int n)
{
    if (n <=1)  {
        printf ("%d", n);
    }
    else {
        printf ("%d", n%2);
        f (n/2);
    }
}

Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to an­other host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP addresses 192.168.1.67 and 192.168.1.155. The netmask used in the network is 255.255.255.224. Given the information above, how many distinct subnets are guaranteed to already exist in the network?

Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to an­other host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP addresses 192.168.1.67 and 192.168.1.155. The netmask used in the network is 255.255.255.224. Which IP address should X configure its gateway as?