If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by A₁₅ to A₀. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

Which one of the following statements is NOT correct about the B⁺ tree data structure used for creating an index of a relational database table?

        #include <stdio.h>
        int main ()  {
                 int arr [] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr+4;
                 printf ("%d\n", ip[1]);
                 return 0;
        }

The number that will be displayed on execution of the program is _____.

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields resectively in the addresses generated by the processor?

Consider the following two statements about database transaction schedules:

I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas Write Rule can generate view serializable schedules that are not conflict serializable.

S → Aa
A → BD
B → b | ε
D → d | ε

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)

Let G be an arbitrary group. Consider the following relations on G:

      R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg
      R2: ∀a,b ∈ G, aR2b if and only if a = b-1

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ______.

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.

The process are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y–X is _______.

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.

Let X be a square matrix. Consider the following two statements on X.

I. X is invertible.
II. Determinant of X is non-zero.

For Σ = {a,b}, let us consider the regular language L = {x|x = a^2+3k or x = b^10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

Consider Z = X - Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

         #include <stdio.h>
         int jumble (int x, int y)  {
               x = 2 * x + y ;
               return x ;
         }
         int main ( )  {
               int x=2, y=5 ;
               y = jumble (y, x) ;
               x = jumble (y, x) ;
               printf ("%d \n", x) ;
               return 0 ;
         }

The following C program is executed on a Unix/Linux system:

            #include <unistd.h>
            int main ()
            {
                  int i ;
                  for (i=0; i<10; i++)
                         if (i%2 == 0) fork ( ) ;
                  return 0 ;
            }

Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|.

Consider the following relations P(X,Y,Z), Q(X,Y,T) and R(Y,V).

How many tuples will be returned by the following relational algebra query?

          ∏x(σ(P.Y=R.Y ∧ R.V=V2)(P × R)) - ∏x(σ(Q.Y=R.Y ∧ Q.T>2)(Q × R))

What is the minimum number of 2-input NOR gates required to implement a 4-variable function function expressed in sum-of-minterms form as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available.

Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?

Consider three 4-variable functions f₁, f₂ and f₃, which are expressed in sum-of-minterms as

f1 = Σ(0, 2, 5, 8, 14),  f2 = Σ(2, 3, 6, 8, 14, 15),  f3 = Σ(2, 7, 11, 14)

For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:

    S' → S
    S → 〈L〉 | id
    L → L,S | S

Let I₀ = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I₀ , 〈 ) is: _____.

  I. The smallest element in a max-heap is always at a leaf node
 II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree in Θ(n) time
 IV. A binary search tree can be constructed from a max-heap in Θ(n) time

In an RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also known that Φ(n) = 2880, where Φ() denotes Euler's Totient Function, then the prime factor of n which is greater than 50 is ______.

A relational database contains two tables Student and Performance as shown below:

The primary key of the Student table is Roll_no. For the Performance table, the columns Roll_no. and Subject_code together from the primary key. Consider the SQL query given below:

       SELECT S.Student_name, sum (P.Marks)
       FROM Student S, Performance P
       WHERE P.Marks > 84
       GROUP BY S.Student_name;

The number of rows returned by the above SQL query is _____.

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:

These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _____.

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is _____.

There are n unsorted arrays: A₁, A₂, ..., A_n. Assume that n is odd. Each of A₁, A₂, ..., A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, ..., A_n is

Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial 3x² + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place) _____.

       #include <stdio.h>
       int main()
       {
           int a[] = {2, 4, 6, 8, 10} ;
           int i, sum = 0, *b = a + 4 ;
           for (i = 0; i < 5; i++)
                 sum = sum + (*b - i) - *(b - i) ;
           printf ("%d\n", sum) ;
           return 0 ;
        }

Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS).

    I. Both Y and Z are in BCNF
   II. Decomposition of X into Y and Z is dependency preserving and lossless

∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))]

Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:

     S1.  {1, 2, 3, ..., 100}
     S2.  Set of all positive integers
     S3.  Set of all integers

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is ______ × 10⁶ bytes/sec.

    S1.  Set of all recursively enumerable languages over the alphabet {0,1}
    S2.  Set of all syntactically valid C programs
    S3.  Set of all languages over the alphabet {0,1}
    S4.  Set of all non-regular languages over the alphabet {0,1}

Consider the following grammar and the semantic actions to support the inheriteatd type declaration attributes. Let X₁, X₂, X₃, X₄, X₅ and X₆ be the placeholders for the non-terminals D, T, L or L₁ in the following table:

Which one of the following are the appropriate choices for X₁, X₂, X₃ and X₄?

Which one of the following languages over Σ = {a,b} is NOT context-free?

             #include <stdio.h>
             int r()  {
                    static int num=7 ;
                    return num-- ;
             }
             int main ()  {
                    for (r(); r (); r())
                           printf ("%d", r());
                    return 0 ;
             }

Which one of the following values will be displayed on execution of the programs?

Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?

               void convert (int n) {
                       if (n < 0)
                          printf ("%d", n);
                       else {
                          convert (n/2);
                          printf ("%d", n%2);
                       }
               }

Which one of the following will happen when the function convert is called with any positive integer n as argument?

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) ______ GB.

Consider the following snapshot of a system running n concurrent processes. Process i is holding X_i instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Y_i additional instances of R while holding the X_i instances it already has. Of the n processes, there are exactly two processes p and q such that Y_p = Y_q = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x₁ x₂ ... x_n ∈ Σⁿ, n ≥ 0. Let π(x) = x₁ º x₂ º ... º x_n.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

       #include <stdio.h>
       int main ()  {
          float sum = 0.0, j = 1.0, i = 2.0;
          while (i/j > 0.0625) {
               j = j + j;
               sum = sum + i/j;
               printf ("%f \n", sum);    
          }
          return 0;
       }

The number of times the variable sum will be printed, when the above program is executed , is ______.

I. G  has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G  has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Consider the following table

Match the algorithm to design paradigms they are based on:

/* This function computes the roots of a quadratic equation
           a.x^2 + b.x + c = . The function stores two real roots
           in *root1 and *root2 and returns the status of validity
           of roots. It handles four different kinds of cases.
           (i) When coefficient a is zero irrespective of discriminant
           (ii) When discreminant is positive
           (iii) When discriminant is zero
           (iv) When discriminant is negative.
           Only in case (ii) and (iii) the stored roots are valid.
           Otherwise 0 is stored in roots. The function returns
           0 when the roots are valid and -1 otherwise.
           The function also ensures root1 >= root2
              int get_QuadRoots( float a, float b, float c,
                 float *root1, float *root2);
        */

A software test engineer is assigned the job of doing black box testing. He comes up with the following test cases, many of which are redundant.

P. Requirements Capture	 1.Module Development and Integration
Q. Design	         2.Domain Analysis
R. Implementation	 3.Structural and Behavioral Modeling
S. Maintenance	         4.Performance Tuning

begin
  if (a== b) {S1; exit;}
  else if (c== d) {S2;]
       else {S3; exit;}
  S4;
end

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

Q1 : Select e.empId
     From employee e
     Where not exists
        (Select * From employee s where s.department = “5” and 
                                        s.salary >=e.salary)
Q2 : Select e.empId
     From employee e
     Where e.salary > Any
    (Select distinct salary From employee s Where s.department = “5”)

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

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

 awk - F '  '  ' {Print $1, $2} ' t1.txt |
while read a b ; do
            awk -v aV = $ a - v by = $b  - F ' '
            aV = = $1 (print aV, bV, $2 ) ' t2.txt
done

1. E - N + P
2. E - N + 2
3. P +  2
4. P + 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?

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

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

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

In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as