# (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