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

FOR ISI ADMISSION TEST EXAM PREPARATION

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

ISI Admission Test 2026 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
PCB

Group A: CS Group

m
co
Answer Question C1 and any 5 questions from C2 to C11.
m .
.co s em
m
C1. Given an array A = (a0 , a1 , . . . , an→1 ) of integers, your task is to

s e g l a
a
determine the maximum possible sum

g l maxsum(A) = max a + a a
a 0↑s↑t↑n→1
s s+1 + · · · + at→1 + at .

For example, if A = (→2, 1, →3, 4, →1, 2, 1, →5, 4), then
maxsum(A) = 6, that is attained for s = 3 and t = 6.

(a) Write a function that computes maxsum(A) given an
array A, as a pseudocode or in a programming language of

o m
c
your choice. Note that you will be awarded 6 marks for

m. will be given based on
e
writing a correct code and 6 marks

l a s
the e!ciency of your program.
(b) Argue why your code
ag is correct, and determine the
worst-case computational complexity of your function
with respect to the length of the array.

[(6 + 6) + (4 + 4) = 20]

m
C2. (a) Let bn bn→1 · · · b1 be the decimal representation of an n digit

m m by stripping o! the unit’s digit b . Then, show that m .
number m. Let bn bn→1 · · · b2 be the integer a obtained from
co
c. o is divisible by 7 if and only if a → 2b is divisible by 7.se
m
em
1

s g l a
la
1

g
(b) Prove that: a
a !
1001
"
1002
!
2023
"
2024 2025
! " ! " ! "
1+ + + ··· + + = .
1 2 1023 1024 1024

[10 + 6 = 16]

m .
—: Page 1 of 12 :—

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

C3. Suppose X = (x1 , x2 , . . . , xn ) is an array of numbers (not
necessarily integers) sorted in the ascending order, and
Y = (y1 , y2 , . . . , yn ) is the array constructed as yi = f (xi ) for
i = 1, 2, . . . , n, where

f (x) = (x + 1)(x → 1)(x → 3).

(a) Describe an algorithm that sorts Y using O(n)
comparisons.
(b) Provide justification for the correctness and the number of
comparisons used by your algorithm.

[10 + 6 = 16]

C4. Let R be the root of a balanced binary search tree having n
nodes, where each node contains an integer, a pointer to its left
child and a pointer to its right child. Note that insertion and
deletion of nodes in such a tree can be done in O(log n) time in
the worst case.

(a) Describe a procedure previous(R, x) that, given the root R
and any integer x, outputs the node containing the largest
integer smaller than x (or, reports if no such node exists).
The worst case time complexity of the procedure should be
O(log n). Provide a justification for the complexity of your
procedure.
(b) Describe a procedure findLargest(R, k) that, given R and an
integer k ↑ n, outputs the k-th largest integer present in
the tree in O(log n) time. For this purpose, you may store
some extra information in each of the nodes, but ensure
that the insertion and deletion of nodes in the tree can still
be done in O(log n) time in the worst case.

[8 + 8 = 16]

—: Page 2 of 12 :—

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

m
m .co
c. o

e m
em l a s
s a g
PCB

C5. For a graph G = (V, E) and a subset X ↓ V of the vertices,
the induced subgraph G[X] is defined as G[X] = (X, E ↓ ), where
m
co
E ↓ = {uv ↔ E | u, v ↔ X}.

o m m .
c
.vertices and T = (V, F ) is a spanning tree of G. Let
Suppose G = (V, E) is a connected undirected graph on two
s e
e m l a
Sa↗s V be a non-empty proper subset of the vertices and define
or more

l ag
agAfollowing:
= {uv ↔ E | u ↔ S, v ↔ V \ S}. Prove or disprove each of the

(a) A ↘ F ≃= ⊋.
(b) If G[S] has s connected components and G[V \ S] has t
connected components, then A↘F contains at least s+t→1
edges.
m
. co
(c) If A ↓ F , then either T [S] or T [V \ S] is disconnected.

em
las
[4 + 8 + 4 = 16]

a g
C6. For an attribute set A with a set of underlying functional
dependencies, the closure A+ is defined as the set of attributes
that can be derived from A. Given a relation R with attribute
sets X, Y, Z, prove or disprove each the following statements.

(a) (X ⇐ Y )+ ↘ (X ⇐ Z)+ = X + ⇐ (Y ↘ Z)+ .
(b) (X ↘ Y )+ ⇐ (X ↘ Z)+ = X + ↘ (Y ⇐ Z)+ .
o m
m .c
. co [8 + 8 =
s e m
16]

s em l a
gof bits as
a
C7. Using JK flip-flops and a minimal number of combinatorial logic
l a
ag
gates, design a sequential circuit that takes a stream
input and outputs 1 whenever three consecutive 0’s appear in
the input stream, and outputs 0 otherwise. Show the detailed
steps of your design with suitable justifications.
[16]

m .
—: Page 3 of 12 :—

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

C8. (a) Consider the following piece of a program for a hypothetical
processor having two user registers R1 and R2.

Instruction Underlying Instruction Size
Operation (in words)
MOVE R2, 1000; R2 = Mem[1000] 2
ADD R1, R2; R1 = R1 + R2 1
MOVE 2000, R1; Mem[2000] = R1 2
MOVE R1, R2; R1 = R2 1

Assume that the clock cycles required for various operations
are given as follows:
• Data transfer between register and memory: 4 clock
cycles,
• Data transfer between two registers: 1 clock cycle,
• ADD with both operands in register: 2 clock cycles, and
• Instruction fetch and decode: 3 clock cycles per word.
How many clock cycles are required to execute the above
program segment?
(b) A hypothetical computer system has two levels (L1 and
L2) cache where L1 and L2 has their hit rates as 94% and
80%, respectively, and miss penalties as 10 and 60 cycles,
respectively. Let the base CPI of this computer system be
1.5 when there is no cache miss. If on average, there are 1.2
memory accesses per instruction, then what is the e!ective
CPI once cache miss occurs?
[6 + 10 = 16]

—: Page 4 of 12 :—

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

m
m .co
c. o

e m
em l a s
s a g
PCB

C9. (a) Let L be a language over an alphabet {a, b} such that the
empty string does not belong to L and the first and the
m
co
last letters of every string in L are the same. Draw a DFA

o m m .
c
. one accepting L.
to accept the language L. Argue whether your DFA is the
s e
m
eProve that the language L = {a b | m ≃= n} is not regular.
minimal
l a
a s
l You may use the fact that the language {a b | n ⇒ 0} is ag
g
(b) m n

a n n

not regular.
[(6 + 4) + 6 = 16]

C10. Suppose the following code is compiled, and run for di!erent
values of N.

o m
c
. {
int main() {

e m
for (int i = 1; i <= N; i++)

l a s
fprintf(stderr, "OPERATING\n");

ag
fork();
fork();
}
fprintf(stderr, "SYSTEMS\n");
return 0;
}

o m
c
Assume that the fork() system call always succeeds.
m .
c. o (a) How many times will the strings OPERATING and SYSTEMS
s em
s em be printed if the value of N is (i) 1, (ii) 2?
g la
gla a the
a
(b) For a given N, let I and J represent, respectively,
N N

number of times the strings OPERATING and SYSTEMS are
printed. Derive recurrence relations for IN and JN .

[(2 + 4) + 10 = 16]

m .
—: Page 5 of 12 :—

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

C11. Consider that node X is sending packets to node Y . The path
from X to Y has a bandwidth of BXY = 5000 bytes/second and a
propagation delay of PXY = 100 milliseconds. The reverse path
from Y to X has a bandwidth of BY X = 9500 bytes/second
and a propagation delay of PY X = 40 milliseconds. Suppose
the size of the data packets is SD = 500 bytes and the size of
the acknowledgement packets is SA = 95 bytes. Ignore the size
of the header in data packets. Moreover, assume that no data
packets or acknowledgement packets are lost during transit and
there is no queuing delay.

(a) Compute the throughput in bytes/second that the node X
can achieve in transmitting to node Y using Stop-and-Wait
protocol.
(b) Suppose instead of Stop-and-Wait, node X uses Sliding
Window protocol.
(i) Compute the size of the window W , in terms of
number of data packets, that node X must use in
order to transfer its data at the maximum possible
rate. Determine the actual rate Tmax that X achieves
while utilizing the window of size W .
(ii) If the bandwidth BY X of the path from Y to X drops to
125 bytes/second, keeping BXY , PXY , PY X , SD and SA
unchanged, can X still achieve the transfer rate Tmax ?
If so, what is the new window size W ? If not, what is
the new limit on Tmax that X can achieve?
[4 + ((4 + 2) + (4 + 2)) = 16]

—: Page 6 of 12 :—

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

m
m .co
c. o

e m
em l a s
s a g
PCB

Group B: Non-CS Group

m
co
Answer Question N1 and any 5 questions from N2 to N13.
m .
c. o
N1. (a) Consider the following function job(), which takes two
s e m
m integers x and y, and returns another integer. a
se g l
positive

g la a
a

What will be the value of job(18,24)? Mathematically,
what does the function job(x,y) compute for two given
positive integers x and y?

o m
c
. itself. For example, 25 is
(b) A positive integer is called automorphic if its square ends

e m
an automorphic numberas
in the same digits as the number

gl
as its square 625 ends with 25,

a
whereas 16 is not automorphic because its square 256 does
not end with 16. Fill in the blanks in the pseudocode
provided below to write the function isAutomorphic,
which determines whether a given number is automorphic.
Note that a / b and a % b compute the quotient and
remainder, respectively, when a is divided by b.

m
m .co
c. o se
m
s em g la
gla a
a

[(5 + 6) + 9 = 20]

m .
—: Page 7 of 12 :—

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

N2. (a) Let bn bn→1 · · · b1 be the decimal representation of an n digit
number m. Let bn bn→1 · · · b2 be the integer a obtained from
m by stripping o! the unit’s digit b1 . Then, show that m
is divisible by 7 if and only if a → 2b1 is divisible by 7.
(b) Prove that:
! " ! " ! " ! " ! "
1001 1002 2023 2024 2025
1+ + + ··· + + = .
1 2 1023 1024 1024

[10 + 6 = 16]

N3. Suppose X = (x1 , x2 , . . . , xn ) is an array of numbers (not
necessarily integers) sorted in the ascending order, and
Y = (y1 , y2 , . . . , yn ) is the array constructed as yi = f (xi ) for
i = 1, 2, . . . , n, where

f (x) = (x + 1)(x → 1)(x → 3).

(a) Describe an algorithm to sort Y using O(n) comparisons.
(b) Provide justification for the correctness and the number of
comparisons used by your algorithm.

[10 + 6 = 16]

N4. (a) Let A be an n⇑n matrix and let I denote the n⇑n identity
matrix. Show that, if A3 = 0, then (I → A) is invertible.
(b) Let V be an n-dimensional vector space over R, and let
F : V ⇓ V be a linear transformation such that F ⇔ F = I,
where I : V ⇓ V is the identify transformation. Prove that
V = Im(I + F ) ↖ Im(I → F ), where ↖ denotes the direct
sum of two subspaces and Im(T ) denotes the image of a
transformation T .
[8 + 8 = 16]

—: Page 8 of 12 :—

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

m
m .co
c. o

e m
em l a s
s a g
PCB

N5. Let f : R ⇓ (0, ↙) be a function satisfying f (x + y) = f (x)f (y)
for all x, y ↔ R.
m
m .co
co
(a) Prove that if f is continuous at 0, then f is continuous at

. e m
m s
every x ↔ R.

s e g l a
a a
(b) Prove or disprove: If f is di!erentiable at 0, then f is

g l di!erentiable at every x ↔ R.
a (c) Determine all such functions f which are di!erentiable
everywhere on R.

[6 + 6 + 4 = 16]

N6. The map below shows all the routes connecting the locations

m
c. o
A, B, C and D. However, there are many bridges, each
indicated with a ∝
? mark. Each bridge is open with probability

e mp), independent of the state
s is closed, the corresponding
p (and closed with probability 1 →
of all other bridges. When a a
l
ag closed.
bridge
segment of the route is also

m
m .co
c. o se
m
s em g la
gla (a) Determine the probability that there is an openaroute from
a A to C that does not pass through D.
(b) Subsequently, determine the probability that there is an
open route from A to B.

[8 + 8 = 16]

m .
—: Page 9 of 12 :—

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

N7. For a graph G = (V, E) and a subset X ↓ V of the vertices,
the induced subgraph G[X] is defined as G[X] = (X, E ↓ ), where
E ↓ = {uv ↔ E | u, v ↔ X}.
Suppose G = (V, E) is a connected undirected graph on two
or more vertices and T = (V, F ) is a spanning tree of G. Let
S ↗ V be a non-empty proper subset of the vertices and define
A = {uv ↔ E | u ↔ S, v ↔ V \ S}. Prove or disprove each of the
following:

(a) A ↘ F ≃= ⊋.
(b) If G[S] has s connected components and G[V \ S] has t
connected components, then A↘F contains at least s+t→1
edges.
(c) If A ↓ F , then either T [S] or T [V \ S] is disconnected.

[4 + 8 + 4 = 16]

N8. Let p(x) = (x→1)(x→2) · · · (x→n+1)(x→n)→1 be a polynomial
where n ⇒ 1. Suppose p(x) = f (x)g(x) where f and g are both
polynomials with integer coe”cients.

(a) Show that f (k) = →g(k) for all k = 1, 2, . . . , n.
(b) Show that either f (x) = →g(x) for all x ↔ R, or one of f
and g is a constant polynomial.
(c) Subsequently, prove that p(x) cannot be written as a
product of two non-constant polynomials with integer
coe”cients.

[2 + 8 + 6 = 16]

—: Page 10 of 12 :—

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

m
m .co
c. o

e m
em l a s
s a g
PCB

N9. (a) Let L be a language over an alphabet {a, b} such that the
empty string does not belong to L and the first and the
m
co
last letters of every string in L are the same. Draw a DFA

o m m .
c
. one accepting L.
to accept the language L. Argue whether your DFA is the
s e
e m
minimal
l a
(b)s Prove that the language L = {a b | m ≃= n} is not regular. g
g a
l You may use the fact that the language {a b | n ⇒ 0} is
m n
a
a not regular. n n

[(6 + 4) + 6 = 16]

N10. Using JK flip-flops and a minimal number of combinatorial logic
gates, design a sequential circuit that takes a stream of bits as

o m
. c
input and outputs 1 whenever three consecutive 0’s appear in

m
e justifications.
the input stream, and outputs 0 otherwise. Show the detailed

l a s
steps of your design with suitable

ag [16]

N11. The switch S shown in the figure is initially at position ‘2’ and
is moved to position ‘1’ at t = 0 second. Then, at t = 2 seconds,
the switch S is again moved to position ‘2’. Find the voltage
across the resistor R2 for t > 2 seconds. You can express the

m
co
final answer in terms of sine, cosine, and exponential functions.

m .
c. o se
m
s em g la
gla a
a

[16]

m .
—: Page 11 of 12 :—

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

N12. A dumbbell consisting of two balls, both of mass m, connected
by a massless rod of length L rests on a frictionless floor against
a frictionless wall until it begins to slide down the wall, as in the
figure below. Derive an expression for the speed of the balls at
the moment when their speeds are equal, in terms of L and g,
where g denotes the gravitational acceleration.
Treat the dumbbell as two point masses separated by a massless
rod. Also assume that the initial state of the dumbbell is vertical
and the image shows the dumbbell some time after it has fallen.

[16]

N13. A thermally insulated cylinder, closed at both ends, is fitted with
a frictionless heat-conducting piston that divides the cylinder
into two parts. Initially, the piston is clamped in the center,
with air of volume V0 at temperature T1 and pressure p1 on one
side, and the same volume of air at temperature T2 and pressure
p2 on the other side. The piston is then released, allowing the
system to reach equilibrium in pressure and temperature, with
the piston in a new position. Assume that the molar specific
heat of air at constant volume is Cv = 32 R.

(a) Derive expressions for the final pressure and final
temperature of the air in the cylinder.
(b) Derive an expression for the total increase in entropy.

[10 + 6 = 16]

—: Page 12 of 12 :—

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