What does the following C-statement declare?

    int ( * f) (int * ) ; 

An Abstract Data Type (ADT) is:

A common property of logic programming languages and functional languages is:

Which one of the following are essential features of an object-oriented programming language?

(i) Abstraction and encapsulation
(ii) Strictly-typedness
(iii) Type-safe property coupled with sub-type rule
(iv) Polymorphism in the presence of inheritance

A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:

Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C). Which one of the following is TRUE?

The following is the Hasse diagram of the poset [{a,b,c,d,e},<]

The poset is

Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is

Let f(x) be the continuous probability density function of a random variable X. The probability that a < X ≤ b, is:

The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:

Consider the following circuit.

Which one of the following is TRUE?

The range of integers that can be represented by an n bit 2's complement number system is:

The hexadecimal representation of 657₈ is

The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is:

Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?

Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?

What is the swap space in the disk used for?

Increasing the RAM of a computer typically improves performance because:

Packets of the same session may be routed through different paths in:

The address resolution protocol (ARP) is used for:

The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning tree algorithm used for bridge-routing?

An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be:

Which one of the following is a key factor for preferring B⁺- trees to binary search trees for indexing database relations?

Which one of the following statements about normal forms is FALSE?

Let r be a relation instance with schema R = (A, B, C, D). We define r₁ = Π_A,B,C(R) and r₂ = Π_A,D(R). Let s = r₁*r₂ where * denotes natural join. Given that the decomposition of r into r₁ and r₂ is lossy, which one of the following is TRUE?

Consider the following C-program:

void foo(int n, int sum) {
  int k = 0, j = 0;
  if (n == 0) return;
  k = n % 10; j = n / 10;
  sum = sum + k;
  foo(j, sum);
  printf ("%d,", k);
}
  
int main () {
  int a = 2048, sum = 0;
  foo(a, sum);
  printf ("%d\n", sum);
}

What does the above program print?

Consider the following C-program:

double foo (double);    /* Line 1 */
 
int main() {
  double da, db;
 
  // input da
 
  db = foo(da);
}
 
double foo(double a) {
  return a;
} 

The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:

Postorder traversal of a given binary search tree T produces the following sequence of keys

   10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 

Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:

   10, 8, 5, 3, 2 

Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

How many distinct binary search trees can be created out of 4 distinct keys?

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1

Which one of the following is FALSE?

Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)

Let P, Q and R be three atomic prepositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?

What is the first order predicate calculus statement equivalent to the following?

   Every teacher is liked by some student  

Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?

Let f: B → C and g: A → B be two functions and let h = f∘g. Given that h is an onto function. Which one of the following is TRUE?

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that

    a ≡ c mod 3 and b ≡ d mod 5  

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

Consider the set H of all 3 × 3 matrices of the type

|a   f   e|
|0   b   d|
|0   0   c|

where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is

Which one of the following graphs is NOT planar?

Consider the following system of equations in three real variables x_l, x₂ and x₃

2xl - x2 + 3x3 = 1 
3xl- 2x2 + 5x3 = 2 
-xl + 4x2 + x3 = 3 

This system of equations has

What are the eigenvalues of the following 2 × 2 matrix?

|2   -1|
|-4   5| 

Let , where |x|<1. What is g(i)?

Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:

(i) Select a box
(ii) Choose a ball from the selected box such that each ball in
     the box is equally likely to be chosen. The probabilities of
     selecting boxes P and Q are (1/3) and (2/3), respectively.

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is:

Consider the machine M:

The language recognized by M is:

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let D_f and D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

Consider the languages:

L1 = {anbncm |n,m > 0} and L2 = {anbmcm |n,m > 0}

Which one of the following statements is FALSE?

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider the languages:

L1 = {wwR |w ∈ {0,1}*}
L2 = {w#wR | w ∈ {0,1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1)*}

Which one of the following is TRUE?

Consider the following two problems on undirected graphs:

α: Given G(V,E), does G have an independent set of size |V|-4?
β: Given G(V,E), does G have an independent set of size 5?

Which one of the following is TRUE?

Consider the grammar:

  E → E + n | E × n | n 

For a sentence n + n × n, the handles in the right-sentential form of the reduction are:

Consider the grammar:

   S → (S) | a 

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n₁, n₂ and n₃ respectively. The following relationship holds good:

Consider line number 3 of the following C-program.

int main ( ) {                   /* Line 1 */
  int I, N;                      /* Line 2 */
  fro (I = 0, I < N, I++);       /* Line 3 */
} 

Identify the compiler's response about this line while creating the object-module:

Consider the following circuit involving a positive edge triggered D FF.

Consider the following timing diagram. Let A_i represent the logic level on the line A in the i-th clock period.

Let A' represent the complement of A. The correct output sequence on Y over the clock periods 1 through 5 is

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.

Which one of the following is TRUE?

Consider the following circuit.

The flip-flops are positive edge triggered D FFs. Each state is designated as a two bit string Q₀Q₁. Let the initial state be 00. The state transition sequence is:

Consider a three word machine instruction

ADD A[R0], @B

The first operand (destination) "A[R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand).

The number of memory cycles needed during the execution cycle of the instruction is

Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.

     (1) A[1] = B[J];     (a) Indirect addressing
     (2) while [*A++];    (b) Indexed addressing
     (3) int temp = *x;   (c) Auto increment

Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively.

A 5 stage pipelined CPU has the following sequence of stages:

IF — Instruction fetch from instruction memory.
RD — Instruction decode and register read.
EX — Execute: ALU operation for data and address computation.
MA — Data memory access - for write access, the register read at RD stage is used.
WB — Register write back. 

Consider the following sequence of instructions:

I1 : L R0, 1oc1; R0 <= M[1oc1]
I2 : A R0, R0 1; R0 <= R0 + R0
I3 : S R2, R0 1; R2 <= R2 - R0
Let each stage take one clock cycle.

What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I₁?

A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be 4 μsec. The byte transfer time between the device interfaces register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under program-controlled mode?

Consider a disk drive with the following specifications:

16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby whenever one byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec. The maximum percentage of time that the CPU gets blocked during DMA operation is:

Suppose n processes, P₁, …., P_n share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process P_i is s_i, where s_i>0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?

Consider the following code fragment:

  if (fork() == 0)
      { a = a + 5; printf(“%d, %d\n”, a, &a); }
  else { a = a – 5; printf(“%d, %d\n”, a, &a); }

Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?

In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is:

Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is:

Let E₁ and E₂ be two entities in an E/R diagram with simple single-valued attributes. R₁ and R₂ are two relationships between E₁ and E₂, where R₁ is one-to-many and R₂ is many-to-many. R₁ and R₂ do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model?

The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with on-delete cascade.

          A   C
          -----
          2   4
          3   4
          4   3
          5   2
          7   2
          9   5
          6   4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:

     select title
     from book as B
     where (select count(*)
        from book as T
        where T.price > B.price) < 5 

Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold: {A → B, BC → D, E → C, D → A}. What are the candidate keys of R?

Consider the following data path of a CPU.

The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.

The instruction "add R0, R1" has the register transfer interpretation R0 <= R0+R1. The minimum number of clock cycles needed for execution cycle of this instruction is:

Consider the following data path of a CPU.

The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.

The instruction "call Rn, sub" is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is

      Rn <= PC + 1;
      PC <= M[PC]; 

The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:

Consider the following C-function:

double foo (int n) {
    int i;
    double sum;
    if (n == 0) return 1.0;
    else {
        sum = 0.0;
        for (i = 0; i < n; i++)
            sum += foo(i);
        return sum;
    }  }   

The space complexity of the above function is:

Consider the following C-function:

double foo (int n) {
    int i;
    double sum;
    if (n == 0) return 1.0;
    else {
        sum = 0.0;
        for (i = 0; i < n; i++)
            sum += foo(i);
        return sum;
    }  }   

Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:

Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.

The edge e must definitely belong to:

Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.

Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

We are given 9 tasks T₁, T₂.... T₉. The execution of each task requires one unit of time. We can execute one task at a time. Each task T_i has a profit P_i and a deadline d_i Profit P_i is earned if the task is completed before the end of the d_i^th unit of time.

Task     T1  T2	 T3  T4  T5  T6	 T7 T8  T9
Profit   15  20	 30  18  18  10	 23 16  25
Deadline 7   2 	 5   3 	 4   5 	 2  7   3

Are all tasks completed in the schedule that gives maximum profit?

We are given 9 tasks T₁, T₂.... T₉. The execution of each task requires one unit of time. We can execute one task at a time. Each task T_i has a profit P_i and a deadline d_i Profit P_i is earned if the task is completed before the end of the d_i^th unit of time.

Task     T1  T2	 T3  T4  T5  T6	 T7 T8  T9
Profit   15  20	 30  18  18  10	 23 16  25
Deadline 7   2 	 5   3 	 4   5 	 2  7   3

What is the maximum profit earned?

Consider the following floating point format.

Mantissa is a pure fraction in sign-magnitude form.

The decimal number 0.239 × 2¹³ has the following hexadecimal representation (without normalization and rounding off:

Consider the following floating point format.

Mantissa is a pure fraction in sign-magnitude form.

The normalized representation for the above format is specified as follows. The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0's are padded in while shifting a field. The normalized representation of the above number (0.239 × 2¹³) is