univ.tifr.res.in GS Computer & Systems Sciences Question Paper 2017 : Tata Institute of Fundamental Research

Name of the Centre :Tata Institute of Fundamental Research
Document type : Previous Question Papers
Name Of The Exam : GS Graduate School Admissions Exam
Name Of The Subject : Computer & Systems Sciences

Website : http://univ.tifr.res.in/admissions/
Download Previous Question Papers :
GS 2017 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2017CSS.pdf
GS 2016 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2016CSS.pdf
GS 2015 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2015CSS.pdf
GS 2014 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2014CSS.pdf
GS 2013 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2013CSS.pdf
GS 2012 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2012CSS.pdf
GS 2011 Computer & Sciences : https://www.pdfquestion.in/uploads/13091-GS2011CSS.pdf

GS Computer & Systems Sciences Question Paper 2017 :

Duration : Three hours (3 hours)

Related : Tata Institute of Fundamental Research GS Graduate School Admissions Exam Question Paper 2010 : www.pdfquestion.in/5163.html

Please read all instructions carefully before you attempt the questions :
1. Please fill-in details about name, reference code etc. on the answer sheet. The Answer Sheet is machine readable. Use only Black/Blue ball point pen to fill-in the answer sheet.

2. Indicate your ANSWER ON THE ANSWER SHEET by blackening the appropriate circle for each question. Do not mark more than one circle for any question : this will be treated as a wrong answer.

3. This question paper consists of three (3) parts. Part-A contains fifteen (15) questions and must be attempted by all candidates. Part-B & Part-C contain fifteen (15) questions each, directed towards candidates for (B) Computer Science and (C) Systems Science (including Communications and Applied Probability), respectively. STUDENTS MAY Attempt Either Part-B Or Part-C. In case, a student attempts both Parts B & C (no extra time will be given) and qualifies for interview in both B & C, he/she will have opportunity to be interviewed in both areas. All questions carry equal marks. A correct answer for a question will give you +4 marks, a wrong answer will give you -1 mark, and a question not answered will not get you any marks.

4. We advise you to first mark the correct answers in the QUESTION SHEET and then to TRANSFER these to the ANSWER SHEET only when you are sure of your choice.
5. Rough work may be done on blank pages of the question paper. If needed, you may ask for extra rough sheets from an Invigilator.

6. Use of calculators, mobile phones, laptops, tablets (or other electronic devices, including those connecting to the internet) is NOT permitted.

7. Do NOT ask for clarifications from the invigilators regarding the questions. They have been instructed not to respond to any such inquiries from candidates. In case a correction/clarification is deemed necessary, the invigilator(s) will announce it publicly.

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. 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/V2
(b) v/2t
(c) 2t
(d) h/t
(e) h/2t

4. Which of the following functions asymptotically grows the fastest as n goes to infinity?
(a) (log log n)!
(b) (log log n)log n
(c) (log log n)log log log n
(d) (log n)log log n
(e) 2 v log log n

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
(d) 50/15· 335
(e) 37 / 2

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

7. Consider the sequence S0, S1, S2, . . . defined as follows: S0 = 0, S1 = 1, and Sn = 2Sn-1 + Sn-2 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

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 offers various choices for the value of h. For which value of h can such a triangle NOT exist?
(a) 3.90 inches
(b) 2v 2 inches
(c) 2 v 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(a) be the probability that the output is 1 when each input is set to 1 independently with probability a. What is p(a) = d dap(a)?
(a) 3a
(b) a2
(c) 6a(1 – a)
(d) 3a2(1 – a)
(e) 6a(1 – a) + a2

10. For a set A, define 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 infinite

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.
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

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.
(a) ((((
(b) )))((((
(c) )))
(d) (((()))
(e) ()()

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 -> ABC
A -> ( B -> 1B | 2B | 3B
B -> 1 | 2 | 3
C -> ) Then, which of the following is TRUE?
(a) L is finite
(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

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. 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 differ in exactly one bit (the first and last string must also differ 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 differ 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 differ in exactly k bits
(e) none of the above

8. 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*

9. 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 colouringusing 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)

10. Given that
B(x) means “x is a bat”,
F(x) means “x is a fly”, and
E(x, y) means “x eats y”,
what is the best English translation of
(a) all flies eat bats
(b) every fly is eaten by some bat
(c) bats eat only flies
(d) every bat eats flies
(e) only bats eat flies