# Papers

Paper

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

PORTAL:
Subjects:
JEE - EXAMS:

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

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

PORTAL:
Subjects:
JEE - EXAMS:

51. Consider the following recurrence:
T(n)=2T(r*i1)+1,T(1) = 1

Which one of the following is true?
(A) T(n) = e(loglogn)
(B) T(n) = e(logn)
(C) T(n)=8(sJ)
(D) T(n)rz8(n)

52. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
(A) 8(n)
(B) e(nlogn)
(C) 8(n2)
(D) 8(n3)

53. Consider the following C-function in which a[nl and b[mlare two sorted integer arrays and c[n + mibe another integer array.

void xyz(int a[], mt b [1, mt c []){
mt i,j,k;
i=j=k=O;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] =

Which of the following condition(s) hold(s) after the termination of the while loop?
(i) j<m,k=n+j—1, and a[n—i1<b[jl ifi=n
(ii) i<n,k=m+i—1, and b[m—i1a[i1 ifj=m

(A) only (i)
(B) only (ii)
(C) either (i) or (ii) but not both
(D) neither (i) nor (ii)

54. Given two arrays of numbers a1,...,a and b1,...,b where each number is 0 or 1, the fastest algorithm to find the largest span (i,j)such that a, + a,1 + ... + a = b, + b,1 + ... + b, or report that there is not such span,
(A) Takes Q(3n) and c(2)time if hashing is permitted
(B) Takes 0(n3) and c(n25)time in the key comparison model
(C) Takes e(n)time and space
(D) Takes o(J) time only if the sum of the 2n elements is an even number

56. Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code. subroutine swap(ix,iy)
it = ix
Li: ix=iy
L2: iy=it
end
ia = 3
ib = 8
call swap (ia, ib+5)
print , ia, ib
end

Si: The compiler will generate code to allocate a temporary nameless cell, initialize it to i3, and pass the address of the cell swap
S2: On execution the code will generate a runtime error on line Li
S3: On execution the code will generate a runtime error on line L2
S4: The program will print i3 and 8
S5: The program will print i3 and -2

Exactly the following set of statement(s) is correct:
(A) Si and S2
(B) Si and S4
(C) S3
(D) Si and S5

57. Consider this C code to swap two integers and these five statements: the

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

PORTAL:
Subjects:
JEE - EXAMS:

26. Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened.
(A) vx[(tiger(x) A lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1
(B) Vx [(tiger (x) v lion (x)) — {(hungry (x) v threatened (x)) A attacks (x)j
(C) Vx[(tiger(x) v lion(x)) — {attacks(x) — (hungry(x) v threatened(x)))1
(D) vx[(tiger(x) v lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1

27. Consider the following propositional statements:
Pl:((AAB)C))((AC)A(BC))
P2:((AvB)C))((A—C)v(B_C))
Which one of the following is true?

(A) P1 is a tautology, but not P2
(B) P2 is a tautology, but not P1
(C) P1 and P2 are both tautologies
(D) Both P1 and P2 are not tautologies

28. A logical binary relation a, is defined as follows:
Let be the unary negation (NOT) operator, with higher precedence then o. Which one of the following is equivalent to A A B?
(A) ('-'.'AOB)
(B) -'.'(AO'-..'B)
(C) ".'(".'Ao".'B)
(D) AOB)

29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n1 (s)the number of l's in s. Which one of the following languages is not regular?
(A) L = {s (0 + 1)*n0 (s) is a 3-digit prime
(B) L = {s E (0 + 1)* for every prefix s' of s, fl0 (s') — n1 (s') 2}
(C) L={sE(0+1)*n0(s)_n1(s)4}
(D) L = {s E (0 + 1) j n0 (s) mod 7 = n1 (s) mod 5 = 0)

30. For SE (0+1)*let d(s)denote the decimal value of s(e.g.d(101)= 5). Let L = {s E (0 + 1) j d (s) mod 5 = 2 and d (s) mod 7 = 4) Which one of the following statements is true?
(A) L is recursively enumerable, but not recursive
(B) L is recursive, but not context-free
(C) L is context-free, but not regular
(D) L is regular

31. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

A B AoB

True True True
True False True
False True False
False False True

(A) Both DHAM3 and SHAM3 are NP-hard
(B) SHAM3 is NP-hard, but DHAM3 is not