By PDMACpayday loans

You Are Here: Home » GATE Question Papers » GATE CS 2006 Computer Science Question Paper

GATE CS 2006 Question Paper

EC Test ID: 00 All India Mock GATE Test
Q.1 – Q.20 Carry One Mark Each

( )
1. Consider the polynomial p x a a x a x a x = + + + , where 0, . a i The
minimum number of multiplications needed to evaluate p on an input x is:
(A) 3
(B) 4
(C) 6
(D) 9

2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A) Z xy
2
(B) 2 Z × xy

x y + (C) Z 2

(D) 2 xyz

{ } 1, 2,3,5, 7, 8, 9 3. The set under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false?
(A) It is not closed
(B) 2 does not have an inverse
(C) 3 does not have an inverse
(D) 8 does not have an inverse

4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) x y R u v , , x u y v and . if < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation
(B) A Partial Order but not a Total Order
(C) A Total Order
(D) An Equivalence Relation

5. For which one of the following reasons does Internet Protocol (IP) use the time-
to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time
(B) Discard packets that reach later than that time
(C) Prevent packets from looping indefinitely
(D) Limit the time for which a packet gets queued in intermediate routers.

6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units  and arrive at times 0, 2 and 6, respectively. How many context switches are  needed if the operating system implements a shortest remaining time first  scheduling algorithm? Do not count the context switches at time zero and at the
end.
(A) 1
(B) 2
(C) 3
(D) 4

7. Consider the following grammar.
S S E *
S E
E F E +
E F
F id
( )
Consider the following LR items corresponding to the grammar above. 0
(i) *. S S E
(ii) . E F E +
(iii) . E F E +
Given the items above, which two of them will appear in the same set in the
canonical sets-of-items for the grammar?
(A) (i) and (ii)
(B) (ii) and (iii)
(C) (i) and (iii)
(D) None of the above

8. You are given a free running clock with a duty cycle of 50% and a digital
waveform f which changes only at the negative edge of the clock. Which one of  the following circuits (using clocked D flip-flops) will delay the phase of f by  180°?
(A)

9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal).
Which one of the following is a legal program counter (all values in decimal)?
(A) 400
(B) 500
(C) 600
(D) 700

10. In a binary max heap containing n numbers, the smallest element can be found  in time
( )
(A) O n
( )
(B) O n log
( )
(C) O n loglog
( )
(D) O 1

{ }
11. Consider a weighted complete graph G on the vertex set , ,…., such that the weight of the edge , is 2 – . i j The weight of a minimum spanning tree
i j
of G is:
(A) 1 n -
(B) 2 2 n -
˜ ’ n
(C) 2 ÷
«
(D) n 2

12. To implement Dijkstra‘s shortest path algorithm on unweighted graphs so that it  runs in linear time, the data structure to be used is:
(A) Queue

(B) Stack
(C) Heap
(D) B-Tree

13. A scheme for storing binary trees in an array X is as follows. Indexing of X sta rts  at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left  child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to  store any binary tree on n vertices the minimum size of X should be
(A) log n
2
(B) n
(C) 2 1 n +
(D) 2 1 – n

14. Which one of the following in place sorting algorithms needs the minimum  number of swaps?
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort

15. Consider the following C-program fragment in which , and n i j are integer
variables.
( )
for i = n, j = 0; i > 0; i /= 2, j +=i ;
( )
Let val j denote the value stored in the variable j after termination of the
forloop. Which one of the following is true?
( ) ( ) = (A) valj n log
( )
( ) (B) valj n =
( ) ( ) (C) valj n =
( ) ( ) (D) valj n n = log

16. Let S be an NP-complete problem and Q and R be two other problems not known  to be in NP. Q is polynomial time reducible to S and S is polynomial-time  reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard

17. An element in an array X is called a leader if it is greater than all elements to the  right of it in X. The best algorithm to find all leaders in an array
(A) Solves it in linear time using a left to right pass of the array
(B) Solves it in linear time using a right to left pass of the array
( )
(C) Solves it using divide and conquer in time n n log
( )
(D) Solves it in time n 2

{ }
18. We are given a set X x x x = = , …… where 2 . A sample S X is drawn by  selecting each x independently with probability 1 . p = The expected value of the  smallest number in sample S is:

(A) 1
n
(B) 2
(C) n
(D) n

{ } { }
19. Let L n m L n m = = = = 0 1 0 , 0 , 0 1 0 , 0 ,  and n m n m n m n m m + + +
1 2
{ }
L n m = = 0 1 0 , 0 . Which of these languages are NOT context free? n m n m n m + + +
3
(A) L only
1
(B) L only
3
(C) L L and
1 2
(D) L L and
2 3

20. Consider the following log sequence of two transactions on a bank account, with  initial balance 12000, that transfer 2000 to a mortgage payment and then apply
a 5% interest.
1. T1 start
2. T1 B old=1200 new=10000
3. T1 M old=0 new=2000
4. T1 commit
5. T2 start
6. T2 B old=10000 new=10500
7. T2 commit
Suppose the database system cra shes just before log record 7 is written. When  the system is restarted, which one statement is true of the recovery procedure?
(A) We must redo log record 6 to set B to 10500
(B) We must undo log record 6 to set B to 10000 and then redo log records 2  and 3

(C) We need not redo log records 2 and 3 because transaction T1 has committed

(D) We can apply redo and undo operations in arbitrary order because they are  idempotent.

Q.21 œ Q.75 Carry Two Marks Each

21. For each element in a set of size 2 , n an unbiased coin is tossed. The 2n coin  tosses are independent. An element is chosen if the corresponding coin toss were  head. The probability that exactly n elements are chosen is:
2 n ˜ ’
÷
n «
(A)
4
n
2 n ˜ ’
÷
n «
(B)
2
n

(C) 1
2n ˜ ’
÷
n
«

(D) 1
2

22. Let E, F and G be finite sets.
( ) ( ) ( ) ( ) ( )
Let X E F F G Y E E G E F and . = – = – - – < < <
Which one of the following is true?
(A) X Y
(B) X Y
(C) X Y =
(D) and X Y Y X – Ø – Ø

23. F is an n n real matrix. b is an 1 n real vector. Suppose there are two × ×
1 n vectors, and u such that , u and Which one of the ×  Fu b F b = = , .
following statements is false?
(A) Determinant of F is zero
(B) There are an infinite number of solutions to Fx = b
(C) There is an 0 x such that 0 Fx =
(D) F must have two identical rows

{ } 24. Given a set of elements N n 1, 2,….., and two arbitrary subsets =
how many of the ! n permutations from N to N satisfy A N B N and ,  p
( ) ( ) ( ) ( ) ( ) min min , p p A B where min S is the smallest integer in the set of =

( ) integers S S , and p is the set of integers obtained by applying permutation p to  each element of ? S
( )
(A) n A B A B – G
( )
(B) A B n + 2 2 2

<
(C) ! A B n A B
G
n ˜ ’
(D) A B A B < G 2 ÷
«

{ } 25. Let S m m = > 1, 2, 3, …….., , 3. Let X X be subsets of S each of size 3. ……
1 n
( ) Define a function f from S to the set of natural numbers as, f i is the number of
{ } ( ) sets X that contain the element . i That is f i j i X = .
j    j
ƒ ( ) m
Then f i is:

i = 1
(A) 3m
(B) 3n
(C) 2 1 m +
(D) 2 1 n +
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) x x x x x x tiger lion hungry threatened attacks
/
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) »  ÿ (B) x x x x x x tiger lion hungry threatened attacks
/
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) »  ÿ (C) x x x x x x tiger lion attacks hungry threatened
/
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) »  ÿ (D) x x x x x x tiger lion hungry threatened attacks
/

27. Consider the following propositional statements:
) ( ) ( ) ( ) ( ) ( ) P A B C A C B C 1: =
) ( ) ( ) ( ) ( ) ( ) P A B C A C B C 2 : =
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 , is defined as follows: W

A B A B W
True True True
True False True
False True False
False False True

Let ~ be the unary negation (NOT) operator, with higher precedence then . W
Which one of the following is equivalent to ? A B
( ) (A) ~ A B W
( ) (B) ~ ~ A B W
( ) (C) ~ ~ ~ A B W
( ) (D) ~ ~ A B W

( ) ( )
29. If s is a string over 0 1 + then let n s denote the number of 0‘s in *
0
( ) s n s the number of 1‘s in . and s Which one of the following languages is not
1
regular?
{ } ( ) ( )
(A) L s n s = + 0 1 * is a 3-digit prime
0
{ } ( ) ( ) ( ) ‘ ‘ ‘ (B) L s s s n s n s = + – = 0 1 * for every prefix of , 2
0 1
{ } ( ) ( ) ( )
(C) L s n s n s = + – = 0 1 * 4
0 1
{ } ( ) ( ) ( )
(D) L s n s n s = + = = 0 1 * mod 7 mod 5 0
0 1

( ) ( ) ( ) 30. For S + 0 1 * let d s denote the decimal value of s (e.g. d 101 5 = ).
{ } ( ) ( ) ( ) Let L s d s d s = + = 0 1 * mod5 2 and mod7 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 SHAM be the problem of finding a Hamiltonian cycle in a graph
3
( ) G V E = , with V divisible by 3 and DHAM be the problem of determining if
Hamiltonian cycle exists in such graphs. Which one of the following is true?

(A) Both DHAM and SHAM are NP-hard
3 3
(B) SHAM is NP-hard, but DHAM is not
3  3
(C) DHAM is NP-hard, but SHAM is not
3  3
(D) Neither DHAM nor SHAM is NP-hard
3 3

32. Consider the following statements about the context free grammar
{ } G S SS S abS ba S = , , ,
I. G is ambiguous
II. G produces all strings with equal number of a‘s and b‘s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
(A) I only
(B) I and III only
(C) II and III only
(D) I, II and III

33. Let L be a regular language, L be a deterministic context-free language and L a
1  2   3
recursively enumerable, but not recursive, language. Which one of the following
statements is false?
(A) L L < is a deterministic CFL
1 2
(B) L L < is recursive
3 1
(C) L L G is context free
1 2
(D) L L L < < is recursively enumerable
1 2 3

( ) 34. Consider the regular language L = + 111 11111 * . The minimum number of  states in any DFA accepting this languages is:
(A) 3
(B) 5
(C) 8
(D) 9

Consider the circuit above. Which one of the following options correctly
( ) represents f x y z , , ?
(A) x z xy y z + +
(B) x z xy yz + +
(C) xz xy yz + +
(D) xz x y yz + +

36. Given two three bit numbers a a a bbb c the carry in, the function and and ,  that represents the carry generate function when these two numbers are added
is:
(A) a b a a b a a a b a a bb a bb a a bb a bbb + + + + + +
2 2 2 1 1 2 1 0 0 2 0 1 0 1 2 1 1 0 2 0 0 2 1 0
(B) a b a bb a a bb a a bb a a b a a bb a a bb + + + + + +
2 2 2 1 0 2 1 1 0 1 0 2 1 1 0 2 1 0 2 0 2 0 1 0
( ) ( ) ( ) ( ) (C) a b a b a b a b a b + + + + +
2 2 2 2 1 1 1 1 0 0
(D) a b a a b a a a b a a bb a bb a a bb a bbb + + + + + +
2 2 2 1 1 2 1 0 0 2 0 1 0 1 2 1 1 0 2 0 0 2 1 0

37. Consider the circuit in the diagram. The operator represents Ex-OR. The D flip-
flops are initialized to zeroes (cleared).

The following data: 100110000 is supplied to the —data“ terminal in nine clock  cycles. After that the values of qqq are:
2 1 0
(A) 000
(B) 001
(C) 010
(D) 101

( ) 38. Consider a Boolean function f w x y z suppose that exactly one of its inputs is ,  allowed to change at a time. If the function happens to be true for two input  vectors i w x y z = , , , and i w x y z = , , , , we would like the function to  1 1 1 1 1  2 2 2 2 2
remain true as the input changes from
( ) i i i i without becoming false to and differ in exactly one bit position ,
ƒ ( ) ( ) momentarily. Let f w x y z , , , 5,7,11,12, 13,15 . = Which of the following cube
covers of f will ensure that the required property is satisfied?
(A) , , , , wxz wx y xy z xyz wyz
(B) , , wxy wxz wyz
(C) , , wxyz xz wxyz
(D) , , , , , wzy wyz wxz wxz x yz xyz

39. We consider the addition of two 2‘s complement numbers b b b …. and
n n – - 1 2 0
a a a …. . A binary adder for adding unsigned binary numbers is used to add
n n – - 1 2 0
the two numbers. The sum is denoted by c c c …. and the carry-out by . c
n n – - 1 2 0  ou t
Which one of the following options correctly identifies the overflow condition?
( )

40. Consider numbers represented in 4-bit gray code. Let h h h h be the gray code
3 2 1 0
representation of a number n and let gggg be the gray code of
3 2 1 0
( ) ( ) n + 1 modulo 16 value of the number. Which one of the following functions is
correct?
ƒ ( ) ( ) (A) g h h h h = 1, 2, 3,6,10,13,14,15
ƒ ( ) ( ) (B) g h h h h = 4,9,10,11,12,13,14, 15
ƒ ( ) ( ) (C) g h h h h = 2, 4,5, 6, 7,12, 13,15
ƒ ( ) ( ) (D) g h h h h = 0,1, 6, 7, 10,11,12,13

41. A CPU has a cache with block size 64 bytes. The main memory has k banks, each
bank being c bytes wide. Consecutive c – byte chunks are mapped on
consecutive banks with wrap-around. All the k banks can be accessed in parallel,  but two accesses to the same bank must be serialized. A cache block access may  involve multiple iterations of parallel bank accesses depending on the amount of  data obtained by accessing all the k banks in parallel. Each iteration requires k ns The  decoding the bank numbers to be accessed in parallel and this takes .   latency of one bank access is 80 ns. If the latency of retrieving c k = = 2 and 24,
a cache block starting at address zero from main memory is:
(A) 92 ns
(B) 104 ns
(C) 172 ns

(D) 184 ns

42. A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch  happens in the first stage of the pipeline. A conditional branch instruction  computes the target address and evaluates the condition in the third stage of the  pipeline. The processor stops fetching new instructions following a conditional  branch until the branch outcome is known. A program executes 10 instructions 9 out of which 20% are conditional branches. If each instruction takes one cycle to  complete on average, the total execution time of the program is:
(A) 1.0 second
(B) 1.2 seconds
(C) 1.4 seconds
(D) 1.6 seconds

43. Consider a new instruction named branch-on-bit-set (mnemonic bbs). The  instruction —bbs reg, pos, label“ jumps to label if bit in position pos of register  operand reg is one. A register is 32 bits wide and the bits are numbered 0 to 31,  bit in position 0 being the least significant. Consider the following emulation of  this instruction on a processor that does not have bbs implemented.  temp reg & mask
Branch to label if temp is non-zero.

The variable temp is a temporary register. For correct emulation, the variable
(A) 0 1 mask pos × 0
(B) 0 mask ffffffff pos × 2

44. Station A uses 32 byte packets to transmit messages to Station B using a sliding  window protocol. The round trip delay between A and B is 80 milliseconds and  the bottleneck bandwidth on the path between A and B is 128 kbps. What is the  optimal window size that A should use?
(A) 20
(B) 40
(C) 160
(D) 320

45. Two computers C1 and C2 are configured as follows. C1 has IP address
and netmask 255.255.192.0. which one of the following statements is true?

(A) C1 and C2 both assume they are on the same network
(B) C2 assumes C1 is on same network, but C1 assumes C2 is on a different
network
(C) C1 assumes C2 is on same network, but C2 assumes C1 is on a different
network
(D) C1 and C2 both assume they are on different networks.

46. Station A needs to send a message consisting of 9 packets to Station B using a  sliding window (window size 3) and go-back-n error control strategy. All packets  are ready and immediately available for transmission. If every 5 packet that A th transmits gets lost (but no acks from B ever get lost), then what is the number of  packets that A will transmit for sending the message to B?
(A) 12
(B) 14
(C) 16
(D) 18

47. Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that
to a minimum spanning tree using Kruskal‘s algorithm? order,
( ) ( ) ( ) ( ) ( ) (A) a b d f b f d c d e – - – - – , , , ,
( ) ( ) ( ) ( ) ( ) (B) a b d f d c b f d e – - – - – , , , ,
( ) ( ) ( ) ( ) ( ) (C) d f a b d c b f d e – - – - – , , , ,
( ) ( ) ( ) ( ) ( ) (D) d f a b b f d e d c – - – - – , , , ,

48. Let T be a depth first search tree in an undirected graph G. Vertices and u are  leaves of this tree . T The degrees of both and u in G are at least 2. which one  of the following statements is true?
(A) There must exist a vertex w adjacent to both and u in G
(B) There must exist a vertex w whose removal disconnects and u in G
(C) There must exist a cycle in G containing and u
(D) There must exist a cycle in G containing u and all its neighbours in G.

49. An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert (Q, x) {
push (S1, x);
}
void delete (Q) {
if (stack-empty(S2)) then
if (stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
( )
Let n and m n = operations be performed in an arbitrary order insert delete
on an empty queue Q. Let and x y be the number of and operations push pop
performed respectively in the process. Which one of the following is true for all
and ? m n
(A) 2 and 2 n m x n m y n m + = < = = +
(B) 2 and 2 2 n m x n m y n + = < = =
(C) 2 2 and 2 m x n m y n m = < = = +
(D) 2 2 and 2 2 m x n m y n = < = =

50. A set X can be represented by an array x n » ÿ / as follows:
i X À
1 if x i »ÿ Ã = / Õ
0 otherwise
Consider the following algorithm in which , and z x y are Boolean arrays of size n:
algorithm zzz(x[ ], y[ ], z [ ] ) {
int i;

for(i=0;i<n;++i)
z[i] = (x[i] ~y[i]) (~x[i] y[i])
}
The set Z computed by the algorithm is:
( ) (A) X Y G
( ) (B) X Y <
( ) ( ) (C) X Y Y X < – -
( ) ( ) (D) X Y Y X G – -

51. Consider the following recurrence:
( )
( ) ( ) » ÿ T n T n T 2 1, 1 1 = + =
… Ÿ
Which one of the following is true?
( ) ( ) (A) T n n loglog =
( ) ( ) (B) T n n log =
( )
( ) (C) T n n =
( ) ( ) (D) T n 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) n
( ) (B) n n log
( )
(C) n 2
( )
(D) n 3

53. Consider the following C-function in which and a n bm » ÿ » ÿ / /are two sorted integer  arrays and c n m » ÿ + /be another integer array.
void xyz(int a[], int b [], int c []){
int i,j,k;
i=j=k=0;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
Which of the following condition(s) hold(s) after the termination of the while
loop?
(i) , 1, and 1 if j m k n j a n b j i n » ÿ » ÿ < = + – - < = / /
(ii) , 1, and 1 if i n k m i bm a i j 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 a a b bwhere each number is 0 or 1, ,…, and ,…,
1 1 n n
( ) the fastest algorithm to find the largest span i j such that ,
a a a b b b + + + = + + + … … , or report that there is not such span,
i i j i i j + + 1 1
( ) ( )
O (A) Takes 3 and 2 time if hashing is permitted n n
( ) ( )
O n n (B) Takes and time in the key comparison model 3 2.5
( ) n (C) Takes T time and space
( )
O n (D) Takes time only if the sum of the 2n elements is an even number

55. Consider these two functions and two statements S1 and S2 about them.

int work1(int *a, int i, int j) int work2(int *a, int i, int j)

{ {

int x = a[i+2]; int t1 = i+2;
a[j] = x+1; int t2 = a[t1];
return a[i+2] – 3; a[j] = t2+1;
} return t2 – 3;
}

S1: The transformation form work1 to work2 is valid, i.e., for any program state  and input arguments, work2 will compute the same output and have the same  effect on program state as work1

S2: All the transformations applied to work1 to get work2 will always improve the  performance (i.e reduce CPU time) of work2 compared to work1
(A) S1 is false and S2 is false
(B) S1 is false and S2 is true
(C) S1 is true and S2 is false
(D) S1 is true and S2 is true

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
L1 : ix = iy
L2 : iy = it
end
ia = 3
ib = 8
call swap (ia, 1b+5)
print *, ia, ib
end

S1: The compiler will generate code to allocate a temporary nameless cell,
initialize it to 13, and pass the address of the cell swap
S2: On execution the code will generate a runtime error on line L1
S3: On execution the code will generate a runtime error on line L2
S4: The program will print 13 and 8
S5: The program will print 13 and -2
Exactly the following set of statement(s) is correct:
(A) S1 and S2
(B) S1 and S4
(C) S3
(D) S1 and S5

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

void swap (int *px, int *py) {
*px = *px – *py;
*py = *px + *py;
*px = *py – *px;
}

S1: 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 swa p procedure correctly for some but not all valid input  pointers
S5: may add or subtract integers and pointers.
(A) S1
(B) S2 and S3
(C) S2 and S4
(D) S2 and S5

58. Consider the following grammar:
S FR
R S e *
F id
In the predictive parser table, M, of the grammar the entries
M S id M R » ÿ » ÿ , and , \$ respectively. / /
{ } { } S FR R e (A) and
{ } { } S FR (B) and
{ } { } S FR R S (C) and *
{ } { } F id R e (D) and

59. Consider the following translation scheme.
S ER
{ } ( ) R E R e * print’*';
{ }  ( ) E F E F + print’+';
{ } ( ) ( ) F S id printid.value ;
id  id value Here is a token that represents an integer and . represents the
corresponding integer value. For an input ’2 * 3 4′, + this translation scheme
prints
(A) 2 * 3 4 +
(B) 2 * 3 4 +
(C) 2 3 * 4 +
(D) 2 3 4+*

60. Consider the following C code segment.
for (i – 0, i<n; i++) {
for (j=0; j<n; j++) {
if (i%2) {
x += (4*j + 5*i);
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

fetch-and-set 61. The atomic 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 S V functions on a binary semaphore .
void P (binary_semaphore *s) {
unsigned y;
unsigned *x = &(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
fetch-and œset (B) Instead of using , 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% of time doing computation, and the last 10% 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) 10.6%
(C) 30.0%
(D) 89.4%

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  decrea sing 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)
Query1: 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 Query1 and Query2.
1. Query1 will produce the same row set as Query2 for some but not all
databases.
2. Both Query1 and Query2 are correct implementation of the specification
3. Query1 is a correct implementation of the specification but Query2 is not
4. Neither Query1 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

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:
Query1: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 Query1 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
Probe index Sequential Probe index
scan, select on student on student Sequential scan
amount > x
Indexed nested loop join Indexed nested loop join
Project on course Select on amount > x
Project on course

A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a  x tuple to see if amount is greater than takes 10 s. 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
databases
(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.

70. The following functional dependencies are given:
, , , , , . AB CD AF D DE F C G F E G A
Which one of the following options is false?
{ } { } CF ACDEFG (A) + =
{ } { } BG ABCDG (B) + =
{ } { } AF ACDEFG (C) + =
{ } { } AB ABCDFG (D) + =

Common Data Questions:

Com mon Data for Questions 71, 72, 73:
n The 2 vertices of a graph G corresponds to all subsets of a set of size n, for 6 = . Two n 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
n (C) 1 +
(D) 2 n

72. The maximum degree of a vertex in G is:
˜ ’ n 2 2
(A) ÷ n 2
2 «
(B) 2 n – 2

(C) 2 3 × n – 3

(D) 2 n – 1

73. The number of connected components in G is:
(A) n
n (B) 2 +
(C) 2 n 2

n
(D) 2
n

Com mon 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-1 multiplexer has a latency of 0.6 ns while a k-
bit comparator has a latency of 10 k ns. The hit latency of the set associative
organization is h while that of the direct mapped one is h .
1   2
74. The value of h is:
1
(A) 2.4 ns
(B) 2.3 ns
(C) 1.8 ns
(D) 1.7 ns

75. The value of h is:
2
(A) 2.4 ns
(B) 2.3 ns
(C) 1.8 ns
(D) 1.7 ns

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 ma x 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

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the ba rrier 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 ba rrier 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.

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two-dimensional 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=0; j<512; j++) {
x +=A[i] [j];
}
}

P2: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[j] [i];
}
}
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 M and that for P2 be M .
1  2
80. The value of M is:
1
(A) 0
(B) 2048
(C) 16384
(D) 262144

M
81. The value of the ratio 1
M is:
2
(A) 0

(B) 1
16

(C) 1
8
(D) 16

Consider the diagram shown below where a number of LANs 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 forwa rding 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) B1, B5, B3, B4, B2
(B) B1, B3, B5, B2, B4
(C) B1, B5, B2, B3, B4
(D) B1, B3, B4, B5, B2

83. Consider the correct spanning tree for the previous question. Let host H1 send  out a broadcast ping packet. Which of the following options represents the  correct forwarding table on B3?
(A) (B)

Hosts Port
H1, H2, H3, H4 3
H5, H6, H9, H10 1

84. Which one of the following grammars generates the language L a b i j = ?

(A) (B) S aS Sba b

S AC CB
C aCba b

A a A
B Bb
(C) (D)
S AC CB  S AC CB
C aCb  C aCb

A a A  A a A a
B Bb  B Bbb
85. In the correct grammar above, what is the length of the derivation (number of  steps starring from S) to generate the string a b with l m ? l m
( )
(A) max , 2 lm +
(B) 2 l m + +
(C) 3 l m + +
( )
(D) max , 3 lm +