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

FOR ISI ADMISSION TEST EXAM PREPARATION

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

ISI Admission Test 2022 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

CS Group (Computer Science)

m
co
Note: Answer all questions from Part-A and any eight ques-
m .
co m
tions from Part-B.

m . s e
a
Part-A

s e g l
g a
l pects: Professor Plum, Mrs. Peacock, and Mr. Green. Given
CS1. Suppose a crime has been committed and there are three sus-
a
a that:
• At least one of the above three suspects is guilty.
• Not all of them are guilty.
• If Mrs. Peacock is guilty, then so is Professor Plum.

m
• If Mr. Green is innocent, then so is Professor Plum.

. co
m
Prove or disprove each of the following statements:

(i) Mr. Green is guilty. se
la
(ii) Mrs. Peacock isginnocent.
a
[3+3 = 6]

CS2. A room has four walls. In how many different ways can you
color the four walls, using colors from the set {Red, Green, Blue,
Yellow}, such that no two adjacent walls have the same color?

m
[7]

m c. o
c. o
CS3. Consider a round-robin football tournament among n ≥ 3 teams,
m
where every team plays a match with every other teameexactly
em s
a or loss.
once. For any team, each match results in a win, ldraw
las g
a match. Prove
ag In the tournament, each team loses at least one
or disprove the following statement:

There must be two teams with the same number of wins
at the end of the tournament.

[7]

m .
1

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

Part-B

CS4. Prove or disprove the following statements:

(i) L1 = {0i 1j | i, j ∈ N} is a regular language.

(ii) L2 = {0n 1n | n ∈ N} is a regular language.

(iii) For x ∈ {0, 1}∗ ,

• R(x) denotes the string obtained by reversing the
string x.
• C(x) denotes the string obtained by flipping 0 to 1 and
1 to 0 in the string x.

L3 = {x ∈ {0, 1}∗ | x = R (C (x))} is a regular language.

[2+3+5 = 10]

CS5. Let B be a binary search tree (BST) on eight nodes filled with the
following set of eight integer keys A = {10, 2, 5, 3, 20, 15, 9, 22}.
The order in which these keys were inserted to create B is not
known. However, it is known that for the given BST, (8 ×
9)/2 = 36 comparisons are needed to check the presence of all
the eight keys in A. Using this information as a clue or otherwise,
construct and depict pictorially four possible BSTs each of which
requires 36 comparisons to check the presence of all the eight
keys in A. Justify your answer. [10]

CS6. Let A[0 . . . n − 1] and B[0 . . . n − 1] be two arrays containing
n real numbers such that A[k] ≤ A[k + 1] and B[k] ≤ B[k + 1]
for all k ∈ {0, 1, . . . , n − 2}. Design an efficient algorithm to find
whether there exists any k ∈ {0, 1, . . . , n − 1} such that A[k] +
√
iB[k], where i = −1, forms a complex root of the equation
x2 + 2cx + c2 + d2 = 0 and c and d are real numbers. State and
justify the time complexity of your algorithm. [10]

2

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

m
m .co
c. o

em
em l a s
s a g

CS7. Consider an operating system consisting of a pair of processes
P0 and P1 . The structure of each process Pi is shown below.
m
m .co
c.jo= 1-i;
while(TRUE){
s em
e m l a
l a s ag
ag
flag[i] = TRUE;
turn = j;
while(TRUE){
if(flag[j] == FALSE || turn == i)
break;
}
/* CRITICAL SECTION */

m
flag[i] = FALSE;
/* REMAINDER SECTION */
. co
}
s em
l a
agthe system as follows.
Suppose we initialize

turn = 0; // Taken as a shared integer variable
flag[0] = FALSE; // Taken as a shared Boolean variable
flag[1] = FALSE; // Taken as a shared Boolean variable

m
c. o
Explain whether the above implementation satisfies mutual ex-
m
c. o em= 10]
clusion and progress.

em s
gla
[4+6

las a
ag CS8. Let G := (V, E) be a simple, connected, undirected, weighted
graph with vertex set V , |V | ≥ 4, and edge set E, |E| ≥ 4.
The edges have distinct positive weights on them. Prove that
a minimum spanning tree of G either contains the edge with
the third smallest weight or the edge with the fourth smallest
weight. [10]

m .
3

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

CS9. Consider an n × n grid as follows:

S = {(i, j) ∈ Z × Z | 1 ≤ i, j ≤ n} .

A triangle with its vertices on the grid points of S is nice if

• the area of the triangle is 3, and
• at least one of its edges is parallel to either x-axis or y-axis.

Find the number of nice triangles. [10]

CS10. A sequential circuit has two D flip-flops DA and DB with outputs
A and B, respectively. The circuit has two inputs x and y, and
one output z. The input equations for the flip-flops and the
circuit output are as follows:

DA = x y + A x

DB = x y + B x

z = Ax + Bx

(i) Draw the logic diagram of the sequential circuit.
(ii) Draw the corresponding state transition diagram.

[4+6 = 10]

CS11. Consider a computer with two-level cache system L1 and L2
along with a main memory M . The L1 cache is divided into two
parts: I-cache (Instruction cache) and D-cache (Data cache).
The probability that the processor reads a memory for an in-
struction is 1/4 and a data is 3/4. The miss ratio of D-cache is
two times of the miss ratio of the L2 cache, but the miss ratios
of I-cache and L2 cache are the same. Let the access times of
I, D, L2 and M be 4 ns, 4 ns, 40 ns and 400 ns, respectively.
Let the average memory access time be 11 ns. Compute the hit
ratio of the D-cache. [10]

4

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

m
m .co
c. o

em
em l a s
s a g

CS12. Consider a pair of relations R1 and R2 having t1 and t2 number
of tuples, respectively. Let us define the semijoin (R1 ⋉ R2 ) and
m
co
antijoin (R1 ▷ R2 ) operations on R1 and R2 in the form of the
m .
.co
following relational algebra expressions:
s e m
me l a
s g
R1 ⋉ R2 = πA(R1 ) (R1 ▷◁ R2 )

g l a a
a Recall that ▷◁ denotes the natural join operation.
R ▷ R = R − (R ⋉ R ) = R − π
1 2 1 1 (R ▷◁ R )
2 1 A(R1 ) 1 2

A dangling tuple in a relation does not have a matching attribute
value in another relation while performing a join operation. If
the ratio between the number of tuples returned by the semijoin
and antijoin is 1:2, then what is the number of dangling tuples

m
in R1 with respect to R2 ? [10]

c. o
CS13. Suppose node A generates data frames and sends to node C
through node B. Assume ethat m the link between A and B as
well as the link betweenla
s
g
B and C are full-duplex and error free.
All data frames area10 bits long and ACK frames are separate
3

frames of negligible length. The data rates of the links A → B
and B → C are 105 bps and R bps, respectively. Propagation
delays of both the links A → B and B → A are 0.02 seconds,
and that of the links B → C and C → B are both 0.004 seconds.
The sliding window protocol with window size W is used between
A and B. The stop and wait protocol is used between B and C.
o m
m c
. of
c. o e m
(i) Determine the window size W such that the utilization
s
em lathe utiliza-
the link A → B is maximum.

las a g
g
(ii) Determine the minimum value of R such that
a tion of the link A → B is maximum and the buffer at B
is not flooded. (Note: In order not to flood the buffer at
B, the time taken by B to send W frames to C must be
at most the time taken by A to send W frames to B.)
[5+5 = 10]

m .
5

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

Non-CS Group (Mathematics)

Note: Answer all questions from Part-A and any eight ques-
tions from Part-B.
Part-A
NC1. Suppose a crime has been committed and there are three sus-
pects: Professor Plum, Mrs. Peacock, and Mr. Green. Given
that:

• At least one of the above three suspects is guilty.
• Not all of them are guilty.
• If Mrs. Peacock is guilty, then so is Professor Plum.
• If Mr. Green is innocent, then so is Professor Plum.

Prove or disprove each of the following statements:

(i) Mr. Green is guilty.
(ii) Mrs. Peacock is innocent.

[3+3 = 6]

NC2. A room has four walls. In how many different ways can you
color the four walls, using colors from the set {Red, Green, Blue,
Yellow}, such that no two adjacent walls have the same color?
[7]

NC3. Consider a round-robin football tournament among n ≥ 3
teams, where every team plays a match with every other team
exactly once. For any team, each match results in a win, draw
or loss. In the tournament, each team loses at least one match.
Prove or disprove the following statement:

There must be two teams with the same number of wins
at the end of the tournament.

[7]

6

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

m
m .co
c. o

e m
em l a s
s a g

Part-B

NC4. Consider an n × n grid as follows:
m
o m .co
c
. with its vertices on the grid points of S is nice if em
S = {(i, j) ∈ Z × Z | 1 ≤ i, j ≤ n} .

Amtriangle
a s
lase ag l
ag • the area of the triangle is 3, and
• at least one of its edges is parallel to either x-axis or y-axis.

Find the number of nice triangles. [10]

NC5. (i) Let f : [0, 1] → [0, 1] be a strictly decreasing continuous
function with f (0) = 1 and f (1) = 0. Show that
� 1 � 1
f (x)dx =
o mf −1 (y)dy .
c
(ii) Let f be a differentiable. function on [−2, 2] such that
0 0

m
f (−2) = 1, f (2) = s5eand |f (x)| ≤ 1 for all x ∈ [−2, 2].
a
oflf (0).
′

Find the value g
a [6+4 = 10]

NC6. (i) Consider a simple, undirected, connected graph G =
(V, E) whose every vertex has degree at least 2. Show
that G contains a cycle.
(ii) A simple, undirected, connected graph is 2-edge connected

o m
c
if at least 2 edges need to be removed to make G discon-
m .
c. o m
e can
nected.
(a) Show an example of a tree with 11 verticessthat
s em g laby adding
gla a
be converted to a 2-edge connected graph

a an edge.
(b) Show an example of a tree with 11 vertices that can
be converted to a 2-edge connected graph by adding
five edges.

[5+(2+3) = 10]

m .
7

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

NC7. Let a0 , a1 , . . . , an be real numbers with property that
a1 a2 an
a0 + + + ··· + = 0.
2 3 n+1
Prove that the equation

a0 + a1 x + · · · + an xn = 0

has a solution in (0, 1). [10]

NC8. Find the largest positive real number δ such that, for real num-
bers x and y
√
|x − y| < δ implies | cos x − cos y| < 2.

[10]

NC9. Let f (x) be a nonconstant polynomial with real coefficients. If
there exists a complex root α of f (x) with multiplicity greater
than 1, show that the polynomial f (f (x)) also has a complex
root with multiplicity greater than 1. [10]

NC10. A particular Covid-19 vaccine produces a side effect (fever) with
probability p ∈ [0, 1]. A clinic vaccinates 500 people each day
and records the number of people having side effects on 5 ran-
domly chosen days.

(i) What is the probability that the number of people
who developed side effects on the 5 observed days are
10, 15, 0, 20, 25?
(ii) Find the value of p that maximizes the probability ob-
tained in part (i).
(iii) Based on the value of p obtained in part (ii), what is the
expected number of people who will develop side effects
on each day?

[4+4+2 = 10]

8

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

m
m .co
c. o

e m
em l a s
s a g

NC11. Let A, A1 , A2 , . . . , Am be n × n matrices with real entries such
that
m
co
m
�

o m .
A= At .

c m
m(i). Show that s e
t=1

s e g l a
l a a
m
�

ag (ii) An n×n matix B with real entries is defined as a two-block
rank(A) ≤ rank(A ). t
t=1

matrix if there exist two disjoint submatrices C and D in
B such that
• All entries of C are the same, and all entries of D are
the same.

m
• All other entries of B not in C and D are 0.

c. o
If the matrices At are two-block matrices for all t ∈

s em m ≥ rank(A)/2.
{1, . . . , m} then show that

g la
a
[3+7 = 10]

NC12. Let GL2 (Z/mZ) denote the following set of matrices
�� � �
a11 a12 �
�
� aij ∈ Z/mZ and a11 a22 − a12 a21 ∈ (Z/mZ)
∗
a21 a22
with matrix multiplication as group operation. Note that
(Z/mZ) denotes the multiplicative group of units in Z/mZ.
∗

m
m (i) Show that
� the map
� ψ : Z/mZ → GL2 (Z/mZ) given by
.co
c. o se
m
em
1 a

la
ψ(a) = is an injective group homomorphism.

s g
0 1

gla (ii) Show that there exists a 2 × 2 matrix M such that M is of
a
a order 2 in GL2 (Z/8Z) and M is of order 5 in GL2 (Z/15Z).

[3+7 = 10]

NC13. Find the perimeter of the region bounded by x2 + y 2 − 144 ≤ 0
√
and x2 + y 2 − (24 2)x + 144 ≤ 0. [10]

m .
9

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