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

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 code void swap (mt *px, mt *py) {
*px = *px – *py;
*py = *px + *py;
*px = *py – *px;
}

Si: will generate a compilation error
S2: may generate a segmentation fault at runtime depending on the arguments passed
S3: correctly implements the swap procedure for all input pointers referring to integers stored in memory locations accessible to the process
S4: implements the swap procedure correctly for some but not all valid input pointers
S5: may add or subtract integers and pointers.

(A) Si
(B) S2 and S3
(C) S2 and S4
(D) S2 and S5

58. Consider the following grammar:
S – FR
R — *5k.
F - Id

In the predictive parser table, M, of the grammar the entries M[S,idl and M[R,\$1 respectively.
(A) {S—FR} and {R—s}
(B) {S—FR} and { }
(C) {S—FR} and {R_*S}
(D) {F — id} and {R — s}

59. Consider the following translation scheme.
S - ER
R *E{print('*');}Rs
E — F+E{print(+);}F
F — (S)id{print(id.value);}

Here Id is a token that represents an integer and id.value represents the corresponding integer value. For an input 2*3+4,this translation scheme prints
(A) 2*3+4
(B) 2*+34
(C) 2 3*4
(D) 2 3 4*

60. Consider the following C code segment.
for (} — 0, i<n; i++)
for (j=O; j<n; j++)
if (}%2)
x += (4*j + 5*});
y += (7 + 4*j);

Which one of the following is false?
(A) The code contains loop invariant computation
(B) There is scope of common sub-expression elimination in this code
(C) There is scope of strength reduction in this code
(D) There is scope of dead code elimination in this code

61. The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S.

void P (binary_semaphore *s)
unsigned y;
unsigned * = &(s—>value);
do
fetch—and—set x, y;
while (y)
void V (binary_semaphore *s)
S—>value = 0;

Which one of the following is true?
(A) The implementation may not work if context switching is disabled in P
(B) Instead of using fetch-and —set, a pair of normal load/store can be used
(C) The implementation of V is wrong
(D) The code does not implement a binary semaphore

62. A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4- way set associative. The minimum size of the TLB tag is:
(A) 11 bits
(B) 13 bits
(C) 15 bits
(D) 20 bits

63. A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?
(A) Efficient implementation of multi-user support is no longer possible
(B) The processor cache organization can be made more efficient now
(C) Hardware support for memory management is no longer needed
(D) CPU scheduling can be made more efficient now

64. Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is:
(A) 13 units
(B) 14 units
(C) 15 units
(D) 16 units

65. Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70°h of time doing computation, and the last 10°h of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?
(A) 0%
(B) 1O.6°h
(C) 30.O°h
(D) 89.4°h

66. Consider the following snapshot of a system running n processes. Process i is holding x,instances of a resource R, 1 n. currently, all instances of R are occupied. Further, for all I, process i has placed a request for an additional y, instances while holding the x, instances it already has. There are exactly two processes p and q such that = Yq = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
(A) min(xp,xq) < max Yk
(B) X + Xq mink pq Yk
(C) max(xp,xq)>1
(D) min(xp,xq)>1

67. Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. ties are not broke but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned.

select A.customer, count (B.customer)
Queryl: from account A, account B where A.balance <=B.balance group by A.customer select A.customer, 1+count(B.customer)
Query2: from account A, account B where A.balance < B.balance group by A.customer

Consider these statements about Queryl and Query2.

1. Queryl will produce the same row set as Query2 for some but not all databases.
2. Both Queryl and Query2 are correct implementation of the specification
3. Queryl is a correct implementation of the specification but Query2 is not
4. Neither Queryl nor Query2 is a correct implementation of the specification
5. Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using ODBC.

Which two of the above statements are correct?
(A) 2 and 5
(B) 1 and 3
(C) 1 and 4
(D) 3 and 5