ISI Admission Test 2024 Question Paper M.Tech(CS), M.Tech(CrS) PCB

FOR ISI ADMISSION TEST EXAM PREPARATION

ISI Admission Test
2024
Question Paper ·
M.Tech(CS),
M.Tech(CrS) PCB
EXAM YEAR TYPE

ISI Admission Test 2024 Question Paper
SUBJECT

M.Tech(CS), M.Tech(CrS) PCB

Notes · Sample Papers · Previous Year Papers · Mock Tests

m
m .co
c. o

e m
em l a s
s a g

Part-A

m
The following notation is used throughout the question paper.

o m .co
c m
• C denotes the set of complex numbers.

• Rm
. s e
s e denotes the set of real numbers.
g l a
g a
l • |S| denotes the cardinality of a set S. a
a

m
c. o
1. Suppose there are three types of people in the world.

m person always speaks the truth.
• A person is “honest” ifethe
s
laif the person always lies.
a g
• A person is a “liar”
• A person is “normal” if the person sometimes speaks the
truth and sometimes lies.

In a city, a crime has been committed. A, B and C are the three
suspects. It is known from reliable sources that among A, B and
C, only one person is honest and that person has committed
m
m .co
the crime. The following is a conversation between the three

c. o se
m
suspects.

s em g la
la
A: I did not commit the crime.

g a
a
B: Yes, A did not commit the crime.
C: B is not normal.

Based on the above, deduce with appropriate justifications who
among A, B and C has committed the crime. [5]

m .
co
1

. e m
e m la s
l a s a g
ag For more Question Papers, Sample Papers, Notes & Syllabus visit Page 1 of 10

2. Recall that C denotes the set of complex numbers. A set S ✓ C
is called engulfing if either |S| = 1 or S satisfies the following:

• |S 2 | = |S|/2
• S 2 is also engulfing,

where
S 2 = {x2 | x 2 S}.

(a) Find an engulfing set of cardinality 4.
(b) Find an engulfing set of cardinality 6.

[4 + 4]

3. A minimum vertex cover of a graph is the smallest set of vertices
that includes at least one endpoint of every edge of the graph.
An algorithm claims to compute a minimum vertex cover of a
graph by repeatedly choosing a vertex of maximum degree and
then removing it from the graph. The algorithm stops as soon
as a vertex cover is obtained. Construct a graph for which this
algorithm will fail to return a minimum vertex cover. [7]

2

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 2 of 10

m
m .co
c. o

em
em l a s
s ag

Part-B

m
CS Group

m .co
co m
1. Consider two binary search trees (BSTs) named T1 and T2 ,

m . s e
e a
rooted at Root1 and Root2 , respectively. Both T1 and T2 are

a s g l
l nodes, respectively. Every node of T and T has three fields: a
AVL (Adelson-Velsky-Landis) trees with M (> 0) and N (> 0)

g
a value, left-link and right-link. T and T have no common value.
1
1

2
2

Define merging of a BST T2 with a BST T1 as a process that
combines the two BSTs to form a single BST by attaching the
root of T2 to a left- or right-link of T1 that is free. Thus, the
merge operation excludes one by one insertion of the nodes of

m
one BST into the other.

c. o
(with 7 integer values),m
(a) Create two AVL trees TA (with 6 integer values) and TB

with T as per the a
e
s definition. Note that T and T
such that T cannot be merged

l
B

g common value.
must not have aany
A above A B

(b) Design an algorithm that takes two AVL trees T1 and T2
as input and merges T2 with T1 , if possible, otherwise re-
ports an error. Explain your algorithm. Deduce the time
complexity of your algorithm, and also find the maximum
possible height of the merged tree in terms of the heights

o m
c
of T1 and T2 .
m .
c. o s em
em
[4 + (4 + 2)]

las agla
ag 2. Consider an array X of n distinct elements such that

X[0] < X[1] < · · · < X[i 1] < X[i] > X[i+1] > · · · > X[n 1].

Suggest a linear time algorithm to sort the elements in X.
[10]

m .
co
3

. e m
e m la s
l a s a g
ag For more Question Papers, Sample Papers, Notes & Syllabus visit Page 3 of 10

3. Let A be an n ⇥ n matrix with entries aij = ±1 for all 1  i, j 
n. Prove that 2n 1 divides the determinant of A. [10]

4. For a graph, a proper vertex colouring assigns a colour to each
vertex such that no two adjacent vertices have the same colour.
A vertex colouring is optimal if it is proper and uses the minimum
number of colours.
Consider a graph G with an optimal vertex colouring. Show that
in G, for each colour, there exists a vertex of that colour which
has vertices of every other colour adjacent to it. [10]

5. Prime numbers p and q are said to be twin primes if q = p + 2.
Consider the following language

L := {1n | there exist twin primes p and q with q p n} .

Prove that L is regular irrespective of whether the number of
twin primes is finite or infinite. [10]

6. For the gate T shown in Fig. A, the truth-table of the function
f(A, B, C) is given in Fig. B.

If you are allowed to set any of the inputs to 1, show that the gate
T is functionally complete (i.e., any 2-input Boolean function can
be implemented with it). [10]

4

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 4 of 10

m
m .co
c. o

e m
em l a s
s a g

7. You are given a processor having a single-level cache hierarchy

m
with only an L1 cache that has a 95% hit rate. You have to

m .co
re-design the cache hierarchy without increasing the E↵ective

c o
. with a lower hit rate of 0.9, and an L2 cache.
Memory Access Time (EMAT), using a smaller and cheaper L1
e m
m a s
se l
cache

la (a) Show that the access time of the L2 cache should be no ag
ag greater than 1/2 of the main memory.
(b) Determine the minimum hit rate of the L2 cache to achieve
the required EMAT?
(c) If the actual access time of the L2 cache is 1/10 of the main
memory access time, then determine the minimum hit rate

m
co
of the L2 cache to achieve the required EMAT?

.
s em
[10]

l a
ag framing method where both the start
8. Consider a bit stuffing
and the end of a frame are indicated by the flag 01k 0 where 1k
denotes k consecutive ones.
Recall that for a flag 01k 0, stuffing a 0 bit is required whenever
01k 1 appears in the original data stream. On the other hand, if
0 is preceded by 01k 1 in the transmitted bit stream, destuffing

o m
c
the 0 bit is required at the receiver.

m .
c. o s em k 1
(a) Is it necessary to stu↵ a 0 bit in 01 0? Justify your

s em answer.
g l a
gla (b) In the worst case, how many bits need toabe stu↵ed for a
a data packet of length L?

[5 + 5]

m .
co
5

. e m
e m la s
l a s a g
ag For more Question Papers, Sample Papers, Notes & Syllabus visit Page 5 of 10

9. Consider the following information about a magnetic hard disk,
with cylinders numbered 0 (innermost) to 511 (outermost):

• at time t = 0 ms, the disk head is at cylinder 120, moving
outwards towards cylinder 511;

• the disk arm takes 1 ms to seek from cylinder i to cylinder
i + 1 or cylinder i 1;

• the time taken to read sectors may be neglected.

The following I/O requests arrive at the disk controller.

Request no. Arrival time (ms) Cylinder no.

r1 1 480
r2 10 240
r3 15 360
r4 20 100
r5 25 140
r6 30 185

(a) In what order will the six requests be serviced if the con-
troller uses the following scheduling algorithms?

i. look
ii. preemptive shortest seek time first (sstf)

The standard definitions of these algorithms are given to-
wards the end of this question.

(b) Let TLOOK (S) and TSSTF (S) denote the total time taken
to service a given sequence S of requests using look and
sstf, respectively. Two requests arrive at time t = 0 for
cylinder nos. x1 and x2 . Show that, for any x1 , x2 2 [0, 511],
TLOOK (S) TSSTF (S) for S = x1 , x2 .

6

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 6 of 10

m
m .co
c. o

e m
em l a s
s a g

In look, the disk head alternatively moves in the outward and

m
inward directions servicing any currently pending requests as it

m .co
reaches each cylinder. While travelling in a particular direction,

c o
that .direction, before reversing direction.
the arm goes only as far as the last request currently pending in
em
m a s
seIn preemptive shortest seek time first (sstf), the disc
la controller runs the scheduling algorithm whenever a new I/O ag l
g
a request arrives. [(1 + 4) + 5]

10. A directed graph can be represented by its edge-list and stored in
a database table with attributes (source, target). For example,
the following table stores the edge-list of the graph shown in the

m
c. o
picture.

s em source target
g l a
a B A
B C
C D
D B
D E
E F

m
c. o
F G

m
c. o em
G D

We define a triangle to be a directed cycle of length 3.as
s em g l E, F, G) is a
la
Note that

g a
in the graph G, (B, C, D) is a triangle, whereas (D,
a cycle but not a triangle.
Write a relational algebra expression or an SQL query to output
all the triangles in a directed graph G that is represented by
its edge-list and stored in a table G edges(source, target).
Briefly justify that your answer is correct. [10]

m .
co
7

. e m
e m la s
l a s a g
ag For more Question Papers, Sample Papers, Notes & Syllabus visit Page 7 of 10

Non-CS Group

1. Let A be an n ⇥ n matrix with entries aij = ±1 for all 1  i, j 
n. Prove that 2n 1 divides the determinant of A. [10]

2. For a graph, a proper vertex colouring assigns a colour to each
vertex such that no two adjacent vertices have the same colour.
A vertex colouring is optimal if it is proper and uses the minimum
number of colours.
Consider a graph G with an optimal vertex colouring. Show that
in G, for each colour, there exists a vertex of that colour which
has vertices of every other colour adjacent to it. [10]

3. A pair of prime numbers p and q are said to be twins if q = p+2.
Consider the following language

L := {1n | there exists twin primes p and q with q p n} .

Prove that L is regular irrespective of whether there are infinite
or finite number of twin primes. [10]

4. W1 and W2 are non-zero, non-trivial, distinct subspaces of a
vector space V (of dimension n) over C.

(a) Prove that there exists a non-zero element ↵ 2 V which is
in neither of the subspaces W1 and W2 .
(b) Prove that there is a basis {b1 , . . . , bn } of V , such that
bi 2
/ W1 [ W2 for i = 1, . . . , n. [4 + 6]

5. A person A rolls a fair die until the outcome is 6. After that,
B rolls the die as many times as A had rolled it. Compute the
probability that B will get exactly one 6. [10]

8

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 8 of 10

m
m .co
c. o

e m
em l a s
s ag

6. Find all values of a 2 C for which the equation

m
co
x4 + ax2 + a2 x 1=0

m .
.co em
has all roots of the same absolute value. [10]

e m l a s
7.s An oil-exploration company is considering 10 possible drilling
a g
g l sites S , S , . . . , S . The drilling costs associated with these a
a 1 2 10

sites are C1 , C2 , . . . , C10 respectively. Due to land topography,
there are some additional constraints as follows.

• Drilling at sites S1 and S7 would prevent the company from
drilling at site S8 .

m
• Drilling at site S3 or S4 prevents the company from drilling at

c o
, S. , S , S , only two sites may be
site S5 .
• Out of the drilling sites S m
s e
a
5 6 7 8

drilled.
g l
a
Your job is to help the company select 5 out of 10 sites for drilling
such that the above constraints are satisfied and the total drilling
cost is minimised. Formulate the problem as an Integer Linear
Program (ILP). [10]

m
8. Consider the sequence an , defined as

c. o
✓ ◆
m
c. o
1 4

m
elimit.
an+1 = an + .

s
2 an

s em a exists. Compute the value of a
g l [6 + 4]
la
Prove that limn!1 the

a
n

ag
9. Consider the set of points {(x, y, z) | x, y, z 2 {0, 1, . . . , n}}.
Determine how many of these points lie on the Euclidean plane
that contains the points (n, 0, 0), (0, n, 0) and (0, 0, n). [10]

m .
co
9

. e m
e m la s
l a s a g
ag For more Question Papers, Sample Papers, Notes & Syllabus visit Page 9 of 10

10. Given a permutation of {1, 2, . . . , n}, we define the symmetric
binary matrix A as follows:
(
1 if (i j)( (i) (j)) < 0,
Aij =
0 otherwise.

Is every binary symmetric n ⇥ n matrix of the form A for some
permutation of {1, 2, . . . , n}? Justify your answer. [10]

10

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 10 of 10