CSS

GS-2017
(Computer & Systems Sciences)
TATA INSTITUTE OF FUNDAMENTAL RESEARCH

WrittenTestinCOMPUTER&SYSTEMSSCIENCESDecember11,2016
Duration:Threehours(3hours)

Name:_______________________________________________Ref.Code:____________


Pleasereadallinstructionscarefullybeforeyouattemptthequestions.

1. Please fillin details about name, reference code etc. on the answer sheet. The Answer
Sheetismachinereadable.UseonlyBlack/Blueballpointpentofillintheanswersheet.

2. Indicate your ANSWER ON THE ANSWER SHEET by blackening the appropriate circle for
eachquestion.Donotmarkmorethanonecircleforanyquestion:thiswillbetreatedasa
wronganswer.

3. Thisquestionpaperconsistsofthree(3)parts.PartAcontainsfifteen(15)questionsand
must be attempted by all candidates. PartB & PartC contain fifteen (15) questions
each, directed towards candidates for (B) Computer Science and (C) Systems Science
(including Communcations and Applied Probability), respectively. STUDENTS MAY
ATTEMPTEITHERPARTBORPARTC.Incase,astudentattemptsbothPartsB&C(no
extra time will be given) and qualifies for interview in both B & C, he/she will have
opportunitytobeinterviewedinbothareas.Allquestionscarryequalmarks.Acorrect
answerforaquestionwillgiveyou+4marks,awronganswerwillgiveyou1mark,anda
questionnotansweredwillnotgetyouanymarks.

4. We advise you to first mark the correct answers in the QUESTION SHEET and then to
TRANSFERthesetotheANSWERSHEETonlywhenyouaresureofyourchoice.

5. Roughworkmaybedoneonblankpagesofthequestionpaper.Ifneeded,youmayaskfor
extraroughsheetsfromanInvigilator.

6. Useofcalculators,mobilephones,laptops,tablets(orotherelectronicdevices,including
thoseconnectingtotheinternet)isNOTpermitted.

7. DoNOTaskforclarificationsfromtheinvigilatorsregardingthequestions.Theyhavebeen
instructed not to respond to any such inquiries from candidates. In case a
correction/clarificationisdeemednecessary,theinvigilator(s)willannounceitpublicly.

CSS 2017 Common Part Page 1 of 17

Part A: Common Part

1. A suitcase weighs one kilogram plus half of its weight. How much does the suitcase
weigh?
(a) 1.333... kilograms
(b) 1.5 kilograms
(c) 1.666... kilograms
(d) 2 kilograms
(e) cannot be determined from the given data

2. For vectors x, yin Rn , dene the inner product x, y = ni=1 xi yi , and the length of
x to be x = x, x. Let a, b be two vectors in Rn so that b = 1. Consider the
following statements:

(i) a, b b

(ii) a, b a
(iii) a, b = ab
(iv) a, b b
(v) a, b a

Which of the above statements must be TRUE of a, b? Choose from the following
options.
(a) (ii) only
(b) (i) and (ii)
(c) (iii) only
(d) (iv) only
(e) (iv) and (v)

3. On planet TIFR, the acceleration of an object due to gravity is half that on planet
earth. An object on planet earth dropped from a height h takes time t to reach the
ground. On planet TIFR, how much time would an object dropped from height h
take to reach the ground?

(a) t/ 2

(b) 2t
(c) 2t
(d) h/t
(e) h/2t
CSS 2017 Common Part Page 2 of 17
4. Which of the following functions asymptotically grows the fastest as n goes to innity?
(a) (log log n)!
(b) (log log n)log n
(c) (log log n)log log log n
(d) (log n)log log n

log log n
(e) 2

5. How many distinct ways are there to split 50 identical coins among three people so
that each person gets at least 5 coins?
(a) 335
(b) 350 250
 
(c) 35
2
50 35
(d) 15 3
 
(e) 37
2

6. How many distinct words can be formed by permuting the letters of the word
ABRACADABRA?
11!
(a)
5! 2! 2!
11!
(b)
5! 4!
(c) 11! 5! 2! 2!
(d) 11! 5! 4!
(e) 11!

7. Consider the sequence S0 , S1 , S2 , . . . dened as follows: S0 = 0, S1 = 1, and Sn =

2Sn1 + Sn2 for n 2. Which of the following statements is FALSE?
(a) for every n 1, S2n is even
(b) for every n 1, S2n+1 is odd
(c) for every n 1, S3n is a multiple of 3
(d) for every n 1, S4n is a multiple of 6
(e) none of the above
CSS 2017 Common Part Page 3 of 17
8. In a tutorial on geometrical constructions, the teacher asks a student to construct a
right-angled triangle ABC where the hypotenuse BC is 8 inches and the length of
the perpendicular dropped from A onto the hypotenuse is h inches, and oers various
choices for the value of h. For which value of h can such a triangle NOT exist?
(a) 3.90 inches

(b) 2 2 inches

(c) 2 3 inches
(d) 4.1 inches
(e) none of the above

9. Consider the majority function on three bits, maj : {0, 1}3 {0, 1}, where maj(x1 , x2 , x3 ) =
1 if and only if x1 +x2 +x3 2. Let p() be the probability that the output is 1 when
each input is set to 1 independently with probability . What is p () = d d
p()?
(a) 3
(b) 2
(c) 6(1 )
(d) 32 (1 )
(e) 6(1 ) + 2

10. For a set A, dene P(A) to be the set of all subsets of A. For example, if A = {1, 2},
then P(A) = {, {1, 2}, {1}, {2}}. Let f : A P(A) be a function and A is not
empty. Which of the following must be TRUE?
(a) f cannot be one-to-one (injective)
(b) f cannot be onto (surjective)
(c) f is both one-to-one and onto (bijective)
(d) there is no such f possible
(e) if such a function f exists, then A is innite

11. Let f g denote function composition such that (f g)(x) = f (g(x)). Let f : A B
such that for all g : B A and h : B A we have f g = f h g = h. Which of
the following must be TRUE?
(a) f is onto (surjective)
(b) f is one-to-one (injective)
(c) f is both one-to-one and onto (bijective)
(d) the range of f is nite
(e) the domain of f is nite
CSS 2017 Common Part Page 4 of 17
12. Consider the following program modifying an n n square matrix A:

for i = 1 to n:
for j = 1 to n:
temp = A[i][j] + 10
A[i][j] = A[j][i]
A[j][i] = temp - 10
end for
end for

Which of the following statements about the contents of the matrix A at the end of
this program must be TRUE ?
(a) the new A is the transpose of the old A
(b) all elements above the diagonal have their values increased by 10 and all values
below have their values decreased by 10
(c) all elements above the diagonal have their values decreased by 10 and all values
below have their values increased by 10
(d) the new matrix A is symmetric, that is, A[i][j] = A[j][i] for all 1 i, j n
(e) A remains unchanged

13. A set of points S R2 is convex if for any points x, y S, every point on the
straight line joining x and y is also in S. For two sets of points S, T R2 , dene the
sum S + T as the set of points obtained by adding a point in S to a point in T . That
is, S + T := {(x1 , x2 ) R2 : x1 = y1 + z1 , x2 = y2 + z2 , (y1 , y2 ) S, (z1 , z2 ) T }.
Similarly, S T := {(x1 , x2 ) R2 : x1 = y1 z1 , x2 = y2 z2 , (y1 , y2 ) S, (z1 , z2 )
T } is the set of points obtained by subtracting a point in T from a point in S. Which
of the following statements is TRUE for all convex sets S, T ?
(a) S + T is convex, but not S T
(b) S T is convex, but not S + T
(c) exactly one of S + T and S T is convex, but it depends on S and T which one
(d) neither S + T nor S T is convex
(e) both S + T and S T are convex
CSS 2017 Common Part Page 5 of 17
14. Consider the following game with two players, Aditi and Bharat. There are n tokens
in a bag. The players know n, and take turns removing tokens from the bag. In each
turn, a player can either remove one token or two tokens. The player that removes
the last token from the bag loses. Assume that Aditi always goes rst. Further, we
say that a player has a winning strategy if she or he can win the game, no matter
what the other player does. Which of the following statements is TRUE?
(a) For n = 3, Bharat has a winning strategy. For n = 4, Aditi has a winning strategy
(b) For n = 7, Bharat has a winning strategy. For n = 8, Aditi has a winning strategy
(c) For both n = 3 and n = 4, Aditi has a winning strategy
(d) For both n = 7 and n = 8, Bharat has a winning strategy
(e) Bharat never has a winning strategy

15. Let T (a, b) be the function with two arguments (both nonnegative integral powers
of 2) dened by the following recurrence:
a  
b
T (a, b) = T , b + T a, if a, b 2;
2 2
a 
T (a, 1) = T ,1 if a 2;
2
b
T (1, b) = T 1, if b 2;
2
T (1, 1) = 1.

What is T (2r , 2s )?
(a) rs
(b) r + s
 r
2 + 2s
(c)
2r

r+s
(d)
r
(e) 2rs if r s, otherwise 2sr
CSS 2017 CS Part Page 6 of 17

Part B: Computer Science

1. A vertex colouring with three colours of a graph G = (V, E) is a mapping c : V
{R, G, B} so that adjacent vertices receive distinct colours. Consider the following
undirected graph.

w1

v1

u1

u3 u2
v3 v2
w3 w2

How many vertex colourings with three colours does this graph have?
(a) 39
(b) 63
(c) 3 28
(d) 27
(e) 24

2. Consider the following statements:

(i) Checking if a given undirected graph has a cycle is in P.

(ii) Checking if a given undirected graph has a cycle is in NP.
(iii) Checking if a given directed graph has a cycle is in P.
(iv) Checking if a given directed graph has a cycle is in NP.

Which of the above statements is/are TRUE? Choose from the following options.

(a) Only (i) and (ii)

(b) Only (ii) and (iv)
(c) Only (ii), (iii), and (iv)
(d) Only (i), (ii), and (iv)
(e) All of them
CSS 2017 CS Part Page 7 of 17
3. We have an implementation that supports the following operations on a stack (in the
instructions below, s is the name of the stack).

isempty(s): returns True if s is empty, and False otherwise .

top(s): returns the top element of the stack, but does not pop the stack; returns
null if the stack is empty.
push(s,x): places x on top of the stack.
pop(s): pops the stack; does nothing if s is empty.

Consider the following code:

pop_ray_pop(x):
s = empty
for i = 1 to length(x):
if (x[i] == ():
push(s,x[i])
else:
while (top(s) == ():
pop(s)
end while
push(s, ))
end if
end for

while not isempty(s):

print top(s)
pop(s)
end while

What is the output of this program when

pop_ray_pop("(((()((())((((")

is executed ?
(a) ((((
(b) )))((((
(c) )))
(d) (((()))
(e) ()()
CSS 2017 CS Part Page 8 of 17
4. Let L be the language over the alphabet {1, 2, 3, (, )} generated by the following
grammar (with start symbol S, and non-terminals {A, B, C}):

S AB C
A (
B 1B | 2B | 3B
B 1 | 2 | 3
C )

Then, which of the following is TRUE?

(a) L is nite
(b) L is not recursively enumerable
(c) L is regular
(d) L contains only strings of even length
(e) L is context-free but not regular

5. Consider the following pseudocode fragment, where y is an integer that has been
initialized.

int i = 1
int j = 1
while (i < 10):
j = j * i
i = i + 1
if (i==y):
break
end if
end while

Consider the following statements:

(i) (i == 10) or (i == y)
(ii) If y > 10, then i == 10
(iii) If j = 6, then y == 4

Which of the above statements is/are TRUE at the end of the while loop? Choose
from the following options.
(a) (i) only
(b) (iii) only
(c) (ii) and (iii) only
(d) (i), (ii), and (iii)
(e) None of the above
CSS 2017 CS Part Page 9 of 17
6. Consider First Order Logic (FOL) with equality and suitable function and relation
symbols. Which one of the following is FALSE?
(a) Partial orders cannot be axiomatized in FOL
(b) FOL has a complete proof system
(c) Natural numbers cannot be axiomatized in FOL
(d) Real numbers cannot be axiomatized in FOL
(e) Rational numbers cannot be axiomatized in FOL

7. An array of n distinct elements is said to be un-sorted if for every index i such that
2 i n 1, either A[i] > max{A[i 1], A[i + 1]}, or A[i] < min{A[i 1], A[i + 1]}.
What is the time-complexity of the fastest algorithm that takes as input a sorted
array A with n distinct elements, and un-sorts A?
(a) O(n log n) but not O(n)

(b) O(n) but not O( n)

(c) O( n) but not O(log n)
(d) O(log n) but not O(1)
(e) O(1)

8. For any natural number n, an ordering of all binary strings of length n is a Gray code
if it starts with 0n , and any successive strings in the ordering dier in exactly one bit
(the rst and last string must also dier by one bit). Thus, for n = 3, the ordering
(000, 100, 101, 111, 110, 010, 011, 001) is a Gray code. Which of the following must
be TRUE for all Gray codes over strings of length n?
(a) the number of possible Gray codes is even
(b) the number of possible Gray codes is odd
(c) in any Gray code, if two strings are separated by k other strings in the ordering,
then they must dier in exactly k + 1 bits
(d) in any Gray code, if two strings are separated by k other strings in the ordering,
then they must dier in exactly k bits
(e) none of the above

9. Which of the following regular expressions correctly accepts the set of all 0/1-strings
with an even (possibly zero) number of 1s?
(a) (10 10 )
(b) (0 10 1)
(c) 0 1(10 1) 10
(d) 0 1(0 10 10 ) 10
(e) (0 10 1) 0
CSS 2017 CS Part Page 10 of 17
10. A vertex colouring of a graph G = (V, E) with k colours is a mapping c : V
{1, . . . , k} such that c(u) = c(v) for every (u, v) E. Consider the following state-
ments:

(i) If every vertex in G has degree at most d, then G admits a vertex colouring
using d + 1 colours.
(ii) Every cycle admits a vertex colouring using 2 colours.
(iii) Every tree admits a vertex colouring using 2 colours.

Which of the above statements is/are TRUE? Choose from the following options.
(a) only (i)
(b) only (i) and (ii)
(c) only (i) and (iii)
(d) only (ii) and (iii)
(e) (i), (ii), and (iii)

11. Given that

B(x) means x is a bat,
F (x) means x is a y, and
E(x, y) means x eats y,
what is the best English translation of

x(F (x) y(E(y, x) B(y)))?

(a) all ies eat bats

(b) every y is eaten by some bat
(c) bats eat only ies
(d) every bat eats ies
(e) only bats eat ies

12. An undirected graph is complete if there is an edge between every pair of vertices.
Given a complete undirected graph on n vertices, in how many ways can you choose
a direction for the edges so that there are no directed cycles?
(a) n
n(n 1)
(b)
2
(c) n!
(d) 2n
n(n 1)
(e) 2m , where m =
2
CSS 2017 CS Part Page 11 of 17
  
13. For an undirected graph G = (V, E), the line graph G = (V , E ) is obtained by
replacing each edge in E by a vertex, and adding an edge between two vertices in
V  if the corresponding edges in G are incident on the same vertex. Which of the
following is TRUE of line graphs?
(a) the line graph for a complete graph is complete
(b) the line graph for a connected graph is connected
(c) the line graph for a bipartite graph is bipartite
(d) the maximum degree of any vertex in the line graph is at most the maximum
degree in the original graph
(e) each vertex in the line graph has degree one or two

14. Consider the following grammar G with terminals {[, ]}, start symbol S, and non-
terminals {A, B, C}:
S AC | SS | AB
C SB
A [
B ]
A language L is called prex-closed if for every x L, every prex of x is also in L.
Which of the following is FALSE?
(a) L(G) is context free
(b) L(G) is innite
(c) L(G) can be recognized by a deterministic push down automaton
(d) L(G) is prex-closed
(e) L(G) is recursive.

15. A multivariate polynomial in n variables with integer coecients has a binary root
if it is possible to assign each variable either 0 or 1, so that the polynomial evaluates
to 0. For example, the multivariate polynomial 2x31 x1 x2 + 2 has the binary root
(x1 = 1, x2 = 0). Then determining whether a multivariate polynomial, given as the
sum of monomials, has a binary root:
(a) is trivial: every polynomial has a binary root
(b) can be done in polynomial time
(c) is NP-hard, but not in NP
(d) is in NP, but not in P and not NP-hard
(e) is both in NP and NP-hard
CSS 2017 SS Part Page 12 of 17

Part C: Systems Science

1. Consider a system which in response to input x(t) outputs

y(t) = 2x(t 2) + x(2t 1) + 1.

Which of the following describes the system?

(a) linear, time-invariant, causal
(b) linear, time-invariant, non-causal
(c) non-linear, time-invariant, causal
(d) non-linear, time-invariant, non-causal
(e) non-linear, time-variant

2. Suppose a 1H inductor and a 1 resistor are connected in series to a 1V battery.

What happens to the current in the circuit?
(a) The current starts at 0A, and gradually rises to 1A
(b) The current rises instantaneously to 1A and stays there after that
(c) The current rises instantaneously to 1A and then falls to 0A
(d) The current oscillates over time between 0A and 1A
(e) The current oscillates over time between 1A and -1A

3. What is the maximum average power that can be dissipated by a load connected to
the output terminals of the following circuit with an alternating current source?

1.15103
100
H 1.15 k

230 V 50 Hz load

(a) 23 W
(b) 11.5 W
(c) 8.1317 W
(d) 2.875 W
(e) None of the above
CSS 2017 SS Part Page 13 of 17
4. A Schmitt trigger circuit is a comparator circuit with a hysteresis. Consider the
Schmitt trigger circuit in the gure implemented using an opamp. What are the
trigger levels for this circuit?

R2

Vs
R1
+
Vi
Vo

Vs

R1
(a) Vs
R2
R2
(b) Vs
R1
R1
(c) Vs
R1 + R2
R2
(d) Vs
R1 + R2
(e) None of the above

5. Consider the inequality

1 2
n n 1,
n
where n is an integer 1. Which of the following statements is TRUE?
(a) This inequality holds for all integers n 1
(b) This inequality holds for all but nitely many integers n 1
(c) This inequality holds for only nitely many integers n 1
(d) This inequality does not hold for any integer n 1

(e) n n1 = n2 1 for innitely many integers n 1
CSS 2017 SS Part Page 14 of 17
6. Let a, b {0, 1}. Consider the following statements where is the and operator,
is exclusive-or, and c denotes the complement function.

(i) max{a b, b ac } = 1
(ii) max{a b, b ac } = 1
(iii) min{a b, b ac } = 0
(iv) min{a b, b ac } = 1

Which of the above statements is/are always TRUE? Choose from the following
options.
(a) (i) and (ii) only
(b) (ii) and (iii) only
(c) (iii) and (iv) only
(d) (iv) and (i) only
(e) None of the above

7. A circulant matrix is a square matrix whose each row is the preceding row rotated
to the right by one element, e.g., the following is a 3 3 circulant matrix.

1 2 3
3 1 2
2 3 1

For any n n circulant matrix (n > 5), which of the following n-length vectors is
always an eigenvector?
(a) A vector whose k-th element is k
(b) A vector whose k-th element is nk

2(n 5)k
(c) A vector whose k-th element is exp j where j = 1
n

2k
(d) A vector whose k-th element is sinh
n
(e) None of the above
CSS 2017 SS Part Page 15 of 17
8. Consider the two positive integer sequences, dened for a xed positive integer c 2
1 n c
f (n) = , g(n) = n ,
n c n
where t denotes the largest integer with value at most t. Which of the following
statements is TRUE as n ?
(a) Both sequences converge to zero
(b) The rst sequence does not converge, while the second sequence converges to 0
(c) The rst sequence converges to zero, while the second sequence does not converge
(d) The rst sequence converges to 1/c, while the second sequence converges to 0
(e) The rst sequence converges to 1/c, while the second sequence converges to c

9. Recall that for a random variable X which takes values in N, the set of natural
numbers, its entropy in bits is dened as


1
H(X) = pn log2 ,
n=1
pn

where, for n N, pn denotes the probability that X = n. Now, consider a fair coin
which is tossed repeatedly until a heads is observed. Let X be the random variable
which indicates the number of tosses made. What is the entropy of X in bits?
(a) 1
(b) 1.5

1+ 5
(c) 1.618 (the golden ratio)
2
(d) 2
(e) None of the above

10. Consider a single coin where the probability of heads is p (0, 1) and probability
of tails is 1 p. Suppose that this coin is ipped an innite number of times. Let
N1 denote the number of ips till we see heads for the rst time. Let N2 denote the
number of ips after the rst N1 ips, until a tails is observed for the rst time (on
ips observed after the rst N1 ips). What is the expected value of N1 + N2 ?
1 1
(a) +
1p p
1p p
(b) +
p 1p
2
(c)
p
1
(d) 2
p + (1 p)2
2
(e)
p(1 p)
CSS 2017 SS Part Page 16 of 17
11. Consider a unit length interval [0, 1] and choose a point X on it with uniform distri-
bution. Let L1 = X and L2 = 1 X be the length of the two sub-intervals created
by this point on the unit interval. Let L = max{L1 , L2 }. Consider the following
statements where E denotes expectation.

(i) E[L] = 3/4

(ii) E[L] = 2/3
(iii) L is uniformly distributed over [1/2, 1]
(iv) L is uniformly distributed over [1/3, 1]

Which of the above statements is/are TRUE? Choose from the following options.
(a) Only (i)
(b) Only (ii)
(c) Only (i) and (iii)
(d) Only (ii) and (iv)
(e) None of the above

12. Consider a signal X that can take two values, 1 with probability p and +1 with
probability 1 p. Let Y = X + N , where N is mean zero random noise that has
probability density function symmetric about 0. Given p and on observing Y , the
detection problem is to decide on a value for X from 1 and +1. Let X denote the
decision, then error is said to happen if X is not the true X. Consider the following
statements about the optimal detector that minimizes the probability of error.

(i) If p = 1/2, then choosing X = +1 if Y > 0 and X = 1 if Y < 0 minimizes the

probability of error.
(ii) The probability of error of the optimal detector for p = 1/3 is larger in compar-
ison to the probability of error of the optimal detector for p = 1/2.
(iii) If p = 0, then choosing X = +1 for any Y minimizes the probability of error.

Which of the above statements is/are TRUE? Choose from the following options.
(a) Only (i)
(b) Only (ii)
(c) Only (iii)
(d) Only (i) and (ii)
(e) Only (i) and (iii)
CSS 2017 SS Part Page 17 of 17
13. Let A be an n n matrix. Consider the following statements.
(i) A can have full-rank even if there exists two vectors v1 = v2 such that Av1 = Av2 .
(ii) A can be similar to the identity matrix, when A is not the identity matrix.
Recall that two matrices B and C are said to be similar if B = S 1 CS for some
matrix S.
(iii) If is an eigenvalue of A, then a vector x = 0 such that (A I)x = 0.
Which of the above statements is/are TRUE? Choose from the following options.
(a) Only (i)
(b) Only (ii)
(c) Only (iii)
(d) (i), (ii), and (iii)
(e) None of the above
14. Consider the positive integer sequence
3/2
xn = n50 e(log(n)) , n = 1, 2, 3, . . .
Which of the following statements is TRUE?
(a) For every M > 0, there exists an n such that xn > M
(b) Sequence {xn } rst increases and then decreases to 1 as n
(c) Sequence {xn } rst decreases and then increases with n 1
(d) Sequence {xn } eventually converges to zero as n
(e) None of the above
15. Suppose that f (x) is a real valued continuous function such that f (x) as
x . Further, let
 n
an = 1/j
j=1
and

n
bn = 1/j 2 .
j=1

Which of the following statements is true? (Hint: Consider the convergence properties
of the sequences {an } and {bn }.)
(a) There exists a number M and a positive integer n0 so that f (an ) M and
f (bn ) M for all n n0
(b) There exists a number M and a positive integer n0 so that f (an ) M and
f (bn ) M for all n n0
(c) There exists a number M and a positive integer n0 so that f (an ) f (bn ) M
for all n n0
(d) There does not exist any number M so that f (bn ) and f (an ) are greater than M
for all n
(e) None of the above