Please read all instructions carefully before you attempt the questions

For admissions in Computer Science (CS) programme and Learning, Information

and Data Sciences (LIDS) programme (formerly called Systems Science)

1. The question paper consists of Three (3) parts:

Part A Common
Part B Computer Science (CS)
Part C Learning, Information, and Data Science (LIDS)

2. The total time allotted is three (3) hours. There are no separate limits on the time allowed
for each part. Each part consists of fifteen (15) questions.

3. Common: Part A must be attempted by all candidates.

4. To be considered for entrance into Computer Science, Part B: CS must be attempted. If

you do not wish to be considered for entrance into Computer Science, you can skip all
questions in Part B: CS.

5. To be considered for entrance into Learning, Information and Data Sciences, Part C:
LIDS must be attempted. If you do not wish to be considered for entrance into Learning,
Information and Data Sciences, you can skip all questions in Part C: LIDS.

6. Candidates may attempt both Part B: CS and Part C: LIDS; however, no extra time will
be given. Candidates who attempt both Part B: CS and Part C: LIDS will be considered
for entrance into both Computer Science and Learning, Information and Data Sciences.

7. As in a paper exam, sections and questions can be attempted in any order and revisited
as often as desired.

8. All questions carry equal marks. A correct answer will give you +4 marks, a wrong
answer will give you -1 marks (i.e., one (1) mark will be deducted for a wrong answer),
and a question not answered will give you 0 marks.

9. For entrance into Learning, Information and Data Sciences, marks in Part A: Common
and Part C: LIDS will be considered and marks in Part B: CS will be ignored.

10. For entrance into Computer Science, marks in Part A: Common and Part B: CS will be
considered and marks in Part C: LIDS will be ignored.

11. Rough work may be done on the rough sheets provided.

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

13. Do NOT ask for clarifications regarding the questions from the invigilators. 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.
Please read all instructions carefully before you attempt the questions.

Syllabus
Computer Science
1. Discrete Mathematics: Sets and Relations, Combinatorics (Counting) and Elementary
Probability Theory, Graph Theory, Propositional and Predicate Logic.
2. Formal Languages, Automata Theory and Computability.
3. Data Structures and Algorithms: Arrays, Lists and Trees, Sorting and Searching,
Graph algorithms, Complexity of problems and NP-completeness.
4. Fundamentals of Programming Languages and Compilers: Control structures,
Parameter passing mechanisms, Recursion, Parsing and type checking, Memory
management.
5. Operating Systems and Concurrency
6. Switching Theory and Digital Circuits
7. Theory of Databases

Learning, Information, and Data Science (LIDS)

(formerly called Systems Sciences)
1. Engineering Mathematics: Probability, Linear Algebra, Basic Optimization, Basic Analysis,
Calculus.
2. Electrical and Computer Sciences: Signals and Systems, Digital Signal Processing.
 Part B
Computer Science Questions

1. Let T be a rooted binary tree whose vertices are labelled with symbols a, b, c, d, e, f, g, h, i, j, k.
Suppose the in-order (visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit
right subtree, visit root) traversals of T produce the following sequences.

in-order: a, b, c, d, e, f, g, h, i, j, k

post-order: a, c, b, e, f, h, j, k, i, g, d

How many leaves does the tree have?

(a) THREE.

(b) FOUR.

(c) FIVE.

(d) SIX.

(e) Cannot be determined uniquely from the given information.

2. Consider the following code.

def brian(n):
count = 0

while ( n != 0 )
n = n & ( n-1 )
count = count + 1

return count

Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and computes
their bit wise AND. For example, 22 & 15 gives 6, because the binary (say 8-bit) representation of 22 is
00010110 and the binary representation of 15 is 00001111, and the bit-wise AND of these binary strings is
00000110, which is the binary representation of 6.
What does the function brian return?

(a) The highest power of 2 dividing n, but zero if n is zero.

(b) The number obtained by complementing the binary representation of n.

(c) The number of ones in the binary representation of n.

(d) The code might go into an infinite loop for some n.

(e) The result depends on the number of bits used to store unsigned integers.

8
3. Consider the following directed graph.

a b c

d e

Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the
vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is T , the number
of back edges is B and the number of cross edges is C. Then

(a) B = 1, C = 1, and T = 4.

(b) B = 0, C = 2, and T = 4.

(c) B = 2, C = 1, and T = 3.

(d) B = 1, C = 2, and T = 3.

(e) B = 2, C = 2, and T = 1.

4. Consider the following undirected graph with some edge costs missing.

? ?
a b c
3
3
? ? 4
-2

d e f
5 ?

Suppose the wavy edges form a Minimum Cost Spanning Tree for G. Then, which of the following inequal-
ities NEED NOT hold?

(a) cost(a, b) ≥ 6.

(b) cost(b, e) ≥ 5.

(c) cost(e, f ) ≥ 5.

(d) cost(a, d) ≥ 4.

(e) cost(b, c) ≥ 4.

9
 Learning, Information, and Data Science
(Formerly Systems Science)
1. Let X1 and X2 be two continuous random variables, and let Y = max{X1 , X2 }
and Z = arg max{X1 , X2 }. Which of the following is true ?
(a) P (Z = i) = P (Z = i|Y )
(b) P (Z = i) = P (Z = i|Y, X1 )
(c) P (Z = i) = P (Z = i|Y, X1 , X2 )
(d) P (Z = i) = 12 , i = 1, 2
(e) (a) and (d)
Ans: (e)

2. Let there be 7 teams in a tournament. Each team plays one game with every
other team. Two points are awarded for a win, one point for a tie, and no
points for a loss. At the end of all matches, the top 3 teams qualify for the next
round. What is the minimum number of points for a team to quality for the
next round.
(a) 5
(b) 6
(c) 4
(d) 7
(e) None of the above
Ans: (c)

3. For a m ⇥ m matrix A if A2 = 0, then which of the following is true.

(a) det(A) = 0
(b) det(I + A) = 1
(c) Trace(A) = 0
(d) (a) (b) and (c)
(e) Only (a) and (c).
Ans: (d)

4. For a m ⇥ n, m 6= n real valued matrix A, which of the following is true.

(a) rank(AAT ) = rank(AT A)
(b) det(AT A) = det(AAT )
(c) Trace(AAT ) = Trace(AT A)
(d) (a) and (c)
(e) None of the above.
Ans: (d)
5. Consider a 4 ⇥ 4 square grid S, where points are indexed as (x, y), x, y 2
{0, 1, 2, 3}. Suppose you start at point (0, 0) and the only move allowed at any
time is either up or right on the grid. For example, if you are at point (x, y)
then either you can go to (x + 1, y) 2 S or (x, y + 1) 2 S and always remain
within S. Let the number of distinct paths to reach point (2, 2) starting from
(0, 0) be z. Two paths are distinct if at least they di↵er in one move. How
many distinct paths are there to reach point (3, 3) starting from (0, 0) ?

(a) 2z + 6
(b) 2z + 8
(c) 3z + 6
(d) 3z + 8
(e) None of the above

Ans: (b)
R1
6. If for a real-valued function f (x) 0, 8 x, let 0
f (x)dx = 1. Then which of
the following is possible
R1
(a) 0 xf (x)dx = 1
R 1 (x)
(b) 0 f1+x dx = 1
R1
(c) 0 (log x)f (x)dx = 1
R 1 f (x)
(d) 0 1+log x
dx = 1
(e) None of the above

Ans: (a)

7. Consider a random variable X that takes values {1, . . . , 6} with equal proba-
bility, and a random variable Y that takes values {1, 2} with P (Y = 1) = p. If
Z = (X mod Y ) + 1, Then which of the following is true ?
1
(a) P (Z = 1) = 2
for some value of p.
1
(b) P (Z = 1) = 2
for no value of p.
1
(c) P (Z = 1) = 2
for p = 1/2.
(d) P (Z = 1) = p(1 p).
(e) (a) and (c)

Ans: (a)