Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ?

Let A be the What is the maximum value of x^TAx where the maximum is taken over all x that are the unit eigenvectors of A?

Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?

In the Spiral model of software development, the primary determinant in selecting activities in each iteration is

Which of the following systems is a most likely candidate example of a pipe and filter architecture ?

A processor takes 12 cycles to complete an instruction I. The corresponding pipelined processor uses 6 stages with the execution times of 3, 2, 5, 4, 6 and 2 cycles respectively. What is the asymptotic speedup assuming that a very large number of instructions are to be executed?

Which of the following input sequences for a cross-coupled R-S flip-flop realized with two NAND gates may lead to an oscillation?

The following circuit implements a two-input AND gate using two 2-1 multiplexers. What are the values of X₁, X₂, X₃ ?

Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?

Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.

        get_exclusive_access ( ) 
{ 
  if (critical _flag == FALSE) { 
      critical_flag = TRUE ; 
      critical_region () ; 
      critical_flag = FALSE; 
      } 
}

Consider the following statements. i. It is possible for both P1 and P2 to access critical_region concurrently. ii. This may lead to a deadlock.

Which of the following holds?

Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the best-fit strategy. The allocation requests are stored in a queue as shown below.

The time at which the request for J₇ will be completed will be

The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is

 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410. 

Consider the following statements about the timeout value used in TCP.
(i) The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of the connection.
(ii) Appropriate RTT estimation algorithm is used to set the timeout value of a TCP connection.
(iii) Timeout value is set to twice the propagation delay from the sender to the receiver.
Which of the following choices hold?

Consider a TCP connection in a state where there are no outstanding ACKs. The sender sends two segments back to back. The sequence numbers of the first and second segments are 230 and 290 respectively. The first segment was lost, but the second segment was received correctly by the receiver. Let X be the amount of data carried in the first segment (in bytes), and Y be the ACK number sent by the receiver. The values of X and Y (in that order) are

Consider the following two statements:
(i) A hash function (these are often used for computing digital signatures) is an injective function.
(ii) An encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?

The minimum positive integer p such that 3^p modulo 17 = 1 is

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute bⁿ mod m, 0≤b, n≤m?

A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of

Given below are HTML lines,

With reference to the HTML lines given above, consider the following statements.
(i) Clicking on the point <80, 75> does not have any effect.
(ii) The web browser can identify the area applicable to the mouse-click within the image and the subsequent action to be taken without additional responses from the web server.
(iii) The dots in the cgi-bin URL will be resolved by the web browser before it is sent to the web server.
(iv) The "fd.html" request when sent to the web server will result in a GET request.
Exactly how many of the statements given above are correct?

Consider the XML document fragment given below:

Consider the XPath expression: *[not (self)::TOC]
What would be the result of the given XPath expression when the current node is Book?

Which one of these first-order logic formula is valid?

The trapezoidal method is used to evaluate the numerical value of . Consider the following values for the step size h.

(i) 10^-2
(ii) 10^-3
(iii) 10^-4
(iv) 10^-5

For which of these values of the step size h, is the computed value guaranteed to be correct to seven decimal places. Assume that there are no round-off errors in the computation.

A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
(i) (0, 0) ∊ P.
(ii) (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P.
Consider the following ordered pairs:
(i) (101, 22)
(ii) (22, 101)
(iii) (145, 265)
(iv) (0, 153)
Which of these ordered pairs of natural numbers are contained in P?

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph?

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Consider n jobs J₁, J₂,......J_n such that job J_i has execution time t_i and a non-negative integer weight w_i. The weighted mean completion time of the jobs is defined to be , where T_i is the completion time of job J_i. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?

The function f is defined as follows:

int f (int n) {
       if (n <= 1) return 1;
       else if (n % 2  ==  0) return f(n/2);
       else return f(3n - 1);
} 

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
(i) isEmpty (Q) — returns true if the queue is empty, false otherwise.
(ii) delete (Q) — deletes the element at the front of the queue and returns its value.
(iii) insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:

void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
   i = delete(Q);
   f(Q);
   insert(Q, i);
  }
} 

Consider the C program given below:

#include 
int main ()    {
    int sum = 0, maxsum = 0,  i,  n = 6;
    int a [] = {2, -2, -1, 3, 4, 2};
    for (i = 0; i < n; i++)    {
            if (i == 0 || a [i]  < 0  || a [i] < a [i - 1])  {
                     if (sum > maxsum) maxsum = sum;
                     sum = (a [i] > 0) ? a [i] : 0;
            }
            else sum += a [i];
    }
    if (sum > maxsum) maxsum = sum ;
    printf ("%dn", maxsum);

} 

What is the value printed out when this program is executed?

Consider the following C program:

   #include 
   #define EOF -1
   void push (int); /* push the argument on the stack */
   int pop  (void); /* pop the top of the stack */
   void flagError ();
   
   int main ()
   {  int c, m, n, r;
      while ((c = getchar ()) != EOF)
      {     if  (isdigit (c) )
                 push (c);
            else if ((c == '+') || (c == '*'))
            {  m = pop ();
               n = pop ();
               r = (c == '+') ? n + m : n*m;
               push (r);
      }
      else if (c != ' ')
               flagError ();
             }
             printf("% c", pop ());
     } 

        5 2 * 3 3 2 + * + 

Consider the program below in a hypothetical language which allows global variable and a choice of call by reference or call by value methods of parameter passing.

int i ;
program main ()
{
    int j = 60;
    i = 50;
    call f(i,j);
    print i, j;
}
procedure f(x,y)
{           
    i = 100;
    x = 10;
    y = y + i ;
} 

Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping.

int i ;
program main ()
{
    i = 10;
    call f();
}

procedure f()
{   
    int i = 20;
    call g ();
}
procedure g ()
{   
    print i;
} 

Early binding refers to a binding performed at compile time and late binding refers to a binding performed at execution time. Consider the following statements:
i. Static scope facilitates w1 bindings.
ii. Dynamic scope requires w2 bindings.
iii. Early bindings w3 execution efficiency.
iv. Late bindings w4 execution efficiency.
The right choices of wl, w2, w3 and w4 (in that order) are

The floating point unit of a processor using a design D takes 2t cycles compared to t cycles taken by the fixed point unit. There are two more design suggestions D1 and D2. D1 uses 30% more cycles for fixed point unit but 30% less cycles for floating point unit as compared to design D. D2 uses 40% less cycles for fixed point unit but 10% more cycles for floating point unit as compared to design D. For a given program which has 80% fixed point operations and 20% floating point operations, which of the following ordering reflects the relative performances of three designs? (Di > Dj denotes that Di is faster than Dj)

Consider a Direct Mapped Cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order

3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24.  

The following expression was to be realized using 2-input AND and OR gates. However, during the fabrication all 2-input AND gates were mistakenly substituted by 2-input NAND gates.

(a.b).c + (a'.c).d + (b.c).d + a. d 

Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS.

(i) R1→Loc, Loc→R2 ≡ R1→R2, R1→Loc
(ii) R1→Loc, Loc→R2 ≡ R1→R2
(iii) R1→Loc, R2→Loc ≡ R1→Loc
(iv) R1→Loc, R2→Loc ≡ R2→Loc 

What is the final value stored in the linear feedback shift register if the input is 101101?

Load R1,Loc1;	 Load R1 from memory location Loc1
Load R2,Loc2;	 Load R2 from memory location Loc2
Add R1,R2,R1;	 Add R1 and R2 and save result in R1
Dec R2;	         Decrement R2
Dec R1;	         Decrement R1
Mpy R1,R2,R3;	 Multiply R1 and R2 and save result in R3
Store R3,Loc3;   Store R3 in memory location Loc3

(C012.25)_H – (10111001110.101)_B =

An error correcting code has the following code words:

00000000, 00001111, 01010101, 10101010, 11110000. 

A hard disk system has the following parameters:
Number of tracks = 500
Number of sectors/track = 100
Number of bytes /sector = 500
Time taken by the head to move from one track to adjacent track = 1 ms
Rotation speed = 600 rpm.
What is the average time taken for transferring 250 bytes from the disk ?

The line T in the following figure is permanently connected to the ground.

Which of the following inputs (X1 X2 X3 X4) will detect the fault?

The two grammars given below generate a language over the alphabet {x, y, z}

G1: S → x|z|xS|zS|yB
    B → y|z|yB|zB
G2: S → y|z|yS|zS|xB
    B → y|yS 

Which one of the following choices describes the properties satisfied by the strings in these languages?

Consider the following DFA in which s₀ is the start state and s₁, s₃ are the final states.

What language does this DFA recognize ?

Consider the grammar given below

S → x B | y A
A → x | x S | y A A
B → y | y S | y B B 

Consider the following strings.

(i) xxyyx
(ii) xxyyxy
(iii) xyxy
(iv) yxxy
(v) yxx
(vi) xyx 

Which of the above strings are generated by the grammar ?

Consider the following grammars. Names representing terminals have been specified in capital letters.

G1: stmnt → WHILE (expr) stmnt
    stmnt → OTHER
    expr → ID
G2: WHILE (expr) stmnt
    stmnt → OTHER
    expr → expr + expr
    expr → expr * expr
    expr → ID   

Which one of the following statements is true?

Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.

The automation which recognizes the language L(P) ∩ L(Q) is:

The following table shoes the time between failures for a software system

The reliability of the system for one hour of operation assuming an exponential model is

Given the following algorithm for sorting an array X of N numbers:

SUBROUTINE SORT(X,N)
   IF(N < 2)
       RETURN
   FOR(i=2 TO N INCREMENT BY 1)
     FOR(j=1 TO i INCREMENT BY 1) 
        IF (X[i] > X[j])
             CONTINUE
        TEMP X[i]
        X[i] = X[j]
        X[j] = TEMP
        END FOR
     END FOR
   END SUBROUTINE 

A good approximation of Halstead's estimated program length is

In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case.

The Branch coverage is

Consider the CPM activity chart where an arc connecting two milestones is labeled with a task identifier and the time taken in days. For example in order to go from A to B, task T1 takes 180 days. A dashed line depicts an additional dependency that is equivalent to a zero time task.

The set of activities that lie on the critical path are

Consider the following pseudo-code:

 IF ((A > B) AND (C > D)) THEN
       A = A + 1
       B = B + 1
       ENDIF

The cyclomatic complexity of the pseudo-code is

Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readers-writers problem, two binary semaphores mutex and wrt are used to obtain synchronization

wait (wrt)
writing is performed
signal (wrt)
wait (mutex)  
  readcount = readcount + 1
  if readcount = 1 then S1
S2
reading is performed
S3
  readcount = readcount - 1
  if readcount = 0 then S4 
signal (mutex) 

The values of S1, S2, S3, S4, (in that order) are

In a multi-user operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by :

A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a page fault, the probability of page being dirty is also p. It is observed that the average access time is 3 time units. Then the value of p is

The contents of the text file t1.txt containing four lines are as follows:

a1 b1
a2 b2
a3 b2
a4 b1 

The contents of the text file t2.txt containing five lines are as follows:

a1 c1
a2 c2
a3 c3
a4 c3
a5 c4 

Consider the following Bourne shell script:

awk - F''' {Print S1, S2} ' t1.txt |
while read a b ; do
            awk -v aV = Sa - v bV = Sb - F''
            'aV = = S1 (print aV, bV, S2 )'t2.txt
done 

Which one of the following strings will NOT be present in the output generated when the above script in run? (Note that the given strings may be substrings of a printed line.)

For the network given in the figure below, the routing tables of the four nodes A, E, D and G are shown. Suppose that F has estimated its delay to its neighbors, A, E, D and G as 8, 10, 12 and 6 msecs respectively and updates its routing table using distance vector routing technique.

In the waveform (a) given below, a bit stream is encoded by Manchester encoding scheme. The same bit stream is encoded in a different coding scheme in wave form (b). The bit stream and the coding scheme are

Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the first 20 time units is 6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5 respectively. The output capacity of multiplexer is 5000 bits per time unit. Then the average number of backlogged of packets per time unit during the given period is

A group of 15 routers are interconnected in a centralized complete binary tree with a router at each tree node. Router j communicates with router j by sending a message to the root of the tree. The root then sends the message back down to router j. The mean number of hops per message, assuming all possible router pairs are equally likely is

A broadcast channel has 10 nodes and total capacity of 10 Mbps. It uses polling for medium access. Once a node finishes transmission, there is a polling delay of 80 μs to poll the next node. Whenever a node is polled, it is allowed to transmit a maximum of 1000 bytes. The maximum throughput of the broadcast channel is

Consider a selection of the form σ_A≤100(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?

Consider the following two transactions: T₁ and T₂.

T1: read(A);
               read(B);
               if A=0 then B ← B+1;
               write(B);
T2: read(B);
               read(A);
               if B≠0 then A ← A-1;
               write(A); 
 
Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions? 
      

Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct.
(i) If A ↠ B and A ↠ C then A → BC
(ii) If A → B and A → C then A ↠ BC
(iii) If A ↠ BC and A → B then A → C
(iv) If A → BC and A → B then A ↠ C
Exactly how many of the above implications are valid?

Consider the following relation schemas:
b-Schema = (b-name, b-city, assets)
a-Schema = (a-num, b-name, bal)
d-Schema = (c-name, a-number)

Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation.

Consider the following query:

 Пc-name (σb-city = "Agra" ⋀ bal < 0 (branch ⋈ (account ⋈ depositor)  

Which one of the following queries is the most efficient version of the above query?

Consider the following clauses:
(i) Not inherently suitable for client authentication.
(ii) Not a state sensitive protocol.
(iii) Must be operated with more than one server.
(iv) Suitable for structured message organization.
(v) May need two ports on the serve side for proper operation.
The option that has the maximum number of correct matches is

Your are given the following four bytes :

 10100011         00110111         11101001         10101011  

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 

Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is t_p, while the transmission time of a frame is t_t. All other latencies can be neglected.
The maximum utilization of the token ring when t_t = 3 ms, t_p = 5 ms, N = 10 is

Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is t_p, while the transmission time of a frame is t_t. All other latencies can be neglected.
The maximum utilization of the token ring when t_t = 5 ms, t_p = 3 ms, N = 15 is:

Consider the sequence <x_n>, n>= 0 defined by the recurrence relation x_{n + 1} = c . x_n²- 2, where c > 0.
Suppose there exists a non-empty, open interval (a, b) such that for all x₀ satisfying a < x₀ < b, the sequence converges to a limit. The sequence converges to the value?

Consider the sequence <x_n>, n>= 0 defined by the recurrence relation x_{n + 1} = c. x_n²- 2, where c > 0.
For which of the following values of c, does there exist a non-empty open interval (a,b) such that the sequence x_n, converges for all x₀ satisfying a < x₀

(i) 0.25
(ii) 0.35
(iii) 0.45
(iv) 0.5

Consider the following expression

 ad' + (ac)' + bc'd 

Consider the following expression

 ad' + (ac)' + bc'd 

Let P₁, P₂,..... , P_n be n points in the xy-plane such that no three of them are collinear. For every pair of points P_i and P_j, let L_ij be the line passing through them. Let Lab be the line with the steepest gradient amongst all n(n -1)/2 lines.
Which one of the following properties should necessarily be satisfied?

Let P₁,P₂,…,P_n be n points in the xy-plane such that no three of them are collinear. For every pair of points P_i and P_j, let L_ij be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines.
The time complexity of the best algorithm for finding P_a and P_b is

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at truck number 180.
Which of the request sets will cause the head to change its direction after servicing every request assuming that the head does not change direction if there is a tie in SSTF and all the requests arrive before the servicing starts?

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180.
What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are 2048 and the head can start from any track?

Consider the B⁺ tree in the adjoining figure, where each node has atmost two keys and three links.

Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?

Consider the B⁺ tree in the adjoining figure, where each node has atmost two keys and three links.

Now the key K50 is deleted from the 8 tree resulting after the two insertions made earlier. Consider the following statements about the B tree resulting after this deletion.
(i) The height of the tree remains the same.
(ii) The node (disregarding the links) is present in the tree.
(iii) The root node remains unchanged (disregarding the links).
Which one of the following options is true?