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

Consider the following formula and its two interpretations $I_1$ and $I_2$.

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

$I_1$ : Domain: the set of natural numbers

$P_x$ = 'x is a prime number'
$Q_{xy}$ = 'y divides x'
$I_2$ : same as $I_1$ except that $P_x$ = 'x is a composite number'.

Which of the following statements is true?

Let (S,$\le$) 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)$\Rightarrow$P(y) for all x, y $\epsilon$S satisfying x$\le$y,

Where $\Rightarrow$stands for logical implication. Which of the following statements CANNOT be true?

Let $\Sigma = \left\{a, b, c, d, e\right\}$ 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$.

Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$.

For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$.

For a non-empty sequence$\left \langle s_j, \dots,s_n\right \rangle$ of stings from $\Sigma^+$, define $h\left(\left \langle s_i \dots s_n\right \rangle\right)=\Pi^n_{i=1}P_i^{f\left(s_i\right)}$

Which of the following numbers is the encoding, $h$, of a non-empty sequence of strings?

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 system of linear equations $$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) \left( \begin{array}{ccc} x \\ y \\ z \end{array} \right) = \left( \begin{array}{ccc} \alpha \\ 5 \\ 7 \end{array} \right)$$ Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of $\alpha$, does this system of equations have infinitely many solutions?

Consider the syntax directed definition shown below,
S $\rightarrow$ id : = E {gen (id.place = E.place;);}
E $\rightarrow$ E₁ + E₂ {t = newtemp( );
gen(t = E1.place + E2.place;);
E.place = t;}
E $\rightarrow$ 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

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_k+1) \in 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 \times n$ array initialized as follows.

$$A[j,k] = \begin{cases} 1 \text { if } (j,k) \in E \\ 0 \text{ otherwise} \end{cases}$$

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 termination of the above algorithm?

Let G = (V,E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G
as follows.

$$G= \begin{cases} 0 \text { if } e \in E_1 \\ 1 \text{ otherwise} \end{cases}$$

        A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex 

v₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed?

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

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

A uni-processor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

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?

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

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 micro second. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 micro second. What is the maximum achievable throughput in this communication?

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The codes for the processes P and Q are shown below.
Process P: Process Q:
while (1) { while (1) {
W: Y:
print '0'; print '1';
print '0'; print '1';
X: Z:
} }
Synchronization statements can be inserted only at points W, X, Y and Z

Which of the following will always lead to an output starting with '001100110011'?

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The codes for the processes P and Q are shown below.
Process P: Process Q:
while (1) { while (1) {
W: Y:
print '0'; print '1';
print '0'; print '1';
X: 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 01n0 or 10n1 where n is odd?

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 { Class Q subclass of P {
void f(int i) { void f(int i) {
print(i); print(2*i);
} }
} }
Now consider the following program fragment:
Px = new Q()
Qy = new Q();
Pz = 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

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 ^{_$\leftarrow$} 0
MOV C, #8 ; C ^{_$\leftarrow$} 8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C ^{_$\leftarrow$} 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 a₇… a₀ and
; instruction will be c₀a₇…a₁ and a₀ respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B ^{_$\leftarrow$} B + 1
X: If the initial value of register A is A0, the value of register B after the program execution will be

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 $\leftarrow$0
MOV C, #8 ; C$\leftarrow$8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C $\leftarrow$ 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 a₇… a₀ and
; instruction will be c₀a₇…a₁ and a₀ respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B $\leftarrow$ B + 1
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?

A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set.
I. Deletion of the smallest element
II. 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?

Let S be a stack of size n $\ge$1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array of
integers. The variable n is initialized to an integer $\ge$3, and TwoLog_n is initialized to the value of 2
*$\lceil log_2(n) \rceil$
for (k = 3; k < = n; k++)
A [k] = 0;
for (k = 2; k < = TwoLog_n ; k++)
for (j = k+1; j < = n ; j++)
A[j] = A[j] || (j% k);
for (j = 3; j < = n ; j++)
if (!A[j]) print f(”%d ”,j);
The set of numbers printed by this program fragment 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 the following functional dependencies in a database.

Date_of_Birth ^{_{$\rightarrow$}} Age Age ^{_{$\rightarrow$}} Eligibility
Name ^{_{$\rightarrow$}} Roll_number Roll_number ^{_{$\rightarrow$}} Name
Course_number ^{_{$\rightarrow$}} Course_name Course_number ^{_{$\rightarrow$}} Instructor
(Roll_number, Course_number) ^{_{$\rightarrow$}} Grade

The relation (Roll_number, Name, Date_of_Birth, Age) is

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.

Which of the following statements is true about M?

Define languages L0 and L1 as follows:
L₀ = {<M, w, 0> | M halts on w}
L₁ = {<M, w, 1> | M does not halt 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 = L_0$\cup$L₁. Which of the following is true?

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

$$\begin{cases}(-1)^s \left(1+m \times 2^{-9}\right) 2^{e-31}, & \text{ if the exponent } \neq 111111 \\ 0, & \text{ otherwise} \end{cases}$$

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?