# (Paper) GATE: Computer Science (CS) Question Paper Year 2006 (4)

68. Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Given the following four queries:

Queryl: select student from enrolled where student in (select student from
paid)

Query2: select student from paid where student in (select student from enrolled)

Query3: select E.student from enrolled E, paid P where E.student = P.student

Query4: select student from paid where exists (select * from enrolled
where enrolled.student = paid.student)

Which one of the following statements is correct?

(A) All queries return identical row sets for any database

(B) Query2 and Query4 return identical row sets for all databases but there
exist databases for which Queryl and Query2 return different row sets.

(C) There exist databases for which Query3 returns strictly fewer rows than
Query2

(D) There exist databases for which Query4 will encounter an integrity violation
at runtime.

69. Consider the relation enrolled (student, course) in which (student,
course) is the primary key, and the relation paid (student, amount) where
student is the primary key. Assume no null values and no foreign keys or
integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were
each paid by 20% of the students. Consider these query plans (Plan 1 on left,
Plan 2 on right) to "list all courses taken by students who have paid more than
x" enrolled paid enrolled paid 1' 1' Probe index Sequential on student scan,
select amount > x A disk seek takes 4ms, disk data transfer bandwidth is 300
MB/s and checking a tuple to see if amount is greater than x takes lOps. Which
of the following statements is correct?

(A) Plan 1 and Plan 2 will not output identical row sets for all databases

(B) A course may be listed more than once in the output of Plan 1 for some data
bases

(C) For x = 5000, Plan 1 executes faster than Plan 2 for all databases

(D) For x = 9000, Plan I executes slower than Plan 2 for all databases.

**Common Data Questions:**

**Common Data for Questions 71, 72, 73:
The 2 vertices of a graph G corresponds to all subsets of a set of size
n, for n < 6. Two vertices of G are adjacent if and only if the corresponding
sets intersect in exactly two elements.**

71. The number of vertices of degree zero in G is:

(A) 1

(B) n

(C) n+1

(D)2

72. The maximum degree of a vertex in G is:

(A) 2J

(B) 2 2

(C) 23x3

(D) 2 1

73. The number of connected components in G is:

(A) n

(B) n+2

(C) 2/2

(D)

**Common Data for Questions 74, 75:
**

**Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-i multiplexer has a latency of 0.6 ns while a kbit comparator has a latency of k/lO ns. The hit latency of the set associative organization is h1while that of the direct mapped one is h2.**

74. The value of h1is:

(A) 2.4 ns

(B) 2.3 ns

(C) 1.8 ns

(D) 1.7 ns

75. The value of h2 is:

(A) 2.4 ns

(B) 2.3 ns

(C) 1.8 ns

(D) 1.7 ns

**Linked Answer Questions: Q.76 to Q85 Carry Two Marks
Each
**

**Statement for Linked Answer Questions 76 & 77:**

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

76. Which one of the following is a valid sequence of elements in an array
representing 3-ary max heap?

(A) 1, 3, 5, 6, 8, 9

(B) 9, 6, 3, 1, 8, 5

(C) 9, 3, 6, 8, 5, 1

(D) 9, 5, 6, 8, 3, 1

77. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the
valid 3- ary max heap found in the above question, Q.76. Which one of the
following is the sequence of items in the array representing the resultant heap?

(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3

(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Statement for Linked Answer Questions 78 & 79:

Barrier is a synchronization construct where a set of processes synchronizes
globally i.e. each process in the set arrives at the barrier and waits for all
others to arrive and then all processes leave the barrier. Let the number of
processes in the set be three and S be a binary semaphore with the usual P and V
functions. Consider the following C implementation of a barrier with line
numbers shown on left.

void barrier (void)

1: P(S);

2: process_arrived++;

3. V(S);

4: while (process_arrived !=3);

5: P(S);

6: process_left++;

7: if (process_left==3)

8: process_arrived = 0;

9: process_left = 0;

10:

11: V(S);

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

78. The above implementation of barrier is incorrect. Which one of the
following is true?

(A) The barrier implementation is wrong due to the use of binary semaphore S

(B) The barrier implementation may lead to a deadlock if two barrier in
invocations are used in immediate succession.

(C) Lines 6 to 10 need not be inside a critical section

(D) The barrier implementation is correct if there are only two processes
instead of three.

79. Which one of the following rectifies the problem in the implementation?

(A) Lines 6 to 10 are simply replaced by process_arrived–

(B) At the beginning of the barrier the first process to enter the barrier waits
until process_arrived becomes zero before proceeding to execute P(S).

(C) Context switch is disabled at the beginning of the barrier and re-enabled at
the end.

(D) The variable process_left is made private instead of shared

**Statement for Linked Answer Questions 80 & 81:
**A CPU has a 32 KB direct mapped cache with 128-byte block size.
Suppose A is a twodimensional array of size 512×512 with elements that occupy
8-bytes each. Consider the following two C code segments, P1 and P2.

P1: for (i=0; i<512; i++)

for (j=O; j<512; j++)

x +=A[i] [j];

P2: for (i=O; i<512; i++)

for (j=O; j<512; j++)

x +=A[j] [}1;

P1 and P2 are executed independently with the same initial state, namely, the
array A is not in the cache and i,j,x are in registers. Let the number of cache
misses experienced by P1 be M1 and that for P2 be 142.

80. The value of M1 is:

(A) 0

(B) 2048

(C) 16384

(D) 262144

81. The value of the ratio

(A) 0

(B)16

(C)

(D) 16

**Statement for Linked Answer Questions 82 & 83:**

**Consider the diagram shown below where a number of LAN5 are connected by
(transparent) bridges. In order to avoid packets looping through circuits in the
graph, the bridges organize themselves in a spanning tree. First, the root
bridge is identified as the bridge with the least serial number. Next, the root
sends out (one or more) data units to enable the setting up of the spanning tree
of shortest paths from the root bridge to each bridge. Each bridge identifies a
port (the root port) through which it will forward frames to the root bridge.
Port conflicts are always resolved in favour of the port with the lower index
value. When there is a possibility of multiple bridges forwarding to the same
LAN (but not through the root port), ties are broken as follows: bridges closest
to the root get preference and between such bridges, the one with the lowest
serial number is preferred. **

82. For the given connection of LANs by bridges, which one of the following
choices represents the depth first traversal of the spanning tree of bridges?

(A) Bi, B5, B3, B4, B2

(B) Bi, B3, B5, B2, B4

(C) Bi, B5, B2, B3, B4

(D) Bi, B3, B4, B5, B2

**Statement for Linked Answer Questions 84 & 85:
**

**84. Which one of the following grammars generates the language L = {a’ bi I)?**

(A) S - ACCB

(B) S—aSSbab C — aCbab

(C) S-ACCB S-ACCB

(D) C—aCbE C—aCbH

85. In the correct grammar above, what is the length of the derivation
(number of steps starring from S) to generate the string a/bm with I < m?

(A) max(I,m)+2

(B) I+m+2

(C) I+m+3

(D) max(I,m)+3

## Previous Page

| Start Page