Consider the following C function.

Assume the following C variable declaration Of the following expressions I A[2] II A[2][3] III B[1] IV B[2][3] which will not give compile-time errors if used as left hand sides of assignment statements in a C program?    

Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, the values of P(A | B) and P(B | A) respectively are

Let T(n) be the number of different binary search trees on n distinct elements. Then  

For a pipelined CPU with a single ALU, consider the following situations

1. The j + 1-st instruction uses the result of the j-th instruction
    as an operand
2. The execution of a conditional jump instruction
3. The j-th and j + 1-st instructions require the ALU at the same 
   time

Which of the above can cause a hazard ?

Nobody knows yet if P = NP. Consider the language L defined as follows : Which of the following statements is true ?      

Consider the following three claims

1. (n + k)m = Θ(nm), where k and m are constants
2. 2n + 1 = O(2n)
3. 22n + 1 = O(2n)

Which of these claims are correct ?

Consider the following graph, Among the following sequences:

(I) a b e g h f 
(II) a b f e h g
(III) a b f h g e 
(IV) a f g h b e

Which are depth first traversals of the above graph?

Consider the following SQL query

select distinct al, a2,........., an
from r1, r2,........, rm
where P

For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions ?  

Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S → {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) ⇒ P(y) for all x, y ∈ S satisfying x≤y, where ⇒ stands for logical implication. Which of the following statements CANNOT be true?    

Consider the following formula a and its two interpretations I1 and I2 Which of the following statements is true?  

Consider the following recurrence relation  

Let f : A → B be an injective (one-to-one) function.

Define g : 2A → 2B as :
g(C) = {f(x) | x ∈ C}, for all subsets C of A.
Define h : 2B → 2A as :
h(D) = {x | x ∈ A, f(x) ∈ D}, for all subsets D of B.

Which of the following statements is always true ?

Consider the set {a, b, c} with binary operators + and × defined as follows :

+	a	b	c		×	a	b	c
a	b	a	c		a	a	b	c
b	a	b	c		b	b	c	a
c	a	c	b		c	c	c	b

For example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following set of equations :

(a × x) + (a × y) = c
(b × x) + (c × y) = c

The number of solution(s) (i.e., pair(s) (x, y)) that satisfy the equations is :

Let ∑ = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows : g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.  

A graph G = (V, E) satisfies |E| ≤ 3 |V| - 6. The min-degree of G is defined as Therefore, min-degree of G cannot be

Consider the following system of linear equation

A piecewise linear function f(x) is plotted using thick solid lines in the figure below If we use the Newton-Raphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be  

The following is a scheme for floating point number representation using 16 bits.

Bit position 15           14 . . . 9            8 . . . . .0
       s                      e                      m
     Sign                  Exponent               Mantissa

Let s,e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is: What is the maximum difference between two successive real numbers representable in this system?  

A 1-input, 2-output synchronous sequential circuit behaves as follows : Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the input (zk + nk = k). The circuit outputs 00 until one of the following conditions holds.

    zk - nk = 2. In this case, the output at the k-th and 
                 all subsequent clock ticks is 10.
    nk - zk = 2. In this case, the output at the k-th and
                 all subsequent clock ticks is 01.

What is the minimum number of states required in the state transition graph of the above circuit?

The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the function given by the following Karnaugh map ? Here, X denotes "don't care"    

Consider the ALU shown below

If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction respectively) ?

Consider the following circuit composed of XOR gates and non-inverting buffers. The non-inverting buffers have delays d1 = 2 ns and d2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns ?  

Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.

	MOV B, # 0	;	B ← 0
	MOV C, # 8	;	C ← 8
Z :	CMP C, # 0	;	compare C with 0
	JZX	;	jump to X if zero flag is set
	SUB C, # 1	;	C ← C - 1
	RRC A, # 1	;	right rotate A through carry by one bit. Thus:
		;	if the initial values of A and the carry flag are a7...a0 and
		;	c0 respectively, their values after the execution of this
		;	instruction will be c0a7...a1 and a0 respectively.
	JC Y	;	jump to Y if carry flag is set
	JMP Z	;	jump to Z
Y :	ADD B, # 1	;	B ← B + 1
	JMP Z	;	jump to Z
X :

Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.

	MOV B, # 0	;	B ← 0
	MOV C, # 8	;	C ← 8
Z :	CMP C, # 0	;	compare C with 0
	JZX	;	jump to X if zero flag is set
	SUB C, # 1	;	C ← C - 1
	RRC A, # 1	;	right rotate A through carry by one bit. Thus:
		;	if the initial values of A and the carry flag are a7...a0 and
		;	c0 respectively, their values after the execution of this
		;	instruction will be c0a7...a1 and a0 respectively.
	JC Y	;	jump to Y if carry flag is set
	JMP Z	;	jump to Z
Y :	ADD B, # 1	;	B ← B + 1
	JMP Z	;	jump to Z
X :

Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value ?    

Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is    

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε Which of the following statements is true?

Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true?

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

	0	1	B
q0	q1, 1, R	q1, 1, R	Halt
q1	q1, 1, R	q0, 1, L	q0, B, L

The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?

Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w}

Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true ?  

Consider the grammar shown below

S → i E t S S' | a
S' → e S | ε
E → b

In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are

Consider the grammar shown below.

S → C C
C → c C | d

The grammar is

Consider the translation scheme shown below

S → T R
R → + T {print ('+');} R | ε
T → num {print (num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print

Consider the syntax directed definition shown below.

S → id : = E  {gen (id.place = E.place;);}
E → E1 + E2   {t = newtemp ( ); gen (t = El.place + E2.place;); E.place = t}
E → id     {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X: = Y + Z', the 3-address code sequence generated by this definition is

In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ?

In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?

A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

   o	Delection of the smallest element 
   o	Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree. What is the result of inserting G in the above tree ?    

Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows : A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?  

  What is the weight of a minimum spanning tree of the following graph ?  

The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “a_s b_s c_s a_e d_s c_e e_s f_s b_e d_e g_s e_e f_e h_s g_e h_e”. Here, x_s denotes the starting time and x_e denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?

Let G (V, E) be a directed graph with n vertices. A path from v_i to v_j in G is sequence of vertices (v_i, v_i+1, ......., v_j) such that (vk, v_k+1) ∈ E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow

Consider the following algorithm.

for i = 1 to n
   for j = 1 to n
      for k = 1 to n
         A [j , k] = max (A[j, k] (A[j, i] + A [i, k]);

Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?

Consider the following logic program P A(x) <- B(x, y), C(y) <- B(x,x) Which of the following first order sentences is equivalent to P?

The following resolution rule is used in logic programming.

Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R)

Which of the following statements related to this rule is FALSE?

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P
{
    void f(int i)
    {
        print(i);
    }
}

Class Q subclass of P
{
    void f(int i)
    {
        print(2*i);
    }
}

Now consider the following program fragment:

P x = new Q();
Q y = new Q();
P z = new Q();
x.f(1); ((P)y).f(1); z.f(1);

Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0×00400000, and a stack page starting at virtual address 0×FFFFF000. The amount of memory required for storing the page tables of this process is:

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:
while (1) {
W:
   print '0';
   print '0';
X:
}
	
Process Q:
while (1) {
Y:
   print '1';
   print '1';
Z:
}

Synchronization statements can be inserted only at points W, X, Y and Z. Which of the following will always lead to an output staring with '001100110011' ?

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:
while (1) {
W:
   print '0';
   print '0';
X:
}
	
Process Q:
while (1) {
Y:
   print '1';
   print '1';
Z:
}

Synchronization statements can be inserted only at points W, X, Y and Z Which of the following will ensure that the output string never contains a substring of the form 01^n0 or 10^n1 where n is odd?

Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 µs Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 µs. What is the maximum achievable throughput in this communication?    

Consider the following functional dependencies in a database:

  Data_of_Birth → Age
  Age → Eligibility
  Name → Roll_number
  Roll_number → Name
  Course_number → Course_name
  Course_number → Instructor
  (Roll_number, Course_number) → Grade

The relation (Roll_number, Name, Date_of_birth, Age) is:

Consider the set of relations shown below and the SQL query that follows.

Students: (Roll_number, Name, Date_of_birth)
  Courses: (Course number, Course_name, Instructor)
  Grades: (Roll_number, Course_number, Grade)

 select distinct Name
         from Students, Courses, Grades
         where Students. Roll_number = Grades.Roll_number
              and Courses.Instructor = Korth
              and Courses.Course_number = Grades.Course_number
              and Grades.grade = A

Which of the following sets is computed by the above query?

Consider three data items D1, D2 and D3 and the following execution schedule of transactions T1, T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively. Which of the following statements is correct?    

In the following C program fragment, j, k n and TwoLog_n are interger variables, and A is an array of integers. The variable n is initialized to an integer ≥ 3, and TwoLog_n is initialized to the value of 2*⌈log2(n)⌉

Consider the C program shown below.

Consider the function f defined below.