In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to 25°C, the probability that it will rain in the afternoon is 0.4. The temperature at noon is equally likely to be above 25°C, or at/below 25°C. What is the probability that it will rain in the afternoon on a day when the temperature at noon is above 25°C?

For the set N of natural numbers and a binary operation f : N x N → N, an element z ∊ N is called an identity for f, if f (a, z) = a = f(z, a), for all a ∊ N. Which of the following binary operations have an identity?

1. f(x,y) = x + y - 3
2. f(x,y) = max(x, y)
3. f(x,y) = x^y

In the automaton below, s is the start state and t is the only final state.

Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?

In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string

S → aSa | bSb | a | b | ϵ 

Which regular expression best describes the language accepted by the non-deterministic automaton below?

Given a Boolean function f (x₁, x₂, …, x_n), which of the following equations is NOT true.

The addition of 4-bit, two’s complement, binary numbers 1101 and 0100 results in

Which of the following DMA transfer modes and interrupt handling mechanisms will enable the highest I/O band-width?

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

A problem in NP is NP-complete if

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

In the working-set strategy, which of the following is done by the operating system to prevent thrashing?
1. It initiates another process if there are enough extra frames.
2. It selects a process to suspend if the sum of the sizes of the working-sets exceeds the total number of available frames.

The process state transition diagram of an operating system is as given below.

Which of the following must be FALSE about the above operating system?

Consider the relations r₁(P, Q, R) and r₂(R, S, T) with primary keys P and R respectively. The relation r₁ contains 2000 tuples and r₂ contains 2500 tuples. The maximum size of the join r₁⋈ r₂ is :

Which of the following relational query languages have the same expressive power?
1. Relational algebra
2. Tuple relational calculus restricted to safe expressions
3. Domain relational calculus restricted to safe expressions

The cyclomatic complexity of the flow graph of a program provides

With respect to software testing, consider a flow graph G with one connected component. Let E be the number of edges, N be the number of nodes, and P be the number of predicate nodes of G. Consider the following four expressions:
1. E - N + P
2. E - N + 2
3. P + 2
4. P + 1
The cyclomatic complexity of G is given by

HELO and PORT, respectively, are commands from the protocols

Which of the following statements is TRUE?

Which of the following statement(s) is TRUE?
1. A hash function takes a message of arbitrary length and generates a fixed length code.
2. A hash function takes a message of fixed length and generates a code of variable length.
3. A hash function may give the same hash value for distinct messages.

Consider the following first order logic formula in which R is a binary relation symbol.

 ∀x∀y (R(x, y)  => R(y, x)) 

When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of N is

Let P, Q and R be sets let Δ denote the symmetric difference operator defined as PΔQ = (P U Q) - (P ∩ Q). Using Venn diagrams, determine which of the following is/are TRUE?
1. PΔ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)
2. P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)

What is the cardinality of the set of integers X defined below?
X = {n | 1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5}

Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is

What are the eigenvalues of the matrix P given below

Match the following iterative methods for solving algebraic equations and their orders of convergence.

The following definite integral evaluates to

Consider the regular grammar below

S → bS | aA | ϵ
A → aS | bA 

The Myhill-Nerode equivalence classes for the language generated by the grammar are

Which of the following statements about regular languages is NOT true?

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

Let L be a context-free language and M a regular language. Then the language L ∩ M is

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z₀, X} where Z₀ is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ₀) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z₀ and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ) 

The language accepted by the PDA is

In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.

S → aSAb | ϵ
A → bA | ϵ 

The grammar generates the language

The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map.

Which of the product terms given below is an essential prime implicant of the function?

The majority function is a Boolean function f(x, y, z) that takes the value 1 whenever a majority of the variables x, y, z and 1. In the circuit diagram for the majority function shown below, the logic gates for the boxes labeled P and Q are, respectively,

For a state machine with the following state diagram the expression for the next state S⁺ in terms of the current state S and the input variables x and y is

When multiplicand Y is multiplied by multiplier X = x_n-1x_n-2 ...x₀ using bit-pair recoding in Booth's algorithm, partial products are generated according to the following table.

The partial products for rows 5 and 8 are

Which of the following statements about relative addressing mode is FALSE?

The memory locations 1000, 1001 and 1020 have data values 18, 1 and 16 respectively before the following program is executed.

MOVI Rs, 1        ; Move immediate
LOAD Rd, 1000(Rs) ; Load from memory
ADDI Rd, 1000     ; Add immediate
STOREI 0(Rd), 20  ; Store immediate 

Which of the statements below is TRUE after the program is executed?

The data path shown in the figure computes the number of 1s in the 32-bit input word corresponding to an unsigned even integer stored in the shift register. The unsigned counter, initially zero, is incremented if the most significant bit of the shift register is

The micro-program for the control is shown in the table below with missing control words for micro-instructions I₁, I₂, ..... I_n.

The counter width (k), the number of missing micro-instructions (n), and the control word for micro-instructions I₂, ..... I_n are, respectively,

A cache line is 64 bytes. The main memory has latency 32 ns and bandwidth 1 GBytes/s. The time required to fetch the entire cache line from the main memory is

A computer system has a level-1 instruction cache (1-cache), a level-1 data cache (D-cache) and a level-2 cache (L2-cache) with the following specifications:

The length of the physical address of a word in the main memory is 30 bits. The capacity of the tag memory in the I-cache, D-cache and L2-cache is, respectively,

Which of the following sequences of array elements forms a heap?

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that

d(P) = 5 units f(P) = 12 units
d(Q) = 6 units f(Q) = 10 units
d(R) = 14 unit f(R) = 18 units 

Which one of the following statements is TRUE about the graph?

The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows

a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21

A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code?

110111100111010

Which one of the choices given below would be printed when the following program is executed?

#include 
struct test {
               int i;
               char *c;
}st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7, "brother"};
main ()
{ 
    struct test *p = st;
    p += 1;
    ++p -> c;
    printf("%s,", p++ -> c);
    printf("%c,", *++p -> c);
    printf("%d,", p[0].i);
    printf("%s n", p -> c);
}

#include 
void swap (int *x, int *y)
{
    static int *temp;
    temp = x;
    x = y;
    y = temp;
}
void printab ()
{
    static int i, a = -3, b = -6;
    i = 0;
    while (i <= 4)
    {
        if ((i++)%2 == 1) continue;
        a = a + i;
        b = b + i;
    }
    swap (&a, &b);
    printf("a =  %d, b = %d\n", a, b);
}
main()
{
    printab();
    printab();
}

Which one of the choices given below would be printed when the following program is executed?

#include 
int a1[] = {6, 7, 8, 18, 34, 67};
int a2[] = {23, 56, 28, 29};
int a3[] = {-12, 27, -31};
int *x[] = {a1, a2, a3};
void print(int *a[])
{
            printf("%d,", a[0][2]);
            printf("%d,", *a[2]);
            printf("%d,", *++a[0]);
            printf("%d,", *(++a)[0]);
            printf("%d/n", a[-1][+1]);
}
main()
{
             print(x);
}

The following function computes the value of ^mC_n correctly for all legal values m and n (m≥1,n≥0 and m>n)

 int func(int m, int n)
{
    if (E) return 1;
    else return(func(m - 1, n) + func(m - 1, n - 1));
}

In the above function, which of the following is the correct expression for E?

Match the following concepts and their best possible descriptions.

Concept:
(i) overloading
(ii) friend
(iii) constructor
(iv) protected
(v) this
(vi) inheritance
Descriptions:
A. allows to define a class to have a properties of another class
B. defining a set of similar functions
C. used in dereferncing
D. used to given a non - member function access to the private parts of body
E. a function which is automatically called when object is created
F. allows a derived class to have access to the private parts of the base
G. a pointer to the object associated with the current functions
H. used to obtain persistence

The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes P₁, P₂ and P₃ are given in the table below. Each process has a CPU burst followed by an I/O burst followed by another CPU burst. Assume that each process has its own I/O resource.

The multi-programmed operating system uses preemptive priority scheduling. What are the finish times of the processes P₁, P₂ and P₃ ?

Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corresponds to the number of free slots in the buffer and is initialized to N. The semaphore E corresponds to the number of elements in the buffer and is initialized to 0.

Producer Process                Consumer Process
Produce an item;                Wait(E);
Wait(F);                        Wait(S);
Wait(S);
Append the items to the buffer; Signal(S);
Signal(S);                      Signal(F);
Signal(E);                      Consume the item;  

Which of the following interchange operations may result in a deadlock?
1. Interchanging Wait (F) and Wait (S) in the Producer process
2. Interchanging Signal (S) and Signal (F) in the Consumer process

For each of the four processes P₁, P₂, P₃ and P₄. The total size in kilobytes (KB) and the number of segments are given below.

The page size is 1 KB. The size of an entry in the page table is 4 bytes. The size of an entry in the segment table is 8 bytes. The maximum size of a segment is 256 KB. The paging method for memory management uses two-level paging, and its storage overhead is P. The storage overhead for the segmentation method is S. The storage overhead for the segmentation and paging method is T. What is the relation among the overheads for the different methods of memory management in the concurrent execution of the above four processes?

The wait and signal operations of a monitor are implemented using semaphores as follows. In the following,
x is a condition variable,
mutex is a semaphore initialized to 1,
x_sem is a semaphore initialized to 0,
x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0,
next_count is the number of processes waiting on semaphore next, initially 0.
The body of each procedure that is visible outside the monitor is replaced with the following:

P(mutex); 
      ⋮
body of procedure 
      ⋮
if (next_count > 0)
    V(next);
else
    V(mutex); 

x_count = x_count + 1;
if (next_count > 0)
    V(next)
else
    V(mutex);
------------------------------------------------------------ E1;
x_count = x_count - 1; 

if (x_count > 0)
{
    next_count = next_count + 1;
    ------------------- E2;
    P(next),
    next_count = next_count - 1;
} 

A software program consists of two modules M₁ and M₂ that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are ‘repairable’ and so the program starts working again as soon as the repair is done. Assume that the mean time to failure (MTTF) of M₁is T₁ with a mean time to repair (MTTR) of R₁. The MTTF of M₂ is T₂ with an MTTR of R₂. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?

Consider the following structure chart diagram. The boxes have function names embedded in them, while the variables are indicated along the arcs.

Given below are a set of statements relevant to the above diagram.
I. F3 and F6 can be in the same module.
II. F4 and F6 can be in the same module.
III. A4 is both an output and a control variable.
IV. It is incorrect to pass A1 as data and use it as a control variable.
Which combination of these statements is TRUE?

Consider a relation R with five attributes V, W, X, Y, and Z. The following functional dependencies hold: VY → W, WX → Z, and ZY → V.
Which of the following is a candidate key for R?

In a database file structure, the search key field is 9 bytes long, the block size is 512 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a non-leaf node in a B⁺ tree implementing this file structure is

Consider the following XML DTD describing course information in a university:

<!ELEMENT Univ (Course+, Prof+)>
<!ELEMENT Course (Title, Eval*)>
<!ATTLIST Course Number ID #REQUIRED Instructor IDREF #IMPLIED>
<!ELEMENT Title (#PCDATA)>
<!ELEMENT Eval (#PCDATA)>
<!ATTLIST Eval Score CDATA #REQUIRED>
<!ELEMENT Prof EMPTY>
<!ATTLIST Prof Name ID #REQUIRED Teaches IDREF #IMPLIED>

What is returned by the following XQuery?

let $as := //@Score
for $c in /Univ/Course[Eval]
let $cs := $c/Eval?@Score
where min($cs) > avg($as)
return $c 

A router uses the following routing table:

A packet bearing a destination address 144.16.68.117 arrives at the router. On which interface will it be forwarded?

Suppose that it takes 1 unit of time to transmit a packet (of fixed size) on a communication link. The link layer uses a window flow control protocol with a window size of N packets. Each packet causes an ack or a nak to be generated by the receiver, and ack/nak transmission times are negligible. Further, the round trip time on the link is equal to N units. Consider time i > N. If only acks have been received till time i(no naks), then the goodput evaluated at the transmitter at time i(in packets per unit time) is

In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5-bit codeword. It is required that the codewords have at most 1 leading and at most 1 trailing zero. How many such codewords are possible?

A router has two full-duplex Ethernet interfaces each operating at 100 Mb/s. Ethernet frames are at least 84 bytes long (including the Preamble and the Inter-Packet-Gap). The maximum packet processing time at the router for wirespeed forwarding to be possible is (in micro­seconds)

A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of on-time to off-time, is 1:2. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is S₁. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is S₂. The values of S₁ and S₂ are, respectively,

On a wireless link, the probability of packet error is 0.2. A stop-and-wait protocol is used to transfer data across the link. The channel condition is assumed to be independent from transmission to transmission. What is the average number of transmission attempts required to transfer 100 packets?

A program on machine X attempts to open a UDP connection to port 5376 on a machine Y, and a TCP connection to port 8632 on machine Z. However, there are no applications listening at the corresponding ports on Y and Z. An ICMP Port Unreachable error will be generated by

A subnetted Class B network has the following broadcast address: 144.16.95.255. Its subnet mask

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is

Consider the following program module:

void swap(float* A1, float* A2)
{
    float temp;
    if (*A1 = = *A2) return;
    temp = *A1;
    *A1 = *A2;
    *A2 = temp;
    return;
} 

The program volume for the above module using Halstead's method is

Consider the following program module:

void swap(float* A1, float* A2)
{
    float temp;
    if (*A1 = = *A2) return;
    temp = *A1;
    *A1 = *A2;
    *A2 = temp;
    return;
} 

The program effort for the above module using Halstead's method is

Consider the following set of linear operations:
x + y/2 = 9
3x + y = 10
The value of the Frobenius norm for the above system of equations is:

Consider the following set of linear operations:
x + y/2 = 9
3x + y = 10
What can be said about the Gauss-Siedel iterative method for solving the above set of linear equations?

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R₀, R₁, R₂, R₃ and R₄ respectively, before the execution of the instruction sequence.

The number of Read-After-Write (RAW) dependencies, Write-After-Read( WAR) dependencies, and Write-After-Write (WAW) dependencies in the sequence of instructions are, respectively,

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R₀, R₁, R₂, R₃ and R₄ respectively, before the execution of the instruction

The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is

Let L be a regular language. Consider the constructions on L below:
I. repeat (L) = {ww | w ∊ L}
II. prefix (L) = {u | ∃v : uv ∊ L}
III. suffix (L) = {v | ∃u : uv ∊ L}
IV. half (L) = {u | ∃v : | v | = | u | and uv ∊ L}
Which of the constructions could lead to a non-regular language?

Let L be a regular language. Consider the constructions on L below:
(I) repeat (L) = {ww | w ∊ L}
(II) prefix (L) = {u | ∃v : uv ∊ L}
(III) suffix (L) = {v | ∃u uv ∊ L}
(IV) half (L) = {u | ∃v : | v | = | u | and uv ∊ L}
Which choice of L is best suited to support your answer above?

A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The critical path for the above project and the slack of P2 are, respectively,

A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The costs (in Rupees per day) of crashing the expected phase completion times for the four phases, respectively, are 100, 2000, 50, and 1000. Assume that the expected phase completion times of the phases cannot be crashed below their respective most likely completion times. The minimum and the maximum amounts (in Rupees) that can be spent on crashing so that ALL paths are critical are, respectively.

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available

What is the output of the following SQL query?

select D.dname
from Drivers D
where D.did in (
                 select R.did
                 from Cars C, Reserves R
                 where R.cid = C.cid and C.colour = 'red'
                 intersect
                 select R.did
                 from Cars C, Reserves R
                 where R.cid = C.cid and C.colour = 'green'
                )

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available

Let n be the number of comparisons performed when the above SQL query is optimally executed. If linear search is used to locate a tuple in a relation using primary key, then n lies in the range