Computer Science (GATE Exam) 2007 - Previous Question Paper Solution

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

In a look-ahead carry generator, the carry generate function Gi and the carry propagate function P_i for
inputs A_i and B_i are given by:
P_i = A_i $\oplus$ B_i and G_i = A_i B_i
The expressions for the sum bit S_i and the carry bit C_i+1 of the look-ahead carry adder are given by:
S_i = P_i C_i and C_i+1 = G_i + P_i C_i, where C_o is the input carry.
Consider a two-level logic implementation of the look-ahead carry generator.
Assume that all P_i and G_i are available for the carry generator circuit and that the AND and OR gates
can have any number of inputs. The number of AND gates and OR gates needed to implement the
look-ahead carry generator for a 4-bit adder with 3 2 1 0 4 S ,S ,S ,S and C as its outputs are
respectively:

A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed
number of frames to a process. Consider the following statements:
P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.
Q: Some programs do not exhibit locality of reference.
Which one of the following is TRUE?

In a simplified computer the instructions are:
OP R_j , R_i - Performs R_j OP R_i and stores the result in register . R_i
OP m, R_i - Performs val i OP R_i and stores the result in R_i. val denotes the content of memory location m.
MOV m, R_i - Moves the content of memory location m to register R_i
MOV R_i , m - Moves the content of register R_i to memory location m.
The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:
t₁ = a + b
t₂ = c + d
t₃ = e - t₂
t₄ = t₁ - b
Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1

If optimal page replacement policy is used, how many page faults occur for the above reference string?

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

S$ \rightarrow$ a B S $ \rightarrow$bA
B $ \rightarrow$b A$ \rightarrow$ a
B $ \rightarrow$bS A $ \rightarrow$aS
B $ \rightarrow$aBB S$ \rightarrow$ bAA

Which of the following strings is generated by the grammar?

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j) then it can move to either (i + 1, j) or (i, j + 1).

Suppose that the robot is not allowed to traverse the line segment from (4, 4) to (5, 4). With this
constraint, how many distinct paths are there for the robot to reach (10, 10) starting from (0, 0)?

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j) then it can move to either (i + 1, j) or (i, j + 1).

How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

S ^{_{$\rightarrow$}} aB S ^{_{$\rightarrow$}} bA
B ^{_{$\rightarrow$}} b A ^{_{$\rightarrow$}} a
B ^{_{$\rightarrow$}} bS A ^{_{$\rightarrow$}} aS
B ^{_{$\rightarrow$}} aBB S ^{_{$\rightarrow$}} bAA

How many derivation trees are there?

Consider a machine with a byte addressable main memory of 2¹⁶ bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?

Consider a pipelined processor with the following four stages:
IF: Instruction Fetch
ID: Instruction Decode and Operand Fetch
EX: Execute
WB: Write Back
The IF, ID and WB stages take one clock cycle each to complete the operation.
The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions
need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding
is used in the pipelined processor.
What is the number of clock cycles taken to complete the following sequence of instructions?
ADD R2, R1, R0 R2 $\rightarrow$ R1 + R0
MUL R4, R3, R2 R4$\rightarrow$ R3 * R2
SUB R6, R5, R4 R6 $\rightarrow$R5 - R4

Consider a machine with a byte addressable main memory of 2¹⁶ bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

How many data cache misses will occur in total?

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is word addressable. After the execution of this program, the content of memory location 2010 is:

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction “INC R3”, what return address will be pushed on to the stack?

Consider the following C program segment where CellNode represents a node in a binary tree:

Struct Cell Node {
  Struct Cell Node * left child;
  Int element;
  Struct Cell Node * right Child;
};
Int Get Value(struct Cell Node * ptr) {
  Int Value = 0;
  if (ptr! = NULL)
    if ((ptr - > left child == NULL) &&
      (ptr - > right Child == NULL))
      Value = 1;
    else
      Value = value + GetValue(ptr - > left Child) + Get Value(ptr - > right child);
}
return (value);
}

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

Information about a collection of students is given by the relation studinfo (studId, name, sex). The relation enroll (studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?

$\pi_{courceId}\left(\left(\pi_{\text{studId}}\left(\sigma_{sex="female"}\left(\text{studInfo}\right)\right) \times \pi_{courseId}\left(\text{enroll}\right)\right) -\text{enroll}\right)$

Consider the table employee (empId, name, department, salary) and the two queries Q₁, Q₂ below.
Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary in department 5, which one of the statements is TRUE for any arbitrary employee table?

$Q_1$ : Select e. empId
            From employee 
            Where not exists 
            (Select * From employee s where s. department = “5” and s. salary >= e. salary) 
$Q_2$ : Select e. empId
            From employee e
            Where e. salary > any
            (select distinct salary From employee s where s. Where s. department = “5”)

Consider the relation employee (name, sex, supervisor Name) with name as the key; supervisor Name gives the name of the supervisor of the employees under consideration. What does the following Tuple Relational Calculus query produce?
{
e. name| employee (e) ^{_{$\land$
$\forall X$}}[^_$\neg$employee (x) ^_$\lor$ x.supervisorName ^_$\ne$e.name ^_$\lor$ x.sex = “male”]
}

Consider the set $S = \left\{ a , b , c , d \right\}$ . Consider the following 4 partitions $\pi_1,\pi_2,\pi_3,\pi_4$ on $S : \pi_1 = \left\{\overline{abcd}\right\} , \pi_2 = \left\{\overline{ab}, \overline{cd}\right\}, \pi_3 = \left\{\overline{abc}, \overline{d}\right\}, \pi_4 = \left\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\right\}$. Let $\prec$ be the partial order on the set of partitions $S' = \{\pi_1,\pi_2,\pi_3,\pi_4\}$ defined as follows: $ \pi_i \prec \pi_j$ if and only if $\pi_i \text{ refines }\pi_j $. The poset diagram for $ (S',\prec)$ is: