TIFR PHD CS & SS 2017
Question 1 
A suitcase weighs one kilogram plus half of its weight. How much does the suitcase weigh?
1.333... kilograms  
1.5 kilograms  
1.666... kilograms  
2 kilograms  
cannot be determined from the given data 
Question 2 
(a, b)≤ ǁbǁ  
(a, b)≤ ǁaǁ  
(a, b) = ǁaǁǁbǁ  
(a, b)≥ ǁbǁ  
(a, b)≥ ǁaǁ 
Question 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?
t/√2  
√2t  
2t  
h/t  
h/2t 
Question 4 
Which of the following functions asymptotically grows the fastest as n goes to inﬁnity?
(log log n)!  
(log log n)^{log n}  
(log log n)^{log log log n}  
(log n)^{log log n}  
2^{√(log log n)} 
Question 5 
How many distinct ways are there to split 50 identical coins among three people so that each person gets at least 5 coins?
3^{35}  
3^{50} − 2^{50}  
(35 2)  
(50 15)*3^{35}  
(37 2) 
Question 6 
How many distinct words can be formed by permuting the letters of the word ABRACADABRA ?
11! / (5! 2! 2!)  
11! / (5! 4!)  
11! 5! 2! 2!  
11!  
11! 5! 4! 
Question 7 
Consider the sequence S0, S1, S2,... deﬁned as follows: S0 = 0, S1 = 1, and Sn = 2S_{n−1} + S_{n−2} for n ≥ 2. Which of the following statements is FALSE?
for every n ≥ 1, S_{2n} is even  
for every n ≥ 1, S_{2n+1} is odd  
for every n ≥ 1, S_{3n} is a multiple of 3  
for every n ≥ 1, S_{4n} is a multiple of 6  
none of the above 
Question 8 
In a tutorial on geometrical constructions, the teacher asks a student to construct a rightangled 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 oﬀers various choices for the value of h. For which value of h can such a triangle NOT exist?
3.90 inches  
2√2 inches  
2√3 inches  
4.1 inches  
none of the above 
Question 9 
3α  
α^{2}  
6α(1 − α)  
3α^{2(1 − α)}  
6α(1 − α)+ α^{2} 
Question 10 
For a set A, deﬁne (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?
f cannot be onetoone (injective)  
f cannot be onto (surjective)  
f is both onetoone and onto (bijective)  
there is no such f possible  
if such a function f exists, then A is inﬁnite 
Question 11 
Let fog denote function composition such that (fog)(x) = f (g(x)). Let f :A > B such that for all g : B > A and h : B>A we have fog = foh ==> g=h. Which of the following must be TRUE?
f is onto (surjective)  
f is onetoone (injective)  
f is both onetoone and onto (bijective)  
the range of f is ﬁnite  
the domain of f is ﬁnite 
Question 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 ?
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 ?
the new A is the transpose of the old A  
all elements above the diagonal have their values increased by 10 and all values below have their values decreased by 10  
all elements above the diagonal have their values decreased by 10 and all values below have their values increased by 10  
the new matrix A is symmetric, that is, A[i][j] = A[j][i] for all 1 ≤ i, j ≤ n  
A remains unchanged 
Question 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?
For n = 3, Bharat has a winning strategy. For n = 4, Aditi has a winning strategy  
For n = 7, Bharat has a winning strategy. For n = 8, Aditi has a winning strategy  
For both n = 3 and n = 4, Aditi has a winning strategy  
For both n = 7 and n = 8, Bharat has a winning strategy  
Bharat never has a winning strategy 
Question 17 
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.
(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.
Only (i) and (ii)  
Only (ii) and (iv)  
Only (ii), (iii), and (iv)  
Only (i), (ii), and (iv)  
All of them 
Question 18 
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 ?
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 ?
((((  
)))((((  
)))  
(((()))  
()() 
Question 19 
Let L be the language over the alphabet {1, 2, 3, (, )} generated by the following grammar (with start symbol S, and nonterminals {A, B, C}):
S → AB C
A → (
B → 1B  2B  3B
B → 1  2  3
C → )
Then, which of the following is TRUE?
L is ﬁnite  
L is not recursively enumerable  
L is regular  
L contains only strings of even length  
L is contextfree but not regular 
Question 20 
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.
(i) only  
(iii) only  
(ii) and (iii) only  
(i), (ii), and (iii)  
None of the above

Question 21 
Consider First Order Logic (FOL) with equality and suitable function and relation symbols. Which one of the following is FALSE?
Partial orders cannot be axiomatized in FOL  
FOL has a complete proof system  
Natural numbers cannot be axiomatized in FOL  
Real numbers cannot be axiomatized in FOL  
Rational numbers cannot be axiomatized in FOL 
Question 22 
An array of n distinct elements is said to be unsorted if for every index i such that 2 <=i <=n1, either A[i] > max{A[i1], A[i + 1] , or A[i] < min A[i1], A[i + 1] . What is the timecomplexity of the fastest algorithm that takes as input a sorted array A with n distinct elements, and unsorts A?
O(n log n) but not O(n)  
O(n) but not O(√n)  
O(√n) but not O(log n)  
O(log n) but not O(1)  
O(1) 
Question 23 
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 diﬀer in exactly one bit (the ﬁrst and last string must also diﬀer 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?
the number of possible Gray codes is even  
the number of possible Gray codes is odd  
in any Gray code, if two strings are separated by k other strings in the ordering, then they must diﬀer in exactly k +1 bits  
in any Gray code, if two strings are separated by k other strings in the ordering, then they must diﬀer in exactly k bits  
none of the above 
Question 24 
Which of the following regular expressions correctly accepts the set of all 0/1strings with an even (possibly zero) number of 1s?
(10^{∗}10^{∗})^{∗}  
(10^{∗}10^{∗}1)^{∗}  
0^{∗}1(10^{∗}1)^{∗}10^{∗}  
0^{∗}1(0^{∗}10^{∗}10^{∗})^{∗}10^{∗}  
(0^{∗}10^{∗}1)^{∗}0^{∗} 
Question 25 
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 statements:
(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.
only (i)  
only (i) and (ii)  
only (i) and (iii)  
only (ii) and (iii)  
(i), (ii), and (iii) 
Question 26 
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)))?
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)))?
all ﬂies eat bats  
every ﬂy is eaten by some bat  
bats eat only ﬂies  
every bat eats ﬂies  
only bats eat ﬂies 
Question 27 
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?
n  
n(n1)/2  
n!  
2^{n}  
2^{m} ,where m=n(n1)/2 
Question 28 
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?
the line graph for a complete graph is complete  
the line graph for a connected graph is connected  
the line graph for a bipartite graph is bipartite  
the maximum degree of any vertex in the line graph is at most the maximum degree in the original graph  
each vertex in the line graph has degree one or two 
Question 29 
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 preﬁxclosed if for every xεL, every preﬁx of x is also in L. Which of the following is FALSE?
S → AC  SS  AB C → SB
A → [
B → ]
A language L is called preﬁxclosed if for every xεL, every preﬁx of x is also in L. Which of the following is FALSE?
L(G) is context free  
L(G) is inﬁnite  
L(G) can be recognized by a deterministic push down automaton  
L(G) is preﬁxclosed  
L(G) is recursive. 
Question 30 
A multivariate polynomial in n variables with integer coeﬃcients 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 2x^{3}_{1}x_{1}x_{1}+2 has the binary root (x_{1} = 1, x_{1} = 0). Then determining whether a multivariate polynomial, given as the sum of monomials, has a binary root:
is trivial: every polynomial has a binary root  
can be done in polynomial time  
is NPhard, but not in NP  
is in NP, but not in P and not NPhard  
is both in NP and NPhard 
Question 31 
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?
y(t) = 2x(t − 2) + x(2t − 1) + 1.
Which of the following describes the system?
linear, timeinvariant, causal  
linear, timeinvariant, noncausal  
nonlinear, timeinvariant, causal  
nonlinear, timeinvariant, noncausal  
nonlinear, timevariant 
Question 32 
Suppose a 1μH inductor and a 1Ω resistor are connected in series to a 1V battery. What happens to the current in the circuit?
The current starts at 0A, and gradually rises to 1A  
The current rises instantaneously to 1A and stays there after that  
The current rises instantaneously to 1A and then falls to 0A  
The current oscillates over time between 0A and 1A  
The current oscillates over time between 1A and 1A 
Question 33 
23 W  
11.5W  
8.1317W  
2.875W  
None of the above 
Question 34 
a  
b  
c  
d  
e 
Question 36 
(i) and (ii) only  
(ii) and (iii) only  
(iii) and (iv) only  
(iv) and (i) only  
None of the above 
Question 41 
Consider a unit length interval [0, 1] and choose a point X on it with uniform distribution. Let L1 = X and L2 = 1X be the length of the two subintervals 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.
(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.
Only (i)  
Only (ii)  
Only (i) and (iii)  
Only (ii) and (iv)  
None of the above 
Question 42 
Only (i)  
Only (ii)  
Only (iii)  
Only (i) and (ii)  
Only (i) and (iii) 
Question 43 
Only (i)  
Only (ii)  
Only (iii)  
(i), (ii), and (iii)  
None of the above 
There are 45 questions to complete.