ISI Admission Test 2020 Sample Paper M.Tech(CS), M.Tech(CrS) PCB

FOR ISI ADMISSION TEST EXAM PREPARATION

ISI Admission Test 2020
Sample Paper ·
M.Tech(CS),
M.Tech(CrS) PCB
EXAM YEAR TYPE SUBJECT

ISI Admission Test 2020 Sample Paper M.Tech(CS), M.Tech(CrS) PCB

Notes · Sample Papers · Previous Year Papers · Mock Tests

co m .
. s e
em l a

as a g

m
om . co
Sample Questions 2020

.c e m
Test Code PCB (Short Answer Type)

m
e l a s
a s
l • The questions are divided into two groups, Group A (Com- a g
g
a puter Science) and Group B (Non Computer Science).
• Answer the questions from any one of the groups.

m
. co
s em
g l a
a

m
m c. o
c. o s e m
s em la
gla ag
a

m . c
c. o s e m
m a
se
For more Question Papers, Sample Papers, Notes & Syllabus visit
g l Page 1 of 12

Group A
Computer Science

C1. Let A be a sorted array containing n distinct integers, such that, for
all 1 ≤ i < j ≤ n, we have A[i] < A[j]. Note that the integers stored
in the array A are not necessarily from the set {1, . . . , n}. Design an
algorithm that outputs an index i ∈ {1, . . . , n} such that A[i] = i,
if such an i exists, and outputs −1 otherwise. The worst case run-
ning time of the algorithm should be asymptotically better than O(n).
Prove the correctness of your algorithm and state its asymptotic time
complexity.

C2. Let Kn denote the complete graph on n vertices, with n ≥ 3, and
let u, v, w be three distinct vertices of Kn . Determine the number of
distinct paths from u to v that do not contain the vertex w.

C3. When we add a pair of two-bit binary numbers, say ab and cd, we get
a number of at most three bits, say pqr. Using standard operators of
Boolean algebra, namely AND (∧), OR (∨) and NOT (¬), derive the
Boolean expressions of p, q and r in terms of a, b, c and d.

C4. In a binary tree T , for a node v, the LEFT-HEIGHT(v) is the length of
the longest path from v to any leaf in the left subtree of v. If v has no
left child then LEFT-HEIGHT(v) = 0. The RIGHT-HEIGHT(v) is defined
accordingly.
A node v is said to be properly balanced if

|LEFT-HEIGHT(v) - RIGHT-HEIGHT(v)| ≤ 1.

Design an efficient algorithm that, given a binary tree, enumerates all
the nodes which are properly balanced.

C5. Consider a stack machine where the only available workspace is a stack
whose elements are unsigned integers. We will denote the configuration
of the stack by a sequence. For example [a, b, c, d] represents a stack
with a being the top most element and d the bottom most element.
The stack machine supports the following instructions:

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

co m .
. s e
em l a

as a g

PUSH a Pushes a to the stack, i.e., if [x, y, z] be the stack,

m
after PUSH a, the stack becomes [a, x, y, z].

m . co
DUP Duplicates the top, i.e., if [a, b, c] be the stack, after

ADD co m
.
DUP the stack becomes [a, a, b, c].

m se
a
Adds the two topmost elements, removes them and

se g l
pushes the result, i.e., if [a, b, c] be the stack, after

la SUB a
ADD it becomes [a + b, c].

ag Subtracts the two topmost elements, removes them
and pushes the absolute value of the result, i.e., if
[a, b, c] be the stack, after SUB it becomes [|a − b|, c].
SQR Computes the square of the topmost element, re-
moves it and pushes the result, i.e., if [a, b, c] be
the stack, after SQR it becomes [a2 , b, c].
SFT Removes the top most element, right shifts the ele-
ment by 1 bit, and pushes the result, i.e., if [a, b, c]
be the stack, after SFT it becomes [ba/2c, b, c].

m
co
REV Reverses the order of the three topmost elements in

.
em
the stack, i.e., if [a, b, c, z] be the stack, after REV the

s
configuration becomes [c, b, a, z] (if the stack contains

l a
less than 3 elements, REV is undefined).

a g
Computation starts with an empty stack and after a sequence of op-
erations the top most element is considered as the final result. For
example, to compute an expression ((x + y)2 + bz/2c)2 the following
sequence of instructions may be used:
PUSH x; PUSH y; PUSH z; SFT; REV; ADD; SQR; ADD; SQR

Given two unsigned integers a and b, write a sequence of instructions
to compute the product ab. The instruction sequence should start with:

m
m c. o
PUSH a; PUSH b; . . .

c. o s e m
em la
with no further PUSH operations allowed. After the whole sequence of

las ag
instructions executes, the top of the stack should contain ab.

ag

om . c
m
1

.c s e
m a
se
For more Question Papers, Sample Papers, Notes & Syllabus visit
g l Page 3 of 12

C6. Consider the alphabet Σ = {0, 1, 2, ..., 9, #}, and the language of strings
of the form x#y#z, where x, y and z are strings of digit such that when
viewed as numbers, satisfy the equation x + y = z. For example, the
string 123#45#168 is in this language because 123 + 45 = 168. Is this
language regular? Justify your answer.

C7. Recall that in go-back-N protocol, the transmitting window size is N
and the receiver window size is 1. Consider a pipelined, reliable trans-
port protocol that uses go-back-N with cumulative acknowledgment.
Assume that the timeouts trigger retransmissions (but note that dupli-
cate acknowledgments do not). Further assume that the receiver does
not maintain any receive buffer, the one-way delay between the sender
and receiver is 50 ms, and every packet is 10,000 bits long. Suppose
that the sender must be able to send at a steady rate of 1 Gb/s (gigabit
per second) under ideal conditions.

(a) What should be the window size to allow the steady rate men-
tioned above?
(b) Suppose that the expected number of packets lost per 100,000
packets is 1. If the sender uses a timeout of 500 ms and a window
size of 20,000 packets, calculate the expected gap between two
timeouts, when
(i) The bottleneck link rate is 1 Gb/s.
(ii) The bottleneck link rate is 2 Gb/s.

C8. Let us assume that a disk scheduling algorithm is applied on a storage
disk to access several cylinders (numbered as 0, 1, . . . , n arranged in
ascending order) for some I/O operations. These are received in the
order < q, r, s, t >.
If the disk head starts from the cylinder p, then state the relations
among p, q, r, s, and t with proper justifications such that both the
scheduling algorithms SSTF and SCAN perform similarly in terms of the
total head movements required.
Note that, in SSTF (Shortest Seek Time First) the disk head moves
to the nearest cylinder among the unaccessed ones at any point. In
SCAN, first the disk head accesses all the cylinders while moving toward
cylinder 0 and then the disk head moves toward the other end.

2

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

co m .
. s e
em l a

as a g

C9. Consider a byte addressable memory with 16 bit addresses and a 2-

m
way set associative L1 cache of size 8 kB (kilobyte). Each cache line

m . co
is 4 words long. A process sequentially accesses the following memory

c. o0x1004, 0x1010, 0x11C0, 0x2000, 0x3000, 0x1006, 0x2001 e m
addresses:

m the L1 cache is initially empty and the LRU (least recently
eused)
0x1000,

l a s
sAssuming
la cess will result in a hit or a miss for each of the above addresses. ag
ag
page replacement policy is used, indicate whether the cache ac-

C10. Let R be a relation with functional dependencies F. For any subset of
attributes X ⊆ R, the closure of X is defined as the set

X + = {A ∈ R | X → A holds with respect to F}.

For two non-empty attribute sets Y and Z in R, prove or disprove each
of the following statements:

m
c. o
(a) (Y + Z)+ = (Y Z)+

em only of positive and negative
(b) (Y Z)+ = Y + Z +

C11. Consider an array of length nsconsisting
g la to rearrange the array so that all the
a before all the positive integers, using O(n)
integers. Design an algorithm
negative integers appear
time and only constant amount of extra space.

C12. You can climb up a staircase of n stairs by taking steps of one or two
stairs at a time.

(a) Formulate a recurrence relation for counting an , the number of
distinct ways in which you can climb up the staircase.

m
c. o
(b) Mention the boundary conditions for your recurrence relation.

m
c. o m
(c) Find a closed form expression for an by solving your recurrence.

s e
em la
C13. An n-variable Boolean function f : {0, 1}n → {0, 1} is called symmetric

las ag
if its value depends only on the number of 1’s in the input. Let σn

g
denote the number of such functions.

a
(a) Calculate the value of σ4 .
(b) Derive an expression for σn in terms of n.

C14. Let the valid moves along a staircase be U (one step up) and D (one
step down). For example, the string s = U U DU represents the se-
quence of moves as two steps up, then one step down, and then again
one step up. Suppose a person is initially at the base of the staircase.

om . c
m
3

.c s e
m a
se
For more Question Papers, Sample Papers, Notes & Syllabus visit
g l Page 5 of 12

A string denoting a sequence of steps that takes the person below the
base is invalid. For example, the sequence U U DDDU is invalid. Let
L be the language defined by the set of valid strings which represent
scenarios in which the person never returns to the base of the staircase
after the final step.
(a) Show that L is not regular.
(b) Write a context free grammar for accepting L.

C15. Consider a max-heap of n distinct integers, n ≥ 4, stored in an array
A[1 . . . n]. The second minimum of A is the integer that is less than all
integers in A except the minimum of A. Find all possible array indices
of A in which the second minimum can occur. Justify your answer.

C16. The following function computes an array SPF, where, for any integer
1 < i < 1000, SPF[i] is the smallest prime factor of i. For example,
SPF[6] is 2, and SPF[11] is 11.
There are five missing parts in the following code, commented as /*
Blank */. For each of them, copy the entire line with the comment
and fill the blank appropriately in your answer sheet.

int SPF[1000];

void findSPF() {
SPF[1] = 1;

// Initializing SPF of every number to be itself
for (int i = 2; i < 1000; i++) {
_____; /* Blank 1 */
}

// SPF of every even number is 2
for (int i = 4; i < 1000; i += 2) {
SPF[i] = _____; /* Blank 2 */
}

// For odd numbers, updating the SPFs of their multiples
for (int i = _____; i * i < 1000; i++) { /* Blank 3 */
if (SPF[i] == i) { // No smaller factor of i found yet
for (int j = _____; j < 1000; j+= i) { /* Blank 4 */
if (SPF[j] == j) {
SPF[j] = _____; /* Blank 5 */
}

4

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

co m .
. s e
em l a

as a g

}

m
co
}

om .
}

.c e m
}

em l a s
l a s a g
g
C17. A context switch from a process Pold to a process Pnew consists of the

a
following steps:

• Step I: saving the context of P ; old
• Step II: running the scheduling algorithm to pick Pnew ;
• Step III: restoring the saved context of Pnew .

Suppose Steps I and III together take T0 units of time. The scheduling
algorithm takes nT1 units of time, where n is the number of ready-

m
to-run processes. The scheduling policy is round-robin with a time

co
slice of 10ms. Compute the CPU utilization for the following scenario:

.
em
k processes become ready at almost the same instant in the order

s
P1 , P2 , . . . , Pk ; each process requires exactly one CPU burst of 20ms

l a
and no I/O burst.

a g
C18. Consider a 5-stage instruction pipeline. The stages and the corre-
sponding stage delays are given below.

Instruction Stage delay
Fetch instruction (FI) 3 ns
Decode instruction (DI) 4 ns
Fetch operand (FO) 7 ns
Execute instruction (EI) 10 ns

o m
Write result (WR) 7 ns

m Assume that there is no delay between two consecutive stages. .Con- c
c. o s eatmtheitFIis
em a
Alprogram con-
sider a processor with a branch prediction mechanism by which

las stage itself, without executing the branch instruction. g
sisting of a sequence of 10 instructions I1, I2, . . . , I10,ais executed in the
always able to correctly predict the direction of the branch

ag pipeline, where the 5th instruction (I5) is the only branch instruction
and its branch target is the 8th instruction (I8).

(a) Draw the pipeline diagram over time showing how the instructions
I1, I2, . . . , I10 flow through the pipeline stages in this processor.
(b) Calculate the time (in ns) needed to execute the program.

om . c
m
5

.c s e
m a
se
For more Question Papers, Sample Papers, Notes & Syllabus visit
g lPage 7 of 12

C19. The data link layer uses a fixed-size sliding window protocol, where the
window size for the connection is equal to twice the bandwidth-delay
product of the network path. Consider the following three scenarios, in
each of which only the given parameter changes as specified (no other
parameters change). For each scenario, explain whether the through-
put (not utilization) of the connection increases, decreases, remains
the same, or cannot be determined:

(a) the packet loss rate L decreases to L/3;
(b) the minimum value of the round trip time R increases to 1.8R;
(c) the window size W decreases to W/3.

C20. Consider two n × 1 vectors u and v, stored as tables U(ind,val) and
V(ind,val) with the same schema. A row (i, ui ) of table U specifies
that the i-th element of vector u has value ui (similarly for v, respec-
tively). Only the non-zero entries of the vectors are stored in the cor-
responding tables. For example, if the vector u equals (0, 1, 3, 0, 2, 0),
then it is represented in table U as:

ind val
2 1
3 3
5 2

Write a relational algebra expression or an SQL query to compute the
sum u + v of the two vectors u and v. Explain your solution.

6

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

co m .
. s e
em l a

as a g

Group B

m
co
Non Computer Science

.c om
NC1. Let {an } be a decreasing sequence such that ∞
e m .
P
n=1 an is convergent.

e m
Prove that the sequence {nan } goes to zero as n → ∞.

l a s
l a s ag
ag
NC2. Consider an n×n matrix A = In −ααT , where In is the identity matrix
of order n and α is an n × 1 column vector such that αT α = 1. Prove
that A2 = A.

NC3. Let A and B be two invertible real matrices of order n. Show that
det (xA + (1 − x)B) = 0 has finitely many solutions for x.

m
NC4. Show that for every θ ∈ (0, π2 ), there exists a unique real number xθ

. co
such that
3

em
(sin θ)xθ + (cos θ)xθ = .
2

l a s
a g real valued functions on [a, b] and are
NC5. Suppose f and g are continuous
0
differentiable on (a, b). Assume that g (x) 6= 0 for any x ∈ (a, b). Prove
that there exists ξ ∈ (a, b) such that
f 0 (ξ) f (b) − f (a)
0
= .
g (ξ) g(b) − g(a)

m
c. o
NC6. Consider the function f : R2 → R defined by

m
c. o e m
xy

s
f (0, 0) = 0, f (x, y) = 2 , (x, y) 6= (0, 0).

em Prove that the directional derivative of f at (0, 0) existsain all direc-
x + y2

s tions. Is f continuous at (0, 0)? Justify your answer. g
l
gla a
a
NC7. Solve the differential equation
dy
x2 (x2 − 1) + x(x2 + 1)y = x2 − 1.
dx

om . c
m
7

.c s e
m a
se
For more Question Papers, Sample Papers, Notes & Syllabus visit
g l Page 9 of 12

NC8. Let f be a real valued function on R. If for all real x,

f (x) + 3f (1 − x) = 5

holds, then show that f is a constant function.

NC9. Let f : [0, 1] → [0, ∞) be a continuous function. Let

a = inf0≤x≤1 f (x) and b = sup0≤x≤1 f (x).

For every positive integer m, define
Z 1
cm = [ (f (x))m dx]1/m .
0

Prove that cm ∈ [a, b], for all m ≥ 1, limm→∞ cm exists and find its
value.

NC10. Let f1 : [0, 4] → [0, 4] be defined by f1 (x) = 3 − (x/2). Define fn (x) =
f1 (fn−1 (x)) for n ≥ 2.

• Prove that limn→∞ fn (0) exists.
• Find the set of all x such that limn→∞ fn (x) exists and also find
the corresponding limits.

NC11. Let m be a fixed integer greater than 2. Prove that all simple graphs
having n (n
≥ 3) vertices and with m edges are connected if and only
if m > n−1
2 .

NC12. Suppose the collection {A1 , · · · , Ak } forms a group under matrix mul-
tiplication, where each Ai is an n × n real matrix. Let A = ki=1 Ai .
P

• Show that A2 = kA.
• If the trace of A is zero, then show that A is the zero matrix.

NC13. Let A be an n × n integer matrix whose entries are all even. Show that
the determinant of A is divisible by 2n . Hence or otherwise, show that
if B is an n × n matrix whose entries are ±1, then the determinant of
B is divisible by 2n−1 .

8

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

co m .
. s e
em l a

as a g

NC14. Let

m
 
1 2 1 −1

m . c o
A= 2 0 t 0 .
 

coA) = 2, calculate t. m
0 −4 5 2

. s e
emn, r, s be positive integers, each greater than 2. Prove that n − 1 gla
If rank(

NC15. sLet
la divides n − 1 if and only if r divides s. a
r

g
aNC16. Let Ω = {1, 2, 3, . . . , 100}. In how many ways
s

a1 < a2 < a3 < a4 < a5 , ai ∈ Ω
can be chosen from Ω such that ai+1 − ai ≥ 2 for each i ?

NC17. Show that 5 | x | +x(x − 2) ≥ 0 for every real number x.

m
c. o
NC18. Let N = 1! + 2! + · · · + 2020!. Find the remainder obtained when N is

NC19. Let G be a finite group and Hem
divided by 8.

Prove that H is normal inla
s the only subgroup of G of order |H|.
ag
G.

NC20 Let H and K be subgroups of a group G of finite indices (i.e., [G : H] <
∞ and [G : K] < ∞). Prove that H ∩ K is also of finite index ( i.e.,
[G : H ∩ K] < ∞).

NC21. Consider all the permutations of the numbers 1, 2, . . . , 9. Find the num-
ber of permutations which satisfy all of the following:
• the sum of the numbers lying between 1 and 2 (including 1 and

m
c. o
2) is 12,

m
c. o m
• the sum of the numbers lying between 2 and 3 (including 2 and

s e
em
3) is 23,

s la
ag
• the sum of the numbers lying between 3 and 4 (including 3 and

la
4) is 34,

ag • the sum of the numbers lying between 4 and 5 (including 4 and
5) is 45.

NC22. If α, β, γ are the roots of the equation x3 + 6x + 1 = 0, then prove
that
α β β γ γ α
+ + + + + = −3.
β α γ β α γ

om . c
m
9

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

NC23. Let X ∼ Bin (n, p), and Y ∼ P oisson (λ). Let

T = X1 + X2 + · · · + XY ,

with Xi ’s i. i. d. Bin (n, p) (and independent to Y ), and

S = Y1 + Y2 + · · · + YX ,

with Yi ’s i. i. d. P oisson (λ) (and independent to X). Compare
Expectations of T and S and Variances of T and S.

10

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