PCB Merged
PCB Merged
PCB Merged
The selection test for M.Tech. in Computer Science will consist of two parts -
– Group A : A test for all candidates in analytical ability and mathematics at the B.Sc. (pass)
level, carrying 40 marks.
– Group B: A test, divided into several sections, carrying equal marks of 60 in Mathematics,
Statistics, and Physics at the B. Sc. (Hons.) level, and in Computer Science, and Engineering
and Technology at the B.Tech. level. A candidate has to answer questions from only one of
these sections according to his/her choice.
The syllabus and sample questions for the MIII test are available separately.
The syllabus and sample questions for the CS test are given below.
Note:
1. Not all questions in the sample set are of equal difficulty. They may not carry equal marks
in the test.
2. Each of the tests MIII, Group A of Test CS and Group B of Test CS will have individual
qualifying marks.
Elements of set theory. Permutations and combinations. Functions and relations. Theory of
equations. Inequalities.
Limits, continuity, sequences and series, differentiation and integration with applications, maxima-
minima.
Elementary Euclidean geometry and trigonometry.
Elementary number theory, divisibility, congruences, primality.
Determinants, matrices, solutions of linear equations, vector spaces, linear independence, di-
mension, rank and inverse.
2
Group B
Mathematics
(B.Sc. Hons. level)
Calculus and real analysis - real numbers, basic properties, convergence of sequences and se-
ries, limits, continuity, uniform continuity of functions, differentiability of functions of one or
more variables and applications, indefinite integral, fundamental theorem of Calculus, Riemann
integration, improper integrals, double and multiple integrals and applications, sequences and
series of functions, uniform convergence.
Linear algebra - vector spaces and linear transformations, matrices and systems of linear equa-
tions, characteristic roots and characteristic vectors, Cayley-Hamilton theorem, canonical forms,
quadratic forms.
Graph Theory - connectedness, trees, vertex coloring, planar graphs, Eulerian graphs, Hamil-
tonian graphs, digraphs and tournaments.
Abstract algebra - groups, subgroups, cosets, Lagrange’s theorem, normal subgroups and quo-
tient groups, permutation groups, rings, subrings, ideals, integral domains, fields, characteristics
of a field, polynomial rings, unique factorization domains, field extensions, finite fields.
Differential equations - solutions of ordinary and partial differential equations and applications.
Statistics
(B.Sc. Hons. level)
Physics
(B.Sc. Hons. level)
Computer Science
(B.Tech. level)
Data structures - array, stack, queue, linked list, binary tree, heap, AVL tree, B-tree.
Programming languages - Fundamental concepts abstract data types, procedure call and pa-
rameter passing, languages like C and C++.
Design and analysis of algorithms Asymptotic notation, sorting, selection, searching.
Computer organization and architecture - Number representation, computer arithmetic, memory
organization, I/O organization, microprogramming, pipelining, instruction level parallelism.
Operating systems - Memory management, processor management, critical section problem,
deadlocks, device management, file systems.
Formal languages and automata theory - Finite automata and regular expressions, pushdown
automata, context-free grammars, Turing machines, elements of undecidability.
Principles of Compiler Construction - Lexical analyzer, parser, syntax-directed translation, in-
4
Moments of inertia, motion of a particle in two dimensions, elasticity, friction, strength of ma-
terials, surface tension, viscosity and gravitation.
Laws of thermodynamics and heat engines.
Electrostatics, magnetostatics and electromagnetic induction.
Magnetic properties of matter - dia, para and ferromagnetism.
Laws of electrical circuits - RC, RL and RLC circuits, measurement of current, voltage and
resistance.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
p-n junction, bipolar & FET devices, transistor amplifier, oscillator, multi-vibrator, operational
amplifier.
Digital circuits - logic gates, multiplexer, de-multiplexer, counter, A/D and D/A converters.
Boolean algebra, minimization of switching functions, combinational and sequential circuits.
C Programming language.
5
SAMPLE QUESTIONS
Group A
Mathematics
A1. Let each row and each column of a n × n matrix A be a permutation of {1, 2, . . . , n} and
let A be symmetric.
(a) If n is odd, prove that each of 1, 2, . . ., n occurs on the principle diagonal of A.
(b) For every even number n, show that there exists an A in which not all of 1, 2, . . ., n
appear on the diagonal.
A2. Let S = {(a1 , a2 , a3 , a4 ) : ai ∈ <, i = 1, 2, 3, 4 and a1 + a2 + a3 + a4 = 0} and
Γ = {(a1 , a2 , a3 , a4 ) : ai ∈ <, i = 1, 2, 3, 4 and a1 − a2 + a3 − a4 = 0}. Find a basis
for S ∩ Γ .
A3. Provide the inverse of the following matrix :
c0 c1 c2 c3
c2 c3 c0 c1
c3 −c2 c1 −c0
c1 −c0 c3 −c2
√ √ √ √
1+√ 3
where c0 = , c1 = 3+√ 3 , c2 = 3−√ 3 , c3 = 1−√ 3
.
4 2 4 2 4 2 4 2
(Hint: What is c20 + c21 + c22 + c23 ?)
A4. For any real
£ number
¤ x£ and for¤ any positive
£ integer
¤ n show that
[x] + x + n1 + x + n2 + . . . + x + n−1 n = [nx]
where [a] denotes the largest integer less than or equal to a.
A5. Let bq bq−1 . . . b1 b0 be the binary representation of an integer b, i.e.,
q
X
b= 2j bj , bj = 0 or 1, for j = 0, 1, . . . , q.
j=0
Show that b is divided by 3 if b0 − b1 + b2 − . . . + (−1)q bq = 0.
√ √
A6. A sequence {xn } is defined by x1 = 2, xn+1 = 2 + xn , n = 1, 2, . . .. Show that the
sequence converges and find its limit.
A7. Find the following
µ limit: ¶
1 1 1
lim √ +√ + ... + √
x→∞ n2 + 1 n2 + 2 n2 + n
A8. Find the total number of English words (all of which may not have proper English meaning)
of length 10, where all ten letters in a word are not distinct.
A9. Let a0 + a21 + a32 + . . . + n+1
an
= 0, where ai ’s are some real constants. Prove that the
equation a0 + a1 x + a2 x + . . . + an xn = 0 has at least one solution in the interval (0,1).
2
A10. Let φ(n) be the number of positive integers less than n and having no common factor with
n. For example, for n = 8, the numbers 1, 3, 5, 7 have no common factors with 8, and hence
φ(8) = 4. Show that
(a) φ(p) = p − 1.
(b) φ(pq) = φ(p)φ(q), where p and q are prime numbers.
6
A11. Let Tn be the number of strings of length n formed by the characters a, b and c that do not
contain cc as a substring.
(a) Find the value of T4 .
(b) Prove that Tn ≥ 2n+1 for n > 1.
A12. Consider a square grazing field with each side of length 8 metres. There is a pillar at the
centre of the field (i.e. at the intersection of the two diagonals). A cow is tied to the pillar
using a rope of length √8 meters. Find the area of the part of the field that the cow is allowed
3
to graze.
A13. Let a1 a2 a3 . . . ak be the decimal representation of an integer a (ai ∈ {0, . . . 9} for i =
1, 2, , . . . , k). For example, if a = 1031, then a1 =X
1, a2 = 0,Xa3 = 3, a4 = 1. Show that a
is divisible by 11 if and only if ai − ai
i odd i even
is divisible by 11.
A14. Let a < b < c < d be four real numbers, such that all six pairwise sums are distinct.
The values of the smallest four pairwise sums are 1, 2, 3, and 4 respectively. What are the
possible values of d? Justify your answer.
A15. Consider the 5 × 10 matrix A as given below.
1 6 11 16 21 26 31 36 41 46
2 7 12 17 22 27 32 37 42 47
A=
3 8 13 18 23 28 33 38 43 48
4 9 14 19 24 29 34 39 44 49
5 10 15 20 25 30 35 40 45 50
Let a set of ten distinct elements b1 , b2 , . . . , b10 be chosen from A such that exactly
two elements are chosen from each row and exactly one from each column. Show that
b1 + b2 + . . . + b10 is always equal to 255.
Group B
Mathematics
xn +3
M1. Let 0 < x1 < 1. If xn+1 = 3xn +1 , n = 1, 2, 3, · · ·
7
5xn +3
(a) Show that xn+2 = 3x n +5
, n = 1, 2, 3, · · ·
(b) Hence or otherwise, show that lim xn exists.
n→∞
(c) Find lim xn .
n→∞
M2. Let
(
(x − 1)(x4 + 4x + 7) if x is rational.
f (x) =
(1 − x)(x4 + 4x + 7) if x is irrational.
M7. Let V be a finite dimensional vector space and T be a linear transformation on V . Prove that
there exists an m ≥ 1 such that
(a) Ker(T n ) = Ker(T m ) for all n ≥ m.
(b) Ker(T m ) ∩ T m (V ) = 0.
Note: T n denotes the composite map T ◦ T ◦ T ◦ · · · ◦ T (n times); and Ker denotes the
kernel.
√
M8. (a) Let {an : n ≥ 1} be a sequence P
of positive numbers. Define
P
bn = a2n−1 a2n for
n ≥ 1. If an is monotonic and bn converges, prove that an also converges.
(b) Let M be the set of all 3 × 3 matrices of the following form:
a 0 0
0 a 0
b c a
where a, b, c ∈ Z2 . Show that with standard matrix addition and multiplication (over Z2 ),
M is a commutative ring. Find all the idempotent elements of M .
M9. State whether the following statements are true or false. Justify your answers.
(a) There exists a group homomorphism from the group of complex numbers C under ad-
dition to the group of real numbers R under addition.
(b) There does not exist any ring homomorphism
√ f from Z[i] to Z such that f (1) = 1. [Here
Z denotes the ring of integers and i = −1]
M10. (a) Let G be a group. For a, b in G we say that b is conjugate to a (written b ∼ a), if there
exists g in G such that b = gag −1 . Show that ∼ is an equivalence relation on G. The
8
equivalence classes of ∼ are called the conjugacy classes of G. Show that a subgroup
N of G is normal in G if and only if N is a union of conjugacy classes.
(b) Let G be a group with no proper subgroups. Show that G is finite. Hence or otherwise,
show that G is cyclic.
M11. Let G be the group of all 2×2 non-singular matrices with matrix multiplication as the binary
operation. Provide an example of a normal subgroup H of G such that H 6= G and H is not
a singleton.
M12. (a) A rumour spreads through a population of 5000 people at a rate proportional to the prod-
uct of the number of people who have heard it and the number who have not. Suppose
that 100 people initiate a rumour and that a total of 500 people know the rumour after
two days. How long will it take for half the people to hear the rumour? [assume that
log 9 129
log 49 = 229 ]
(b) Find the equation of the curve satisfying the differential equation
d2 y 2 dy
dx2
(x + 1) = 2x dx .
M15. Let k be a positive integer. Let G = (V, E) be the graph where V is the set of all strings of
0’s and 1’s of length k, and E = {(x, y) : x, y ∈ V , x and y differ in exactly one place}.
(a) Determine the number of edges in G.
(b) Prove that G has no odd cycle.
(c) Prove that G has a perfect matching.
(d) Determine the maximum size of an independent set in G.
M16. χ(D), the chromatic number of a digraph D = (V, A), is defined as the minimum number of
parts in a partition V = V1 ∪ V2 ∪ · · · ∪ Vk , such that, Vi is an independent set for 1 ≤ i ≤ k.
Justify whether every digraph D contains a path of length at least χ(D) − 1.
Statistics
S3. Let X and Y be independent and identically distributed random variables, with P (X =
k) = 2−k for k = 1, 2, 3, . . .. Find P (X > Y ) and P (X > 2 Y ).
S4. Let X1 , X2 , X3 , . . . , Xn be independent random variables having the same Cauchy distri-
bution with location parameter θ. The corresponding probability density function is given
by
1
f (x|θ) = , x, θ ∈ IR.
π[1 + (x − θ)2 ]
Suppose we wish to find the maximum likelihood estimator of θ.
(a) Show that, for each i
· ¸ · 2 ¸
∂ log f (X|θ) ∂ log f (X|θ) 1
Eθ = 0 and Eθ = .
∂θ ∂θ2 2
N
P
1
where Φ(·) is the distribution function of the standard normal distribution and X̄ = N Xi .
i=1
S6. Consider a data set with three variables X1 , X2 and X3 . The correlation between X1 and
X2 is found to be 0.75, while that between X2 and X3 is found to be 0.52. The multiple
correlation coefficient of X1 on X2 and X3 is 0.86.
(a) Are these values consistent? Justify your answer.
(b) Using the above figures is it possible to compute the correlation between X1 and X2
eliminating the effect of X3 ? Justify your answer.
10
1 1
f (x) = g(x) + h(x),
2 2
where g(x) and h(x) are the probability density functions of normal distributions having
unit variance, and means −µ and µ respectively.
(a) Find a sufficient statistic for µ.
(b) Derive an estimator for µ using the method of moments.
S8. Let X = (X1 , X2 , . . . , Xn )0 be a random sample from the exponential distribution E(θ, σ)
with unknown location parameter θ and unknown scale parameter σ . Consider the problem
of testing H0 : θ = θ0 against H1 : θ 6= θ0 .
(a) Let X(1) ≤ X(2) ≤ . . . ≤ X(n) be the order statistics associated with X . Let
X(1) − θ0
T = Pn .
i=1 (Xi − X(i) )
has size α.
(c) Show that for any alternative (θ1 , σ) with θ1 < θ0 , the power of the level-α test in (b),
denoted by β(θ1 , σ), is given by
S9. Let X = (X1 , X2 , . . . , Xn )0 be a random sample from the uniform distribution on (0, θ).
Show the following:
(a) For testing H0 : θ = θ0 against H1 : θ ≥ θ0 , any test ϕ defined as
½
1 if max(x1 , x2 , . . . , xn ) > θ0
ϕ(x) =
0 otherwise
for which
i. Eθ0 (ϕ(X)) = α, and
ii. Eθ (ϕ(X)) ≤ α for θ ≤ θ0 ,
is uniformly most powerful (UMP) at level α.
(b) For testing H0 : θ = θ0 against H1 : θ 6= θ0 , a unique UMP test at level α exists, and is
given by
1 if max(x1 , x2 , . . . , xn ) > θ0 or
1
ϕ(x) = max(x1 , x2 , . . . , xn ) ≤ θ0 α n
0 otherwise
S10. Consider a population with 3 units, labeled 1, 2, 3. Let the observations on a random variable
of interest (Y ) for these units be y1 , y2 and y3 . A simple random sample without replacement
(SRSWOR) of size 2 is drawn from this population. Consider the two estimators :
i. Ȳ , that is, the usual sample mean, and
11
ii. y1 y2
2 + 2 if the sample consists of units 1 and 2,
Ȳˆ = y1
2 + 2y3
3 if the sample consists of units 1 and 3,
y2 y3
2 + 3 if the sample consists of units 2 and 3.
(a) Show that both estimators are unbiased for the population mean.
(b) Show that Var(Ȳˆ ) < Var(Ȳ ) if y3 (3y2 − 3y1 − y3 ) > 0.
(Hint: Suppose X̄ is the sample mean for a simple random sample without replacement
of size n from a population of size N with population unit values x1 , . . . , xN . Then
N
P
µ ¶ (xi − x̄)2 N
N −n i=1 1X
var(X̄) = where x̄ = xi .
Nn N −1 N
i=1
S11. Suppose (X1 , X2 , . . . , Xn ) are independent and identically distributed exponential random
variables with location parameter θ (> 0) and scale parameter equal to 1. Let X(1) =
min{X1 , X2 , . . . , Xn }.
(a) Show that the distribution function of T = X(1) , denoted by Fθ (t), is a decreasing
function of θ.
(b) Given α (∈ (0, 1)), use (a) to obtain a (1 − α) confidence interval for θ.
S12. Let Y1 , Y2 and Y3 be uncorrelated random variables with common variance σ 2 > 0 such
that
E(Y1 ) = β1 + β2 ,
E(Y2 ) = 2β1 ,
E(Y3 ) = β1 − β2 ,
where β1 and β2 are unknown parameters. Find the residual (error) sum of squares under
the above linear model.
S13. (a) Suppose X = (X1 , X2 , X3 )0 ∼ N3 (µ, Σ), where
µ1 σ11 σ12 σ13
µ = µ2 and Σ = σ21 σ22 σ23 .
µ3 σ31 σ32 σ33
S14. An experimenter wants to study three factors, each at two levels, for their individual effects
and interaction effects, if any. If the experimental units are heterogeneous with respect to
two factors of classification, suggest a suitable experimental design for the study. Give the
analysis of variance (ANOVA) for the suggested design, indicating clearly how the various
sums of squares are to be computed.
12
Physics
P1. (a) A particle of mass m moves in one dimension under the influence of a potential V (x).
Suppose it is in an energy eigenstate ψ(x) = (γ 2 /π)1/4 exp(γ 2 x2 /2) with energy E =
~2 γ 2 /2m (~ = h/2π and γ is a constant).
(i) Find the mean values of the position and momentum of the particle.
(ii) Derive an expression for the potential V (x).
(b) A particle of mass m moves in a one dimensional box of length l with potential
V (x) = 0, 0 < x < l,
V (x) = ∞, otherwise.
At time t = 0, the wave function
p of this particle is known to have the form
ψ(x, t = 0) = 30/l5 x(l − x), 0 < x < l,
ψ(x, t = 0) = 0, otherwise.
Write an expression for ψ(x, t > 0) as a series.
P2. (a) Consider a material that has two solid phases, a metallic phase and an insulator phase.
The phase transition takes place at the temperature T0 which is well below the Debye
temperature for either phase. The high temperature phase is metastable all the way down
to T = 0 and the speed of sound, cs , is the same for each phase. The contribution to the
heat capacity coming from the free electrons to the metal is
k
Ce = ρe Vγ T, γ = 3π 2
4TF
where ρe is the number density of the free electrons, TF is the Fermi temperature, K is
the Boltzmann constant, and V is the volume. Calculate the latent heat per unit volume
required to go from the low temperature phase to the high temperature phase at T = T0 .
Which phase is the high temperature phase?
(b) A crystal at temperature T is made up of N noninteracting atoms, where each atom can
be in one of two states, the energies of these states being B .
i. Find the partition function of this system.
ii. Find the energy of this system.
iii. Find the entropy of this system and then give the expression in the limit of very low
and very high temperatures.
P3. (a) A particle of mass m moves under a force directed towards a fixed point and this force
depends on the distance from the fixed point. Show that
i. the particle will be constrained to move in a plane, and
ii. the areal velocity of the particle is constant.
(b) If the force F varies as the inverse of the square of the distance , show that
∇×F=0
(b) A uniform thin bar of mass M is supported by two rapidly rotating rollers whose axes
are separated by a fixed distance a. The bar is initially placed at rest asymmetrically, as
shown in the figure below. C denotes the centre of the bar.
x C
(i) If the rollers rotate in opposite directions as shown in the figure, derive the equation
of motion of the bar and solve for x(t), where x(t) is the displacement of C from
the left roller at time t. Assume x(0) = x0 , ẋ(0) = 0, and the coefficient of kinetic
friction between the bar and the rollers to be µ.
(ii) If the directions of rotation of the rollers are reversed, calculate the displacement
x(t). Again assume x(0) = x0 and ẋ(0) = 0.
P5. (a) Consider a hollow sphere of radius r having surface density of mass equal to 3/4. Con-
sider any point inside the sphere which is at a distance a from the origin. Find the
gravitational force and potential at that point due to the mass of the sphere.
(b) In a Millikan’s oil drop experimental setup, two small negatively charged spherical oil
droplets having radii 3r and 5r were allowed to fall freely in the closed chamber filled
with air. The downward terminal velocities attained by them were v1 and v2 respectively.
Subsequently, under the action of a strong electric field, the droplets attained upward
terminal velocities v1 /6 and v1 /20 respectively. Neglecting the buoyant force of air
and assuming the charges to be uniformly distributed over the surface of the droplets,
compare their surface charge densities.
P6. (a) Consider two concentric metal spheres of finite thickness in vacuum, as shown in the
figure below. The inner sphere has inner and outer radii a1 and a2 respectively, where
a1 < a2 . Similarly, the outer sphere has inner and outer radii b1 , b2 respectively, where
b1 < b 2 .
b1
a1
a2
b2
A charge Q1 is put on the inner sphere and a charge Q2 on the outer sphere. Find the
charge densities on the inner and outer surfaces of each sphere. If Q1 = −Q2 , find the
mutual capacitance of the system.
(b) The Lorentz force for a particle of mass m and charge q is
à →!
−
−
→ −→ −→
v ×B
F =q E+
c
14
−
→ −
→
(i) Show that if the particle moves in a time independent electric field E = − ∇φ(x, y, z)
and any magnetic field, then the energy 12 mv 2 + qφ is a constant.
−
→ t
(ii) Suppose the particle moves along the x-axis in the electric field E = Ae− τ êx ,
where A and τ are both constants and êx is the unit vector along x-axis. Find the
displacement x(t) of the particle at time t, assuming that the magnetic field is zero
along the x-axis and x(0) = ẋ(0) = 0.
P7. (a) Two objects A and B travel with velocities 45 c and 53 c (c is the velocity of light in
vacuum) respectively with respect to a stationary observer sitting on the earth. The two
objects are moving along the same straight line in the same direction.
(i) How fast should another object C travel between them, so that it appears to C that
both A and B are moving at the same speed?
(ii) Hence determine the speed of A (or B ) as measured by C .
(b) A proton and a neutron can undergo radioactive capture at rest resulting in a deuteron
and a photon: p + n → d + γ . Find the energy of the photon emitted in this capture in
terms of the masses of the particles.
(c) A p-state electron and an s-state electron are coupled via
P11. An elementary particle called Σ−, at rest in laboratory frame, decays spontaneously into
two other particles according to Σ− → π − + n. The masses of Σ−, π − and n are M1 , m1 ,
and m2 respectively.
(a) How much kinetic energy is generated in the decay process?
(b) What are the ratios of kinetic energies and momenta of π − and n?
P12. Consider the following truth table where A, B and C are Boolean inputs and T is the
Boolean output.
A B C T
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Express T in a product-of-sum form and hence, show how T can be implemented using
NOR gates only.
P13. (a) A series R-L-C circuit is excited from a constant-peak variable frequency voltage source
of the form V = V0 sin ωt, where V0 is constant. The current in the circuit becomes
maximum at a frequency of ω0 = 600 rad/sec. and falls to half of the maximum value
at ω = 400 rad/sec. If the resistance in the circuit is 3Ω , find L and C .
(b) Find the value of R and the current flowing through R shown in the figure when the
current is zero through R0
P15. Consider the following circuit where the triangular symbol represents an ideal op-amp.
16
(a) Calculate the output voltage v0 for the (i)common-mode operation and (ii) difference
mode operation.
(b) Also calculate the value of the common-mode rejection ratio for R0 /R = R1 /R2 .
P16. (a) A particle of mass m is moving in a plane under the action of an attractive force propor-
tional to 1/r2 , r being the radial distance of the particle from the fixed point. Write the
Lagrangian of the system and using the Lagrangian show that the areal velocity of the
particle is conserved (Kepler’s second law).
(b) A particle of mass m and charge q is moving in an electromagnetic field with velocity
v . Write the Lagrangian of the system and hence find the expression for the generalized
momentum.
Computer Science
C1. (a) A grammar is said to be left recursive if it has a non-terminal A such that there is a
derivation A =⇒+ Aα for some sequence of symbols α. Is the following grammar left-
recursive? If so, write an equivalent grammar that is not left-recursive.
A → Bb A → a
B → Cc B → b
C → Aa C → c
(b) An example of a function definition in C language is given below:
char fun (int a, float b, int c)
{ /* body */ · · · }
Assuming that the only types allowed are char, int, float (no arrays, no pointers, etc.),
write a grammar for function headers, i.e., the portion char fun(int a, . . .) in the above
example.
(c) Consider the floating point number representation in the C programming language. Give
a regular expression for it using the following convention: l denotes a letter, d denotes
a digit, S denotes sign and P denotes point. State any assumption that you may need to
make.
C2. Recall that a semaphore S is an integer variable that can be accessed only through two
operations, wait(S ) and signal (S ) which behave as follows:
wait(S) { signal(S)
while (S <= 0) {
/* do nothing */ ; S++;
S--; }
}
– two processes should never concurrently execute the two statements in the body of the
wait function.
Show how you would implement the wait and signal functions without using any special
hardware instructions (atomic test-and-set, interrupt disabling, etc.). You may assume, how-
ever, that (i) a variable declared as shared (e.g. shared int x = 0;) is available to a
set of co-operating processes; (ii) basic machine instructions (load, store, test) are executed
atomically; and (iii) each semaphore will be used by exactly two processes for synchroniza-
tion.
C3. (a) A relation R(A, B, C, D) has to be accessed under the query σB=10 (R). Out of the
following possible file structures, which one should be chosen and why?
i. R is a heap file.
ii. R has a clustered hash index on B.
iii. R has an unclustered B + tree index on (A, B).
(b) If the query is modified as πA,B (σB=10 (R)), which one of the three possible file struc-
tures given above should be chosen in this case and why?
(c) Let the relation have 5000 tuples with 10 tuples/page. In case of a hashed file, each
bucket needs 10 pages. In case of B + tree, the index structure itself needs 2 pages. If
it takes 25 msecs to read or write a disk page, what would be the disk access time for
answering the above queries?
(d) Relation R(A,B,C) supports the following functional dependencies:
A → B, B → C and C → A.
i. Identify the key attributes.
ii. Explain whether R is in BCNF.
iii. If R is not in BCNF, decompose to create a set of normalized relations satisfying
BCNF.
iv. If R does not support the functional dependencies B → C, but the other two are
maintained, would R be in BCNF? If not, decompose R to normalized relations
satisfying BCNF.
C4. Let A and B be two arrays, each of size n. A and B contain numbers in sorted order. Give
an O(logn) algorithm to find the median of the combined set of 2n numbers.
C5. (a) Consider a pipelined processor with m stages. The processing time at every stage is the
same. What is the speed-up achieved by the pipelining?
(b) In a certain computer system with cache memory, 750 ns (nanosec) is the access time
for main memory for a cache miss and 50 ns is the access time for a cache hit. Find the
percentage decrease in the effective access time if the hit ratio is increased from 80% to
90%.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and 1000 cylinders. The speed
of rotation of the disk is 6000 rpm. The average seek time is 10 millisecs. A file of size
50 MB is written from the beginning of a cylinder and a new cylinder will be allocated
only after the first cylinder is totally occupied.
i. Find the maximum transfer rate.
ii. How much time will be required to transfer the file of 50 MB written on the disk?
Ignore the rotational delay but not the seek time.
(b) Consider a 4-way traffic crossing as shown in Figure 1. Suppose that we model the
crossing as follows:
– each vehicle is modeled by a process,
18
– the crossing is modeled as a shared data structure. Assume that the vehicles can only
move straight through the intersection (no left or right turns). Using read-write locks
(or any standard synchronization primitive), you have to devise a synchronization
scheme for the processes. Your scheme should satisfy the following criteria:
i. prevent collisions,
ii. prevent deadlock, and
iii. maximize concurrency but prevent indefinite waiting (starvation).
Write down the algorithm that each vehicle must follow in order to pass through the
crossing. Justify that your algorithm satisfies the given criteria.
C7. (a) A computer on a 6 Mbps network is regulated by a token bucket. The bucket is filled
at a rate of 2 Mbps. It is initially filled to capacity with 8 Megabits. How long can the
computer transmit at the full 6 Mbps?
(b) Sketch the Manchester encoding for the bit stream 0001110101.
(c) If delays are recorded in 8-bit numbers in a 50-router network, and delay vectors are
exchanged twice a second, how much bandwidth per (full-duplex) line is consumed by
the distributed routing algorithm? Assume that each router has 3 lines to other routers.
(d) Consider three IP networks X, Y, and Z. Host HX in the network X sends messages,
each containing 180 bytes of application data, to a host HZ in network Z. The TCP layer
prefixes a 20 byte header to the message. This passes through an intermediate network
Y. The maximum packet size, including 20 byte IP header, in each network is X: 1000
bytes, Y: 100 bytes, and Z: 1000 bytes. The networks X and Y are connected through a
1 Mbps link, while Y and Z are connected by a 512 Kbps link.
i. Assuming that the packets are correctly delivered, how many bytes, including head-
ers, are delivered to the IP layer at the destination for one application message?
Consider only data packets.
ii. What is the rate at which application data is transferred to host HZ ? Ignore errors,
acknowledgments, and other overheads.
C8. Consider a binary operation shuffle on two strings, that is just like shuffling a deck of cards.
For example, the operation shuffle on strings ab and cd, denoted by ab k cd, gives the set of
strings {abcd, acbd, acdb, cabd, cadb, cdab}.
(a) Define formally by induction the shuffle operation on any two strings x, y ∈ Σ ? .
(b) Let the shuffle of two languages A and B, denoted by A k B be the set of all strings
obtained by shuffling a string x ∈ A with a string y ∈ B. Show that if A and B are
regular, then so is A k B.
19
C9. (a) Give a method of encoding the microinstructions (given in the table below) so that the
minimum number of control bits are used and maximum parallelism among the microin-
structions is achieved.
Microinstructions Control Signals
I1 C1 , C2 , C3 , C4 , C5 , C6
I2 C1 , C3 , C4 , C6
I3 C2 , C5 , C6
I4 C4 , C5 , C8
I5 C7 , C8
I6 C1 , C8 , C9
I7 C3 , C4 , C8
I8 C1 , C2 , C9
(b) A certain four-input gate G realizes the switching function G(a, b, c, d) = abc + bcd.
Assuming that the input variables are available in both complemented and uncomple-
mented forms:
i. Show a realization of the function
f(u, v, w, x) = Σ (0, 1, 6, 9, 10, 11, 14, 15)
with only three G gates and one OR gate.
ii. Can all switching functions be realized with {G, OR} logic set?
C10. (a) You are given a relation EMPLOYEES(NAME, DEPT, SALARY). Express the following
query in relational algebra:
Find the names of the employee(s) with the highest salary.
You may use only the operators union, intersection, difference, selection, projection,
product, join and renaming.
(b) A relation R(A, B, C) may have multiple keys.
i. If you are told that A is not a key for R(A, B, C), determine the largest set of
distinct keys that R can have.
NOTE : If both B and C are keys of R, then ABC cannot be a key of R.
ii. Construct an instance of R for which the set of keys is the set obtained in (i).
iii. Generalize your answer to (i) when the given relation is
R(A1 , A2 , . . . , An ).
C11. Consider a 100mbps token ring network with 10 stations having a ring latency of 50 µs (the
time taken by a token to make one complete rotation around the network when none of the
stations are active). A station is allowed to transmit data when it receives the token, and it
releases the token immediately after transmission. The maximum allowed holding time for
a token (THT) is 200 µs.
(a) Express the maximum efficiency of this network when only a single station is active in
the network
(b) Find an upper bound on the token rotation time when all stations are active
(c) Calculate the maximum throughput rate that one host can achieve in the network.
a+b↑c+d*e
C13. A tape S contains n records, each representing a vote in an election. Each candidate for the
election has a unique id. A vote for a candidate is recorded as his/her id.
(a) Write an O(n) time algorithm to find the candidate who wins the election. Comment on
the main memory space required by your algorithm.
(b) If the number of candidates k is known apriori, can you improve your algorithm to
reduce the time and/or space complexity?
(c) If the number of candidates k is unknown, modify your algorithm so that it uses only
O(k) space. What is the time complexity of your modified algorithm?
C14. (a) Let L = {w ∈ {a, b, c}∗ : w contains the pattern aba}. For example, the string cbabaca ∈
L, while the string abbcb ∈
/ L. Draw the state diagram of a deterministic finite automaton
(DFA) which accepts L.
(b) Some websites require you to choose a strong password when you register. A password
is any non-empty sequence of letters, digits, and special characters (one of !, @, #, $, %,
&, +). Define a strong password as one that contains at least one digit and at least one
special character. Write a regular expression for strong passwords.
C15. You are given a set P = {p1 , p2 , . . . , pn } of points, and a set I = {I1 , I2 , . . . , Im } of inter-
vals on the x-axis. Each interval is
represented by its left end-point and right end-point. Thus, for i = 1, 2, . . . , m, Ii is stored
as [ai , bi ], where ai and bi are also points on the x-axis (but not necessarily members of P ).
(a) Design an efficient algorithm to test whether each interval in I contains at least one
point of P . You must explain the data structures used in your algorithm. Analyze the
time complexity of your algorithm.
(b) Design an efficient algorithm to identify a point in P that is contained in the maximum
number of intervals. Analyze its time complexity.
C16. You have to write two functions add and multiply in C for adding and multiplying
two arbitrarily large, positive integers nx and ny . Assume that nx and ny are stored as the
strings x and y, which contain the decimal representations of nx and ny , respectively. The
functions add and multiply should return strings containing the decimal representations
of nx + ny and nx × ny , respectively. For example, add("11","23") should return the
string "34", and multiply("12","15") should return the string "180".
Note that nx and ny may be larger than the largest integer that can be stored in a variable of
type int or long.
(a) Write algorithms (in plain English) for adding and multiplying nx and ny .
(b) Implement your algorithms in C following the prototypes given below:
char *add(char *x, char *y);
char *multiply(char *x, char *y);
NOTE : You may use the add function when implementing the
multiply function.
E1. (a) A long shunt D.C. generator supplies power to 55 lamps of rating 200 W, 220 V at 88%
overall efficiency. The shunt and series field resistance and the armature resistance are
110 Ω , 0.06 Ω and 0.04 Ω respectively. Calculate
21
E3. An alternator on open-circuit generates 360 V at 60 Hz when the field current is 3.6 A.
Neglecting saturation, determine the open-circuit e.m.f. when the frequency is 40 Hz and
the field-current is 24 A.
E4. (a) In the circuit shown below, the output VS1 of an op-amp (O1 ) is connected to the invert-
ing terminal of another op-amp (O2 ) through resistance R. O1 changes gain depending
on the polarity of VS .
Find the output voltage V0 for (i) VS = 1 V, and (ii) VS = −1 V.
Assume that the diode D2 is ideal, R1 = 2 KΩ , R2 = 8 KΩ , R3 = 8 KΩ , R = 2 KΩ
and VS2 = 0.5 V.
R3
R2 D2 R1
R1
− VS1 R V1
VS +
−
+ V0
O1 VS2 R V2 O2
R1
(b) In an n-p-n transistor, 108 holes/µs move from the base to the emitter region, while
1010 electrons/µs move from the emitter to the base region. An ammeter reads the base
current as 16 µA. Determine the emitter current and the collector current. Each hole
carries a charge of 1.602 × 10−19 C.
E5. (a) Calculate the bias resistances for the cascode amplifier shown in the figure below, such
that VA = 10 V after accounting for the voltage drop across RB1 . It is given that VCC =
20 V, IE1 = IE2 = 1 mA, β1 = β2 = 100, RL = 4.7 KΩ . The bias voltage for the
common emitter stage is VB2 = 1.5 V. Further, VB1 = 11.5 V, and the constant emitter
to base voltage is ≈ 0.7 V.
22
V0
RB1
Q1
+
VB1 RL
−
VA
+
VCC
Vi Q2 −
RB2
+ −
VB2
(b) In the monostable multivibrator circuit shown in the figure below, VSS = 10 V, C =
0.01 µF, R = 10 KΩ . Further, assume that the transition voltage VT is 5 V, the output
resistance R01 of gate G1 is 500 Ω , and the internal resistance of the NOR gate is 1 KΩ .
If a short positive trigger pulse is applied at Vi , find
(i) the initial drop ∆ in V1o and V2i ;
(ii) the value of voltage V1o at the end of the quasi-stable state;
(iii) the duration T of the quasi-stable state.
VSS
I1 C
Vi V1o V2o
G1 G2
V2i
I2
E6. If the inputs A and B to the circuit shown below can be either 0 volt or 5 volts,
(i) what would be the corresponding voltages at output Z, and
(ii) what operation is being performed by this circuit ?
Assume that the transistor and the diodes are ideal and base to emitter saturation voltage =
0.5 volts.
23
E7. The hybrid parameters of a p-n-p junction transistor used as an amplifier in the common-
emitter configuration are: hie = 800 Ω, hf e = 46, hoe = 8 × 10−5 mho, hre = 55.4 × 10−4 .
If the load resistance is 5 kΩ and the effective source resistance is 500 Ω , calculate the
voltage and current gains and the output resistance.
E8. Derive the equivalent lattice network corresponding to the bridged T network shown in the
figure.
E9. Derive the open-circuit transfer impedance of the lattice shown in the figure below and deter-
mine the condition for having no zeros in the right-half plane, i.e., for positive frequencies.
E10. (a) Using the minimum number of flip-flops, design a special purpose counter to provide
the following sequence:
0110, 1100, 0011, 1001
(b) Find the currents I1 and I2 in the following circuit.
24
E11. A hypothetical four-input Boolean T -gate is defined by the Karnaugh map given below.
ab
cd 00 01 11 10
00 1 0 0 1
01 0 0 0 0
11 0 0 0 0
10 1 0 0 1
E12. a A uniform thin bar of mass M is supported by two rapidly rotating rollers whose axes
are separated by a fixed distance a. The bar is initially placed at rest asymmetrically, as
shown in the figure below. C denotes the centre of the bar.
x C
(i) If the rollers rotate in opposite directions as shown in the figure, derive the equation
of motion of the bar and solve for x(t), where x(t) is the displacement of C from
the left roller at time t. Assume x(0) = x0 , ẋ(0) = 0, and the coefficient of kinetic
friction between the bar and the rollers to be µ.
(ii) If the directions of rotation of the rollers are reversed, calculate the displacement
x(t). Again assume x(0) = x0 and ẋ(0) = 0.
25
E15. Find the acceleration of the block of mass M in the situation shown below. The coefficient
of friction between the blocks is µ1 and that between the bigger block and the ground is µ2.
E16. A flywheel of mass 100 kg and radius of gyration 20 cm is mounted on a light horizontal
axle of radius 2 cm, and is free to rotate on bearings whose friction may be neglected. A
light string wound on the axle carries at its free end a mass of 5 kg. The system is released
from rest with the 5 kg mass hanging freely. If the string slips off the axle after the weight
has descended 2 m, prove that a couple of moment 10/π 2 kg.wt.cm. must be applied in
order to bring the flywheel to rest in 5 revolutions.
E17. The truss shown in the figure rotates around the pivot O in a vertical plane at a constant
angular speed w. Four equal masses (m) hang from the points B, C, D and E. The members
of the truss are rigid, weightless and of equal length. Find a condition on the angular speed
w so that there is compression in the member OE.
26
E18. Two bulbs of 500 cc capacity are connected by a tube of length 20 cm and internal radius
0.15 cm. The whole system is filled with oxygen, the initial pressures in the bulbs before
connection being 10 cm and 15 cm of Hg, respectively. Calculate the time taken for the
pressures to become 12 cm and 13 cm of Hg, respectively. Assume that the coefficient of
viscosity h of oxygen is 0.000199 cgs unit.
E19. A vertical hollow cylinder contains an ideal gas with a 5 kg piston placed over it. The cross-
section of the cylinder is 5 × 10−3 m2 . The gas is heated from 300 K to 350 K and the
piston rises by 0.1 m. The piston is now clamped in this position and the gas is cooled back
to 300 K. Find the difference between the heat energy added during heating and that released
during cooling.
(1 atmospheric pressure= 105 N m−2 and g = 10ms−2 .)
E20. (a) A system receives 10 Kcal of heat from a reservoir to do 15 Kcal of work. How much
work must the system do to reach the initial state by an adiabatic process?
(b) A certain volume of Helium at 15C is suddenly expanded to 8 times its volume. Calcu-
late the change in temperature (assume that the ratio of specific heats is 5/3).
E21. A spherical charge distribution has a volume density ρ, which is a function of r, the radial
distance
½ from the center of the sphere, as given below.
A/r, A is constant for 0 ≤ r ≤ R
ρ=
0, for r > R
Determine the electric field as a function of r, for r≥ R. Also deduce the expression for the
electrostatic potential energy U(r), given that U (∞) = 0 in the region r ≥ R.
E22. A proton of velocity 107 m/s is projected at right angles to a uniform magnetic induction
field of 0.1w/m2 . How much is the path of the particle deflected from a straight line after it
has traversed a distance of 1 cm? How long does it take for the proton to traverse a 90◦ arc?
E23. A circular disc of radius 10 cm is rotated about its own axis in a uniform magnetic field of
100 weber/m2 , the magnetic field being perpendicular to the plane of the disc. Will there be
any voltage developed across the disc? If so, then find the magnitude of this voltage when
the speed of rotation of the disc is 1200 rpm.
E24 Write a C program to generate a sequence of positive integers between 1 and N, such that
each of them has only 2 or/and 3 as prime factors. For example, the first seven elements of
the sequence are: 2, 3, 4, 6, 8, 9, 12. Justify the steps of your algorithm.
27
E25. Let Ii = [ai , bi ] denote a closed interval on the x-axis, where ai and bi are respectively
the x-coordinates of the left and right end-points of Ii . A program takes as input a set of n
intervals {Ii , I2 , . . . , In } (not necessarily disjoint), sorted according to their left end-points.
The program has to report the union of Ii ’s as a set of disjoint intervals, as explained in the
following example:
a3 b3 a5 b5
a7 b7
a1 b1 a4 b4
a2 b2 a6 b6 a8 b8
Here, the input is {[a1 , b1 ], [a2 , b2 ], [a3 , b3 ], [a4 , b4 ], [a5 , b5 ], [a6 , b6 ], [a7 , b7 ], [a8 , b8 ]}. The
required output is {[a1 , b2 ], [a4 , b4 ], [a7 , b8 ]}.
(a) Describe your method for solving this problem using a flow-chart or pseudo-code or in
plain English.
(b) Write a program in C for your method.
Test Code: CS (Short answer type) 2008
The candidates for M.Tech. in Computer Science will have to take two
tests – Test MIII (objective type) in the forenoon session and Test CS
(short answer type) in the afternoon session. The CS test booklet will have
two groups as follows.
GROUP A
A test for all candidates in analytical ability and mathematics at the B.Sc.
(pass) level, carrying 30 marks.
GROUP B
The syllabi and sample questions for the CS test are given below.
Note: Not all questions in the sample set are of equal difficulty. They
may not carry equal marks in the test.
Syllabus
GROUP A
1
GROUP B
Mathematics
(B.Sc. Hons. level)
Statistics
(B.Sc. Hons. level)
2
Descriptive statistical measures, product-moment correlation, partial and
multiple correlation; regression (simple and multiple); elementary theory
and methods of estimation (unbiasedness, minimum variance, sufficiency,
maximum likelihood method, method of moments, least squares methods).
Tests of hypotheses (basic concepts and simple applications of Neyman-
Pearson Lemma). Confidence intervals. Tests of regression. Elements of
non-parametric inference. Contingency tables and Chi-square, ANOVA,
basic designs (CRD/RBD/LSD) and their analyses. Elements of factorial
designs. Conventional sampling techniques, ratio and regression methods
of estimation.
Physics
(B.Sc. Hons. level)
3
Hydrogen atom spectrum, electron spin, spin–orbit coupling, fine
structure, Zeeman effect, lasers.
Condensed matter physics – crystal classes, 2D and 3D lattice, reciprocal
lattice, bonding, diffraction and structure factor, point defects and
dislocations, lattice vibration, free electron theory, electron motion in
periodic potential, energy bands in metals, insulators and semiconductors,
Hall effect, thermoelectric power, electron transport in semiconductors,
dielectrics, Claussius Mossotti equation, Piezo, pyro and ferro electricity.
Nuclear and particle physics – Basics of nuclear properties, nuclear forces,
nuclear structures, nuclear reactions, interaction of charged particles and
e-m rays with matter, theoretical understanding of radioactive decay,
particle physics at the elementary level.
Computer Science
(B.Tech. level)
Data structures - array, stack, queue, linked list, binary tree, heap, AVL
tree, B-tree.
Programming languages - Fundamental concepts – abstract data types,
procedure call and parameter passing, languages like C and C++.
Design and analysis of algorithms - Sorting, selection, searching.
Computer organization and architecture - Number representation,
computer arithmetic, memory organization, I/O organization,
microprogramming, pipelining, instruction level parallelism.
Operating systems - Memory management, processor management,
critical section problem, deadlocks, device management, file systems.
Formal languages and automata theory - Finite automata and regular
expressions, pushdown automata, context-free grammars, Turing
machines, elements of undecidability.
Principles of Compiler Construction - Lexical analyzer, parser, code
optimization, symbol table.
Database management systems - Relational model, relational algebra,
relational calculus, functional dependency, normalization (up to 3rd
normal form).
Computer networks - OSI, TCP/IP protocol; internetworking; LAN
technology - Bus/tree, Ring, Star; MAC protocols; WAN technology -
circuit switching, packet switching; data communications - data encoding,
routing, flow control, error detection/correction.
4
Switching Theory and Logic Design - Boolean algebra, minimization of
Boolean functions, combinational and sequential circuits – synthesis and
design.
5
Sample Questions
GROUP A
Mathematics
A1. If 1, a1, a2,…, an-1 are the n roots of unity, find the value of
(1 - a1) (1 - a2)…(1 - an-1).
A2. Let
S {( a1 , a2 , a3 , a4 ) : ai , i 1, 2, 3, 4 and a1 a2 a3 a4 0}
and
{( a1 , a2 , a3 , a4 ) : ai , i 1, 2, 3, 4 and a1 a2 a3 a4 0}.
Find a basis for S .
c0 c1 c2 c3
c 2 c3 c0 c1
c c c1 c0
3 2
c c c3 c2
1 0
where c 1 3 , c 3 3 , c 3 3 , and c 1 3 .
0 1 2 3
4 2 4 2 4 2 4 2
(Hint: What is c 0 c1 c 2 c3 ?)
2 2 2 2
A4. For any real number x and for any positive integer n show that
x x 1 x 2 x n 1 nx
n n n
where [a] denotes the largest integer less than or equal to a.
6
Show that the sequence converges and find its limit.
A8. Find the total number of English words (all of which may not have
proper English meaning) of length 10, where all ten letters in a word
are not distinct.
a1 a 2 a
A9. Let a0 + ..... n 0, where ai’s are some real constants.
2 3 n 1
Prove that the equation a 0 a 1 x a 2 x 2 ... a n x n 0 has at least one
solution in the interval (0, 1).
A10. Let (n) be the number of positive integers less than n and having no
common factor with n. For example, for n = 8, the numbers 1, 3, 5, 7
have no common factors with 8, and hence (8) = 4. Show that
(i) ( p ) p 1 ,
(ii) ( pq ) ( p ) ( q) , where p and q are prime numbers.
A11. A set S contains integers 1 and 2. S also contains all integers of the
form 3x+ y where x and y are distinct elements of S, and every
element of S other than 1 and 2 can be obtained as above. What is S?
Justify your answer.
A12. Let f be a real-valued function such that f(x+y) = f(x) + f(y) x, y
R. Define a function by (x) = c + f(x), x R, where c is a
real constant. Show that for every positive integer n,
n ( x ) (c f c f 2 (c) ..... f n 1 (c)) f n ( x );
A13. Consider a square grazing field with each side of length 8 metres.
There is a pillar at the centre of the field (i.e. at the intersection of
the two diagonals). A cow is tied to the pillar using a rope of length
8
3 metres. Find the area of the part of the field that the cow is
allowed to graze.
7
A14. Let f : [0,1] [-1,1] be such that f(0) = 0 and f(x) = sin 1x for x > 0.
Is it possible to get three sequences {an}, {bn}, {cn} satisfying all the
three properties P1, P2 and P3 stated below? If so, provide an
example sequence for each of the three sequences. Otherwise, prove
that it is impossible to get three such sequences.
is divisible by 11.
GROUP B
Mathematics
x n 3
M1. Let 0 < x1 < 1. If xn+1 = , n = 1,2,3, …
3x n 1
5x n 3
(i) Show that xn+2 = , n = 1,2,3, …
3x n 5
(ii) Hence or otherwise, show that nlim
xn exists.
8
Show that f (x) vanishes at infinitely many points in (0,1).
Find nlim
Pn .
M6. (a) Let A, B and C be 1n, nn and n1 matrices respectively. Prove
or disprove: Rank(ABC) Rank(AC).
(b) Let S be the subspace of R4 defined by
S = {(a1, a2, a3, a4) : 5a1 - 2a3 -3a4 = 0}.
Find a basis for S.
9
(a) How many 5-element multi-subsets of a 10-element set are possi-
ble?
(b) Generalize your result to m-element multi-subsets of an n-ele-
ment set (m < n).
M10. Let R be the field of reals. Let R[x] be the ring of polynomials over
R, with the usual operations.
(a) Let I R[x] be the set of polynomials of the form a0 +a1x +....
+ anxn with a0 = a1 = 0. Show that I is an ideal.
(b) Let P be the set of polynomials over R of degree 1. Define
and on P by (a0 +a1x) (b0 +b1 x) = (a0 + b0)+(a1 +b1)x and
(a0 +a1x) (b0 + b1x) = a0b0 + (a1b0 +a0b1)x. Show that (P, ,
) is a commutative ring. Is it an integral domain? Justify your
answer.
M11. (a) If G is a group of order 24 and H is a subgroup of G of order 12,
prove that H is a normal subgroup of G.
(b) Show that a field of order 81 cannot have a subfield of order 27.
10
M14. (a) Show that a tree on n vertices has at most n2 vertices with
degree > 1.
(b) Show that in an Eulerian graph on 6 vertices, a subset of 5
vertices cannot form a complete subgraph.
M15. a) Show that the edges of K4 can be partitioned into 2 edge-disjoint
spanning trees.
(b) Use (a) to show that the edges of K6 can be partitioned into 3
edge-disjoint spanning trees.
(c) Let Kn denote the complete undirected graph with n vertices and
let n be an even number. Prove that the edges of Kn can be
partitioned into exactly n/2 edge-disjoint spanning trees.
Statistics
S1. (a) X and Y are two independent and identically distributed random
variables with Prob[X = i] = pi, for i = 0, 1, 2, ……… Find
Prob[X < Y] in terms of the pi values.
(b) Based on one random observation X from N(0, 2), show that
/2 |X| is an unbiased estimate of .
S2. (a) Let X0, X1, X2, … be independent and identically distributed random
variables with common probability density function f. A random
variable N is defined as
N n if X1 X 0 , X 2 X 0 , , X n1 X 0 , X n X 0 , n 1, 2, 3,
S3. If a die is rolled m times and you had to bet on a particular number of
sixes occurring, which number would you choose? Is there always
one best bet, or could there be more than one?
11
likelihood estimate of based on observations x1 , x2 , x3 on
X 1 , X 2 , X 3 respectively. Is it unbiased? Find the variance of the
estimate.
S5. New laser altimeters can measure elevation to within a few inches,
without bias. As a part of an experiment, 25 readings were made on
the elevation of a mountain peak. These averaged out to be 73,631
inches with a standard deviation (SD) of 10 inches. Examine each of
the following statements and ascertain whether the statement is true
or false, giving reasons for your answer.
(a) 73631 4 inches is a 95% confidence interval for the elevation
of the mountain peak.
(b) About 95% of the readings are in the range 73631 4 inches.
(c) There is about 95% chance that the next reading will be in the
range of 73631 4 inches.
S6. Consider a randomized block design with two blocks and two
treatments A and B. The following table gives the yields:
Treatment A Treatment B
Block 1 a b
Block 2 c d
12
combinations of X1, X2, X3, X4 such that they are also independently
and identically distributed.
(b) Let X be a continuous random variable such that X and -X are
identically distributed. Show that the density function of X is
symmetric.
S9. Let t1, t2,…,tk be k independent and unbiased estimators of the same
k
ti
parameter with variances 1 , 2 , k . Define t as . Find E(
2 2 2
i 1 k
k
of c.
13
S12. Let X1, X2,…,Xn (Xi= (xi1, xi2, …, xip), i=1, 2, …, n) be n random
samples from a p-variate normal population with mean vector and
covariance matrix I.
1 n
xj xij ,1 j p.
n i 1
Obtain the distribution of ' S where k , 0.
4
S13. Let Yi j X ij i , i 1,2,, k ,
j 1
where Yi’s and X’ijs are known, and i’s are independent and each i
follows N(0,2).
S14. For the following sampling scheme, compute the first and second
order inclusion probabilities:
From a group of 15 male and 10 female students, one male and one
female students are selected using SRS. After these selections, from
the remaining 23 students, two are chosen using SRSWR, thus
selecting a sample of size 4.
14
Physics
(b) The nucleus BZA decays by alpha ( He24 ) emission with a half-life
T to the nucleus C ZA24 which in turn, decays by beta (electron)
T
emission with a half-life to the nucleus DZA14 . If at time t 0 ,
4
the decay chain B C D had started with B0 number of B
nuclei only, then find out the time t at which the number of C
nuclei will be maximum.
P2. (a) Consider a material that has two solid phases, a metallic phase
and an insulator phase. The phase transition takes place at the
temperature T0 which is well below the Debye temperature for ei-
ther phase. The high temperature phase is metastable all the way
down to T = 0 and the speed of sound, cs, is the same for each
phase. The contribution to the heat capacity coming from the free
electrons to the metal is
k
C e=e V T , =3 2
4T F
15
(i) Find out the probability that the electrons will be between the
shells. Assume the wave function for the ground state of the
hydrogen atom as
−r
1 a
= e cost
o
a0
3
(ii) If the wave function for the ground state of the hydrogen
atom is given by
−r
1 a
= eo
a03
P3. p1 and p 2 are two relativistic protons traveling along a straight line in
n 14n
the same direction with kinetic energies , and fractions
n 1 14n 1
of their respective total energies. Upon entering a region where a
uniform magnetic field B acts perpendicularly on both, p1 and p 2
describe circular paths of radii r1 and r2 respectively. Determine the
r1
ratio . What is the value of when n 5 ?
r2
16
(b) The Hamiltonian of a mechanical system having two degrees of
freedom is:
1 1
H(x, y; px, py) = (px2 + py2) + m 2(x2 + y2),
2m 2
where m and are constants; x, y are the generalized co-ordinates
for which px, py are the respective conjugate momenta. Show that
the expressions (x py -y px)n, n=1,2,3,… are constants of motion
for this system.
P5. (a) A particle describes the curve rn = acosnθ under a force P towards
the pole, r, θ being the polar coordinates. Find the law of force.
(b) Two particles, each with speed v, move in a plane making an
angle 2θ with each other as seen from the laboratory frame.
Calculate the relative speed (under the formalism of special
relativity) of one with respect to the other.
17
P8. (a) Given the circuit shown in the figure, find out the current through
the resistance R 3 between A and B .
(b) Suppose a metal ring of mean radius 100 cm is made of iron and
steel as shown in the figure. The cross-section of the ring is 10
sq.cm. If the ring is uniformly wound with 1000 turns, calculate
the current required to produce a flux of 1 milliweber. The abso-
lute permeability of air is 4 10 7 H/m and relative permeabili-
ty of iron and steel are 250 and 1000 , respectively.
18
300K, and the magnitude of the electronic charge is 1.6 10-19
Coulomb.
P10. Two heavy bodies A and B , each having charge Q , are kept
rigidly fixed at a distance 2a apart. A small particle C of mass m
and charge q ( Q ), is placed at the midpoint of the straight
line joining the centers of A and B . C is now displaced slightly
along a direction perpendicular to the line joining A and B , and
then released. Find the period of the resultant oscillatory motion of
C , assuming its displacement y a .
If instead, C is slightly displaced towards A , then find the instan-
a
taneous velocity of C , when the distance between A and C is .
2
P12. Consider the following truth table where A, B and C are Boolean
inputs and T is the Boolean output.
A B C T
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
19
Express T in a product-of-sum form and hence, show how T can be
implemented using NOR gates only.
P13. (a) Find the relationship between L, C and R in the circuit shown in
the figure such that the impedance of the circuit is independent
of frequency. Find out the impedance.
(b) Find the value of R and the current flowing through R shown in
the figure when the current is zero through R.
B
P14. A gas obeys the equation of state P where B is a
V V2
function of temperature only. The gas is initially at temperature
and volume V0 and is expanded isothermally and reversibly to
volume V1 2V0 .
(a) Find the work done in the expansion.
(b) Find the heat absorbed in the expansion.
20
S P
(Hint: Use the relation where the symbols have
V V
their usual meaning.)
P15. (a) From the Earth, an observer sees two very high speed rockets
A and B moving in a straight line in the same direction with
c 2c
velocities and respectively. What is the velocity of B
2 3
relative to A? Here, c denotes the speed of light in vacuum.
(b) Two objects having rest masses m1 and m2 move with
relativistic speeds. Their total energies are E1 and E2 and
kinetic energies are K1 and K2 respectively. If 2m2E1=5m1E2
and K1 is only 5% less than E1, find the value of K2 in terms of
E2.
Computer Science
A → Bb A→a
B →Cc B→b
C → Aa C→c
21
char fun (int a, float b, int c)
{ /* body */ … }
Assuming that the only types allowed are char, int, float
(no arrays, no pointers, etc.), write a grammar for function
headers, i.e., the portion char fun(int a, …) in the
above example.
22
(b) If the query is modified as A,B(B=10(R)), which one of the three
possible file structures given above should be chosen in this
case and why?
(c) Let the relation have 5000 tuples with 10 tuples/page. In case of
a hashed file, each bucket needs 10 pages. In case of B+ tree,
the index structure itself needs 2 pages. If it takes 25 msecs. to
read or write a disk page, what would be the disk access time
for answering the above queries?
C4. Let A and B be two arrays, each of size n. A and B contain num-
bers in sorted order. Give an O(log n) algorithm to find the medi-
an of the combined set of 2n numbers.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and
1000 cylinders. The speed of rotation of the disk is 6000 rpm.
The average seek time is 10 millisecs. A file of size 50 MB is
written from the beginning of a cylinder and a new cylinder
will be allocated only after the first cylinder is totally occupied.
i) Find the maximum transfer rate.
ii) How much time will be required to transfer the file of 50
MB written on the disk? Ignore the rotational delay but not
the seek time.
23
Suppose that we model the crossing as follows:
- each vehicle is modeled by a process,
- the crossing is modeled as a shared data structure. Assume that
the vehicles can only move straight through the intersection (no
left or right turns). Using read-write locks (or any standard
synchronization primitive), you have to device a
synchronization scheme for the processes. Your scheme should
satisfy the following criteria:
i) prevent collisions,
ii) prevent deadlock, and
iii) maximize concurrency but prevent indefinite waiting
(starvation).
Write down the algorithm that each vehicle must follow in order
to pass through the crossing. Justify that your algorithm satisfies
the given criteria.
C8. Consider a binary operation shuffle on two strings, that is just like
shuffling a deck of cards. For example, the operation shuffle on
strings ab and cd, denoted by ab || cd, gives the set of strings
{abcd, acbd, acdb, cabd, cadb, cdab}.
24
used and maximum parallelism among the microinstructions
is achieved.
25
compute the average number of cycles per instruction (CPI),
total execution time for this program, and the corresponding
MIPS rate.
(b) If we now use an optimizing compiler which reduces the total
number of ALU/register transfer instructions by a factor of 2,
keeping the number of other instruction types unchanged, then
compute the average CPI, total time of execution and the
corresponding MIPS rate for this modified program.
C13. (a) The order of a regular language L is the smallest integer k for
which Lk = Lk+1, if there exists such a k, and otherwise.
(i) What is the order of the regular language a + (aa)(aaa)*?
(ii) Show that the order of L is finite if and only if there is an
integer k such that Lk = L*, and that in this case the order of L
is the smallest k such that Lk = L*.
C14. (a) You are given an unordered sequence of n integers with many
duplications, such that the number of distinct integers in the
sequence is O(log n). Design a sorting algorithm and its
necessary data structure(s), which can sort the sequence using
at most O(n log(log n)) time. (You have to justify the time
complexity of your proposed algorithm.)
26
(b) Let A be a real-valued matrix of order n x n already stored in
memory. Its (i, j)-th element is denoted by a[i, j]. The
elements of the matrix A satisfy the following property:
Let the largest element in row i occur in column li. Now, for
any two rows i1, i2, if i1 < i2, then li1 ≤ li2 .
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12
(a)
Row l(i)
I
1 2
2 3
3 3
4 4
5 5
(b)
#include <stdio.h>
#define SQR(x) (x*x)
#define ADD1(x) (x=x+1)
#define BeginProgram int main(int ac,char *av[]){
#define EndProgram return 1; }
For each of the following code fragments, what will be the output?
27
(i) #include "abc.h"
main()
{ int y = 4; printf("%d\n", SQR(y+1)); }
(ii) #include "abc.h"
BeginProgram
int y=3; printf("%d\n", SQR(ADD1(y)));
EndProgram
E3. A chain of total length L = 4 metres rests on a table top, with a part
of the chain hanging over the edge, as shown in the figure below.
Let be the ratio of the length of the overhanging part of the chain
to L.
28
If the coefficient of friction between the chain and the table top is
0.5, find the values of for which the chain remains stationary. If
= 0.5, what is the velocity of the chain when the last link leaves the
table?
E5. The truss shown in the figure rotates around the pivot O in a vertical
plane at a constant angular speed . Four equal masses (m) hang from
the points B, C, D and E. The members of the truss are rigid,
weightless and of equal length. Find a condition on the angular speed
so that there is compression in the member OE.
E6. If the inputs A and B to the circuit shown below can be either 0 volt
or 5 volts,
(i) what would be the corresponding voltages at output Z, and
(ii) what operation is being performed by this circuit ?
Assume that the transistor and the diodes are ideal and base to
emitter saturation voltage = 0.5 volts.
29
E7. Two bulbs of 500 cc capacity are connected by a tube of length 20 cm
and internal radius 0.15 cm. The whole system is filled with oxygen,
the initial pressures in the bulbs before connection being 10 cm and
15 cm of Hg, respectively. Calculate the time taken for the pressures
to become 12 cm and 13 cm of Hg, respectively. Assume that the
coefficient of viscosity of oxygen is 0.000199 cgs unit.
300 3.6
E8. (a) Ice in a cold storage melts at a rate of kg/hour when the
80 4.2
external temperature is 27oC. Find the minimum power output of
the refrigerator motor, which just prevents the ice from melting.
(Latent heat of fusion of ice = 80 cal/gm.)
30
E10. A spherical charge distribution has a volume density , which is a
function of r, the radial distance from the center of the sphere, as
given below.
A / r , A is constant for 0 r R
=
0, for r R
Determine the electric field as a function of r, for r R. Also deduce
the expression for the electrostatic potential energy U(r), given that
U(∞) = 0 in the region r R.
E13. (a) State the two necessary conditions under which a feedback
amplifier circuit becomes an oscillator.
(b) A two-stage FET phase shift oscillator is shown in the diagram
below.
31
(ii) Find the frequency of oscillation.
(iii) Establish that the gain A must exceed 3.
E14. A circular disc of radius 10cm is rotated about its own axis in a
uniform magnetic field of 100 weber/m2, the magnetic field being
perpendicular to the plane of the disc. Will there be any voltage
developed across the disc? If so, then find the magnitude of this
voltage when the speed of rotation of the disc is 1200 rpm.
32
and the effective source resistance is 500 , calculate the voltage
and current gains and the output resistance.
E20. Consider the circuit below, where all resistance values are in ohms.
E22. In the figure, consider that FF1 and FF2 cannot be set to a desired
value by reset/preset line. The initial states of the flip-flops are
unknown. Determine a sequence of inputs (x1, x2) such that the
output is zero at the end of the sequence.
Output
33
E23. Write a C program to generate a sequence of positive integers
between 1 and N, such that each of them has only 2 or/and 3 as
prime factors. For example, the first seven elements of the sequence
are: 2, 3, 4, 6, 8, 9, 12. Justify the steps of your algorithm.
E24. Design a circuit using the module, as shown in the figure below, to
compute a solution of the following set of equations:
3x + 6y – 10 = 0
2x – y – 8 = 0
A module consists of an ideal OP-AMP and 3 resistors, and you may
use multiple copies of such a module. Voltage inverters and sources
may be used, if required.
34
Test Code: PCB (short answer type) 2013
The selection test for M.Tech. in Computer Science will consist of two parts.
• Test MMA (objective type) in the forenoon session is the 1st part, and
• Test PCB (short answer type) in the afternoon session is the 2nd part.
The PCB test will consist of two groups.
The syllabus and sample questions for the MMA test are available separately. The
syllabus and sample questions for the PCB test are given below.
Note:
1. Not all questions in this sample set are of equal difficulty. They may not carry
equal marks in the test. More sample questions are available on the website
for M.Tech(CS) at http://www.isical.ac.in/∼deanweb/MTECHCSSQ.html
2. Each of the two tests MMA and PCB, will have individual qualifying marks.
1
Elementary Euclidean geometry and trigonometry.
Elementary number theory, divisibility, congruences, primality.
Determinants, matrices, solutions of linear equations, vector spaces, linear indepen-
dence, dimension, rank and inverse.
Group B
Mathematics
In addition to the syllabus for Mathematics in Group A, the syllabus includes:
Calculus and real analysis – real numbers, basic properties, convergence of se-
quences and series, limits, continuity, uniform continuity of functions, differentia-
bility of functions of one or more variables and applications, indefinite integral,
fundamental theorem of Calculus, Riemann integration, improper integrals, double
and multiple integrals and applications, sequences and series of functions, uniform
convergence.
Linear algebra – vector spaces and linear transformations, matrices and systems
of linear equations, characteristic roots and characteristic vectors, Cayley-Hamilton
theorem, canonical forms, quadratic forms.
Graph Theory – connectedness, trees, vertex coloring, planar graphs, Eulerian
graphs, Hamiltonian graphs, digraphs and tournaments.
Abstract algebra – groups, subgroups, cosets, Lagrange’s theorem, normal sub-
groups and quotient groups, permutation groups, rings, subrings, ideals, integral
domains, fields, characteristics of a field, polynomial rings, unique factorization
domains, field extensions, finite fields.
Differential equations – solutions of ordinary and partial differential equations and
applications.
Statistics
Notions of sample space and probability, combinatorial probability, conditional
probability, Bayes’ theorem and independence.
Random variable and expectation, moments, standard univariate discrete and con-
tinuous distributions, sampling distribution of statistics based on normal samples,
central limit theorem, approximation of binomial to normal, Poisson law.
Multinomial, bivariate normal and multivariate normal distributions.
Descriptive statistical measures, product-moment correlation, partial and multiple
correlation.
Regression – simple and multiple.
Elementary theory and methods of estimation – unbiasedness, minimum variance,
sufficiency, maximum likelihood method, method of moments, least squares meth-
ods.
Tests of hypotheses – basic concepts and simple applications of Neyman-Pearson
lemma, confidence intervals.
2
Tests of regression, elements of non-parametric inference, contingency tables and
Chi-square, ANOVA, basic designs (CRD/RBD/LSD) and their analyses, elements
of factorial designs.
Conventional sampling techniques, ratio and regression methods of estimation.
Physics
3
Computer Science
Data structures – array, stack, queue, linked list, binary tree, heap, AVL tree, B-
tree.
Programming languages – Fundamental concepts – abstract data types, procedure
call and parameter passing, languages like C and C++.
Design and analysis of algorithms – Asymptotic notation, sorting, selection, search-
ing.
Computer organization and architecture – Number representation, computer arith-
metic, memory organization, I/O organization, microprogramming, pipelining, in-
struction level parallelism.
Operating systems – Memory management, processor management, critical section
problem, deadlocks, device management, file systems.
Formal languages and automata theory – Finite automata and regular expressions,
pushdown automata, context-free grammars, Turing machines, elements of unde-
cidability.
Principles of Compiler Construction – Lexical analyzer, parser, syntax-directed
translation, intermediate code generation.
Database management systems – Relational model, relational algebra, relational
calculus, functional dependency, normalization (up to 3r d normal form).
Computer networks – OSI, LAN technology – Bus/tree, Ring, Star; MAC proto-
cols; WAN technology – circuit switching, packet switching; data communications
– data encoding, routing, flow control, error detection/correction, Internet working,
TCP/IP networking including IPv4.
Switching Theory and Logic Design – Boolean algebra, minimization of Boolean
functions, combinational and sequential circuits - synthesis and design.
Engineering and Technology
C Programming language.
Moments of inertia, motion of a particle in two dimensions, elasticity, friction,
strength of materials, surface tension, viscosity and gravitation.
Laws of thermodynamics and heat engines.
Electrostatics, magnetostatics and electromagnetic induction.
Magnetic properties of matter – dia, para and ferromagnetism.
Laws of electrical circuits – RC, RL and RLC circuits, measurement of current,
voltage and resistance.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
p-n junction, bipolar & FET devices, transistor amplifier, oscillator, multi-vibrator,
operational amplifier.
Digital circuits – logic gates, multiplexer, de-multiplexer, counter, A/D and D/A
converters.
Boolean algebra, minimization of switching functions, combinational and sequen-
tial circuits.
4
SAMPLE QUESTIONS
Group A
A1. How many times will the digit ‘7’ be written when listing the integers from 1
to 1000? Justify your answer.
A2. For sets A and B, define A∆B = (Ā ∩ B) ∪ (A ∩ B̄). Show the following
for any three sets A, B and C.
(a) A∆A = ∅.
(b) A∆(B∆C) = (A∆B)∆C.
(c) If A∆B = A∆C then B = C.
A3. In a group of n persons, each person is asked to write down the sum of the
ages of all the other (n − 1) persons. Suppose the sums so obtained are
s1 , . . . , sn . It is now desired to find the actual ages of the persons from these
values.
5
Group B
Mathematics
{x : Ax = 0} = {x : A2 x = 0}.
(c) Let
2 −1 −1
1
A = −1 2 −1 .
3
−1 −1 2
Which of the following statements are true? In each case, justify your
answer.
(i) The rank of A is equal to the trace of A.
(ii) The determinant of A is equal to the determinant of An for all n >
1.
M3. (a) (i) For 0 ≤ θ ≤ π/2, show that sin θ ≥ 2θ/π.
(ii) Hence or otherwise show that for λ < 1,
Z π/2
λ
lim x e−x sin θ dθ = 0.
x→∞ 0
P
Let√an ≥ 0, n = 1, 2, . . . be such that
(b) P an converges. Show that
an n−p converges for every p > 1/2.
M4. (a) Let a1 , a2 , . . . be integers and suppose there exists an integer N such
X∞
an
that an = (n − 1) for all n ≥ N. Show that is rational.
n=1
n!
6
(b) Let 0 < s1 , s2 , s3 < 1. Show that there exists exactly one x ∈ (0, ∞)
such that
sx1 + sx2 + sx3 = 1.
M7. (a) Let S and T be two subsets of a finite group (G, +) such that |S|+|T | >
|G|. Here |X| is the number of elements in a set X. Then prove that
S + T = G, where S + T = {s + t : s ∈ S, t ∈ T }.
7
Statistics
E(y1 ) = θ0 + θ1 + θ2 ,
E(y2 ) = θ0 + θ1 + θ3 ,
E(y3 ) = θ0 + θ2 + θ3 ,
E(y4 ) = θ0 + θ1 + θ2 .
3
X
(a) Determine the condition under which the parametric function ci θi is
i=0
estimable for known constants ci , i = 0, 1, 2, 3.
8
(b) Obtain the least squares estimates of the parameters θ0 , θ1 , θ2 and θ3 .
(c) Obtain the best linear unbiased estimator of (2θ1 − θ2 − θ3 ) and also
determine its variance.
(a) Find the most powerful test at level α = 0.05 to test whether the coin is
fair against the alternative that the coin is more likely to show up heads.
(b) What will be the conclusion of the test if there are exactly 7 heads in 10
tosses?
(c) Find the power function of this test.
9
Physics
→→
−
(a) Consider the central force F (−
−
→
P1. r) = F (r) rr . Show that
→ −
− →
∇ × F = 0.
(b) An electron is describing an orbit of radius a around the z-axis and in
→
−
a plane perpendicular to it. A uniform magnetic field B is acting along
the z-axis. Determine the magnitude of the angular momentum of the
electron.
(c) In an X-ray machine, an accelerating potential of 50 KeV is applied on
the electrons emitted by the cathode. What is the minimum wavelength
present in the X-rays emitted?
(d) A wire of negligible thickness having mass per unit length λ is floating
in a liquid kept in a square vessel of side 2a. The wire is floating parallel
to one of the sides of the vessel. The top surface of the liquid (in contact
with the wire) dips by a distance d as shown in the following figure.
What is the surface tension of the liquid? (Assume d ≪ a.)
a a
d
Liquid
P2. (a) A particle is falling freely from a height h at 30◦ latitude in the northern
q
3
hemisphere. Show that the particle will undergo a deflection of ω 2h 3g
in the eastward direction, where ω is the rotational velocity of the earth
about its own axis and g is the acceleration due to gravity.
→
−
(b) A particle of mass m is moving in a plane in the field of force F =
−br kr cos θ, where k is a constant, rb is the radial unit vector and θ is the
polar angle.
(i) Write the Lagrangian of the system.
(ii) Show that the Lagrange’s equations of motion are:
A. mr̈ − mr θ̇2 + kr cos θ = 0;
B. mr 2 θ̇ 6= constant.
(iii) Interpret (ii)B in the context of Kepler’s second law.
10
(x2 − x1 ) = 3c(t2 − t1 ), where c represents the velocity of light in
vacuum. Consider another inertial frame which moves with velocity
u along x-axis with respect to the first frame. Find the value of u for
which the events are simultaneous in the latter frame.
(b) Consider a particle of mass m inside a one-dimensional box of length L.
Let the state ψ(x, t) of the particle at t = 0 be given by the following:
A sin( 4πx
L
) cos( 3πx
L
), 0 ≤ x ≤ L
ψ(x, 0) =
0, otherwise
P5. (a) How does one understand molecular mean free path in the context of
molecular kinetic theory of gases? Obtain the analytic form of the law
governing the distribution of free paths in an ideal gas.
(b) Calculate the mean free path, the collision rate and the molecular di-
ameter for Hydrogen gas molecules having the following particulars:
molecular weight of Hydrogen = 2.016 gm; viscosity, η = 85 × 10−6
dynes/cm2 /velocity gradient; mean speed, c = 16 × 104 cm/sec; density,
ρ = 0.000089 gm/cc.
P6. (a) Consider the following circuit. Assume the diode to be ideal and RL =
RS = 100 Ω. Sketch the waveforms of the diode voltage VD and load
voltage VL if the source voltage varies with time t as VS = sin ωt, where
ω is the angular frequency.
11
VD
+ -
+
RS RL
+ VL
Vs
-
I2
1Ω 2Ω 2Ω
+
V1 I1 2Ω I3 3Ω
12
Computer Science
C1. (a) How many asterisks (*) in terms of k will be printed by the following C
function, when called as count(m) where m = 3k ? Justify your answer.
Assume that 4 bytes are used to store an integer in C and k is such that
3k can be stored in 4 bytes.
void count(int n)
{
printf("*");
if(n>1)
{
count(n/3);
count(n/3);
count(n/3);
}
}
C2. Give an efficient implementation for a data structure STACK MAX to support
an operation max that reports the current maximum among all elements in
the stack. Usual stack operations (createEmpty, push, pop) are also to
be supported.
How many bytes are needed to store your data structure after the follow-
ing operations: createEmpty, push(5), push(6), push(7), pop, max,
push(6), push(8), pop, pop, max, push(5). Assume that an integer can
be stored in 4 bytes.
C3. You are given an array X[ ]. The size of the array is very large but unknown.
The first few elements of the array are distinct positive integers in sorted
order. The rest of the elements are 0. The number of positive integers in the
array is also not known.
13
Design an algorithm that takes a positive integer y as input and finds the
position of y in X. Your algorithm should return “Not found” if y is not in
the array. You will get no credit if the complexity of your algorithm is linear
(or higher) in the number of positive integers in X.
C4. (a) Prove or disprove the following statement: The union of a regular lan-
guage with a disjoint non-regular language over the same alphabet can
never be regular.
[Hint: You may use the closure properties of regular languages.]
(b) It is known that the language L1 = {0n 1n 2i | i 6= n} is not a context free
language (CFL). Now consider the language
L2 = {0i 1n 2n | i 6= n}. We can prove L2 is not a CFL by convert-
ing L2 into L1 by applying two operations, both known to be closed on
CFLs. What are the two operations you will use for this conversion?
Justify your answer.
C5. Consider three relations R1(X, Y, Z), R2(M , N, P ), and R3(N, X). The
primary keys of the relations are underlined. The relations have 100, 30, and
400 tuples, respectively. The space requirements for different attributes are:
X = 30 bytes, Y = 10 bytes, Z = 10 bytes, M = 20 bytes, N = 20 bytes,
and P = 10 bytes. Let V (A, R) signify the variety of values that attribute
A may have in the relation R. Let V (N, R2) = 15 and V (N, R3) = 300.
Assume that the distribution of values is uniform.
(a) If R1, R2, and R3 are to be joined, find the order of join for the min-
imum cost. The cost of a join is defined as the total space required by
the intermediate relations. Justify your answer.
(b) Calculate the minimum number of disk accesses (including both reading
the relations and writing the results) required to join R1 and R3 using
block-oriented loop algorithm. Assume that (i) 10 tuples occupy a block
and (ii) the smaller of the two relations can be totally accommodated in
main memory during execution of the join.
C6. (a) Consider three processes, P1 , P2 , and P3 . Their start times and execu-
tion times are given below.
Process Start time Execution time
P1 t = 0 ms 100 ms
P2 t = 25 ms 50 ms
P3 t = 50 ms 20 ms
Let ∆ be the amount of time taken by the kernel to complete a context
switch from any process Pi to Pj . For what values of ∆ will the average
14
turnaround time for P1 , P2 , P3 be reduced by choosing a Shortest Re-
maining Time First scheduling policy over a Shortest Job First policy?
(b) The circuit shown in the following figure computes a Boolean function
F . Assuming that all gates cost Rs. 5 per input (i.e., an inverter costs Rs.
5, a 2-input gate costs Rs. 10, etc.), find the minimum cost realization
of F using only inverters, AND / OR gates.
A
D
F
C
15
sn−1 ⊕ (an−1 sn−1 ) = bn−1 (sn−1 ⊕ an−1 )
where ⊕ denotes the Boolean XOR operation. You may use the Boolean
identity: X + Y = X ⊕ Y ⊕ (XY ) to prove your result.
(b) Consider a machine with 5 stages F , D, X, M, W , where F denotes
instruction fetch, D - instruction decode and register fetch, X - exe-
cute/address calculation, M - memory access, and W - write back to
a register. The stage F needs 9 nanoseconds (ns), D needs 3 ns, X
requires 7 ns, M needs 9 ns, and W takes 2 ns. Let M1 denote a non-
pipelined implementation of the machine, where each instruction has to
be executed in a single clock cycle. Let M2 denote a 5-stage pipelined
version of the machine. Assume that pipeline overhead is 1 ns for each
stage. Calculate the maximum clock frequency that can be used in M1
and in M2 .
16
Engineering and Technology
E1. (a) A 44 KW d.c. machine has 110 Ω shunt resistance and 0.05 Ω arma-
ture resistance. Calculate the total armature power developed when the
machine is working as (i) a generator and (ii) a motor.
(b) Test data of a 200/400 V, 10 KVA transformer is as follows:
(i) Open-circuit test on primary side: 200 V, 50 A, 2500 W
(ii) Short-circuit test on secondary side: 20 V, 10 A, 80 W
Calculate the total loss at full-load with unity power factor.
E2. Two long straight parallel wires stand 2 meters apart in air and carry currents
I1 and I2 in the same direction. The field intensity at a point midway between
the wires is 7.95 Ampere-turn per meter. The force on each wire per unit
length is 2.4 ×10−4 N. Assume that the absolute permeability of air is 4π ×
10−7 H per meter.
(a) Explain the nature of the force experienced between the two wires, i.e.
attractive or repulsive.
(b) Determine I1 and I2 .
(c) Another parallel wire carrying a current of 50 A in the opposite direction
is now placed midway between the two wires and in the same plane.
Determine the resultant force on this wire.
E3. A choke coil connected across a 500 V, 50 Hz supply takes 1 A current at a
power factor of 0.8.
(a) Determine the capacitance that must be placed in series with the choke
coil so that it resonates at 50 Hz.
(b) An additional capacitor is now connected in parallel with the above
combination in (a) to change the resonant frequency. Obtain an ex-
pression for the additional capacitance in terms of the new resonant fre-
quency.
E4. (a) The mechanical system shown in the figure below is loaded by a hori-
zontal 80 N force. The length of the spring is 500 mm. Each arm of the
mechanical system is also of length 500 mm as shown in the figure. Un-
der the influence of 80 N load, the spring is stretched to 600 mm but the
entire mechanical system including the spring remains in equilibrium.
Determine the stiffness of the spring. Note that the spring and the frame
are fixed at the pin position P. The other end of the spring is at R which
is a frictionless roller free to move along the vertical axis. Assume that
the mechanical joints between the arms are frictionless.
17
(b) A brake system is shown in the figure below. The solid disk of radius
1000 mm is being rotated at 196 rpm. The bar AB, of length 4000 mm,
is fixed at the end A and subjected to a downward load of 100 N at
the end B to stop the rotation of the disk. The bar AB (assumed to be
horizontal) touches the rotating disk at a point 500 mm from the fixed
end of the bar. The weight of the disk is 10 Kg and the coefficient of
friction between the bar and the disk is 0.5. Calculate the number of
revolutions the disk will make before coming to rest.
E5. (a) Air at 90◦ C and 605 Kg per square meter pressure is heated to 180◦ C
keeping the volume constant at 21 cubic meter. Find
(i) the final pressure, and
(ii) the change in the internal energy.
Note that the specific heat at constant pressure (Cp ), the specific heat at
constant volume (Cv ), and the mechanical equivalent of heat are 0.3, 0.2
and 420 Kg-meter per Kcal, respectively.
(b) A molten metal is forced through a cylindrical die at a
pressure of 168×103 Kg per square meter. Given that the density of
the molten metal is 2000 Kg per cubic meter and the specific heat of the
metal is 0.03, find the rise in temperature during this process. Assume
that the mechanical equivalent of heat is 420 Kg-meter per Kcal.
E6. (a) Calculate the current I flowing through the resistor R shown in the fol-
lowing figure (e1 < e2 < · · · < en ).
18
r r r
I
r1 + e1 r2 + e2 rn + n
e
− − − R
E7. (a) Design a logic circuit to implement the following truth table. What is
the function of this logic circuit?
Inputs Outputs
A B C D
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
(b) Show that the logic circuit corresponding to the following truth table can
be realized by interconnecting two instances of the logic circuit derived
in (a) and an additional OR gate.
Inputs Outputs
A B C D E
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
E8. (a) Consider the following circuit with an ideal Op-amp. Calculate Vo .
19
10 K
2V 5K
Vo
2K
1V 2K
(b) The following network uses four transconductor amplifiers and two ca-
pacitors to produce the output voltage Vo for the input voltage Vi .
Vo
gm gm gm gm
1 2 3 4
V
i _
+ + +
_ _ _
+
C C
1 2
Vo gm1 /gm4 .
H(s) = = gm2 C2
Vi C1 C2
1 + ( gm gm )s + ( gm gm )s 2
3 4 3 4
Q1
+ +
Q2 Re = 1K
Vi Vo
- -
(i) Draw the equivalent circuit using the small-signal hybrid parameter
model.
20
(ii) For the following values of h parameters for both transistors: hie =
1000 Ω, hf e = 100, hre = hoe = 0, determine the voltage amplifi-
cation Av and the input resistance Rin .
E10. (i) Find the output of the following C program.
#include <stdio.h>
void PRINT1(void)
{
static int x = 10;
x += 5;
printf("%d ", x);
}
void PRINT2(void)
{
static int x;
x = 10;
x += 5;
printf("%d ", x);
}
int main( )
{
PRINT1( ); PRINT1( ); PRINT2( ); PRINT2( );
return 0;
}
(ii) Explain the output of the following C program.
#include <stdio.h>
int main( )
{
char string1[15] = "ISI, Kolkata";
char string2[15] = "ISI, Kolkata";
if (string1 == string2)
printf("Two strings are equal");
else
printf("Two strings are unequal");
return 0;
}
(iii) Write a C function for finding the second largest element in an
array of n integers. Note that the array contains at least two distinct
integers. For example, if the array contains 30, 21, 12, 30, −5, 21
and 10, your function should return 21. The function must use as
few comparisons as possible.
—–x—–
21
Test Code: CS (Short answer type) 2004
M.Tech. in Computer Science
The candidates for M.Tech. in Computer Science will have to take two
tests ñ Test MIII (objective type) in the forenoon session and Test CS
(short answer type) in the afternoon session. The CS test booklet will have
two groups as follows.
GROUP A
A test for all candidates in mathematics at the B.Sc. (pass) level, carrying
30 marks.
GROUP B
A test, divided into several sections, carrying equal marks of 70 in
mathematics, statistics, and physics at the B. Sc. (Hons.) level and in
computer science, engineering and technology at the B.Tech. level. A
candidate has to answer questions in one of these sections only according
to his/her choice.
The syllabus and sample questions of the CS test are given below.
Note: All questions in the sample set are not of equal difficulty. They
may not carry equal marks in the test.
Syllabus
GROUP A
Elements of set theory. Permutations and combinations. Functions and
relations. Theory of equations. Inequalities.
Limit, continuity, sequences and series, differentiation and integration
with applications, maxima-minima, elements of ordinary differential
equations, complex numbers and De Moivreís theorem.
Elementary Euclidean geometry and Trigonometry.
Elementary number theory, divisibility, congruences, primality.
Determinants, matrices, solutions of linear equations, vector spaces, linear
independence, dimension, rank and inverse.
1
GROUP B
Mathematics
(B.Sc. Hons. level)
In addition to the syllabus of Mathematics in Group A, the syllabus
includes:
Calculus and real analysis ñ Real numbers, basic properties;
convergence of sequences and series; limits, continuity, uniform
continuity of functions; differentiability of functions of one or more
variables and applications. Indefinite integral, fundamental theorem of
Calculus, Riemann integration, improper integrals, double and multiple
integrals and applications. Sequences and series of functions, uniform
convergence.
Linear algebra - Vector spaces and linear transformations; matrices and
systems of linear equations, characteristic roots and characteristic vectors,
Cayley-Hamilton theorem, canonical forms, quadratic forms.
Graph Theory - Connectedness, trees, vertex colouring, planar graphs,
Eulerian graphs, Hamiltonian graphs, digraphs and tournaments.
Abstract algebra ñ Groups, subgroups, cosets, Lagrangeís theorem;
normal subgroups and quotient groups; permutation groups; rings,
subrings, ideals, integral domains, fields, characteristics of a field,
polynomial rings, unique factorization domains, field extensions, finite
fields.
Differential equations ñ Solutions of ordinary and partial differential
equations and applications.
Linear programming including duality theory.
Statistics
(B.Sc. Hons. level)
Notions of sample space and probability, combinatorial probability,
conditional probability, Bayes theorem and independence, random
variable and expectation, moments, standard univariate discrete and
continuous distributions, sampling distribution of statistics based on
normal samples, central limit theorem, approximation of binomial to
normal. Poisson law, Multinomial, bivariate normal and multivariate
normal distributions.
2
Descriptive statistical measures, graduation of frequency curves, product-
moment, partial and multiple correlation; regression (simple and multiple);
elementary theory and methods of estimation (unbiasedness, minimum
variance, sufficiency, maximum likelihood method, method of moments,
least squares methods). Tests of hypotheses (basic concepts and simple
applications of Neyman-Pearson Lemma). Confidence intervals. Tests of
regression. Elements of non-parametric inference. Contingency Chi-
square, ANOVA, basic designs (CRD/RBD/LSD) and their analyses.
Elements of factorial designs. Conventional sampling techniques, ratio and
regression methods of estimation.
Physics
(B.Sc. Hons. level)
Kinetic theory of gases. Equation of states for ideal and real gases.
Specific heats of gases. First and Second laws of thermodynamics and
thermodynamical relations. Heat engines. Low temperature physics, Joule-
Thomson effect.
Structure of atoms ñ Bohr-Sommerfeldís model, quantum number, e/m
of electrons, mass spectrograph. Wave-particle dualism, De Broglieís
equation, X-ray, Braggís law, Compton effect. Schrodingerís equation,
potential well and harmonic oscillator problems. Types of semiconductors,
transport phenomena of electrons and holes in semiconductors, p-n
Junction, radioactivity, special theory of relativity.
Simple harmonic motion. Moments of inertia. Conservation laws.
Coulombís law, Gaussís Theorem, dielectrics, Biot-Savartís Law,
Ampereís law. Electromagnetic induction, self and mutual inductance.
Maxwellís equations. Fundamental laws of electric circuits, RC, RL, RLC
circuits. Boolean algebra and logic circuits. Transistor and diode circuits.
Amplifiers. Oscillators.
Computer Science
(B.Tech. level)
Data structures - stack, queue, linked list, binary tree, heap, AVL tree, B
tree, design of algorithms, internal sorting, searching, programming
fundamentals, switching theory and logic design, computer organization
and architecture, operating systems, principles of compiler construction,
formal languages and automata theory, database systems, computer
networks.
3
Engineering and Technology
(B.Tech. level)
Moments of inertia, motion of a particle in two dimentions, elasticity,
surface tension, viscosity, gravity, acceleration due to gravity.
Problems on geometrical optics.
First and second laws of thermodynamics, thermodynamic relations and
their uses, heat engines.
Electrostatics, magnetostatics, electromagnetic induction.
Magnetic properties of matter - Dia, para and ferromagnetism.
Laws of electrical circuits - RC, RL and RLC circuits, measurement of
currents, voltages and resistance.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
p-n junction, transistor amplifiers, oscillator, multivibrators, operational
amplifiers.
Digital circuits - Logic gates, multiplexers, demultiplexers, counters, A/D
and D/A converters.
Boolean algebra, minimization of switching functions, combinational and
sequential circuits.
4
Sample Questions
GROUP A
Mathematics
A1. If 1, a1, a2,Ö , an-1 are the n roots of unity, find the value of
(1 - a1) (1 - a2)Ö (1 - an-1).
A2. Let A = (aij) be an n x n matrix, where
b if i = j,
aij =
c if i ≠ j ,
and b, c are real numbers such that b ≠ c. When is the matrix A
invertible?
A3. (a) Let
S ={( a1 , a2 , a3 , a4 ) : ai ∈ℜ, i =1, 2, 3, 4 and a1 + a2 + a3 + a4 = 0}
and
Γ = {(a1 , a 2 , a3 , a 4 ) : a i ∈ℜ, i = 1, 2, 3, 4 and a1 − a 2 + a 3 − a 4 = 0}.
Find a basis for S Γ.
(b) Provide the inverse of the following matrix:
c0 c1 c2 c3
c 2 c3 c0 c1
c − c2 c1 − c0
3
c − c c3 − c2
1 0
1+ 3 3+ 3 3− 3 1− 3
where c 0 = , c1 = , c2= , and c 3 = .
4 2 4 2 4 2 4 2
(Hint: What is c02 + c12 + c 22 + c32 ?)
A4. For any real number x and for any positive integer n show that
1 2 n − 1
[x] + x + + x + + L + x + = [nx ]
n n n
5
where [a] denotes the largest integer less than or equal to a.
A5. Let bqbq-1Ö b1b0 be the binary representation of an integer b, i.e.,
q
b = ∑ 2 j b j , bj = 0 or 1, for j = 0, 1, Ö , q.
j =0
Show that b is divisible by 3 if b0 − b1 + b2 − K +(−1) q bq = 0 .
at least one solution in the interval (0, 1).
A10. Let φ (n) be the number of positive integers less than n and having
no common factor with n. For example, for n = 8, the numbers 1, 3,
5, 7 have no common factors with 8, and hence φ(8) = 4. Show that
(i) φ ( p) = p − 1 ,
(ii) φ ( pq) = φ ( p)φ (q) , where p and q are prime numbers.
A11. A set S contains integers 1 and 2. S also contains all integers of the
form 3x+ y where x and y are distinct elements of S, and every
element of S other than 1 and 2 can be obtained as above. What is S?
Justify your answer.
A12. Let f be a real-valued function such that f(x+y) = f(x) + f(y)
∀x, y ∈ R. Define a function φ by φ(x) = c + f(x), x ∈ R, where c is a
real constant. Show that for every positive integer n,
φ ( x) = (c + f (c ) + f (c) + ..... + f (c)) + f ( x);
n 2 n −1 n
where, for a real-valued function g, g n (x ) is defined by
6
g 0 ( x) = 0, g 1 ( x) = g ( x), g k +1 ( x) = g ( g k ( x)).
A13. Consider a square grazing field with each side of length 8 metres.
There is a pillar at the centre of the field (i.e. at the intersection of
the two diagonals). A cow is tied with the pillar using a rope of
length 83 metres. Find the area of the part of the field that the cow
is allowed to graze.
A14. There are four geometrical objects in the form of square, rhombus,
circle and triangle. Each one is made from one of the 4 different
materials gold, copper, silver, and bronze and coloured differently
using blue, red, green and yellow paints. The square is of green
colour. The blue object is made of bronze. The circle is not red.
The triangle is not made of gold. The square is not made of copper.
The rhombus is not blue and is not made of silver. The circle is not
made of bronze. The triangle is not yellow. The red object is not
made of copper. Deduce logically the colour and material of the
circle.
GROUP B
Mathematics
x n +3
M1. Let 0 < x1 < 1. If xn+1 = 3x + 1 , n = 1,2,3, Ö
n
5x n +3
(i) Show that xn+2 = 3x +5 , n = 1,2,3, Ö
n
7
(b) Let f : [0,1] → ℜ be a continuous function with f(0) = 0. Assume
that f ′ is finite and increasing on (0,1).
Let g ( x) = f ( x)
x
x ∈ (0,1) . Show that g is increasing.
M3. (a) Prove the inequality ex > 1+(1+x) log(1+x), for x > 0.
x
(b) Show that the series ∑ n(1 + nx) 2 is uniformly convergent on
[0,1].
M4. Consider the function of two variables
F(x,y) = 21x - 12x2 - 2y2 + x3 + xy2.
(a) Find the points of local minima of F.
(b) Show that F does not have a global minimum.
M5. Find the volume of the solid given by 0 ≤ y ≤ 2 x , x 2 + y 2 ≤ 4 and
0 ≤ z ≤ x .
M6. (a) Let A, B and C be 1×n, n×n and n×1 matrices respectively. Prove
or disprove: Rank(ABC) ≤ Rank(AC).
(b) Let S be the subspace of R4 defined by
S = {(a1, a2, a3, a4) : 5a1 - 2a3 -3a4 = 0}.
Find a basis for S.
M7. Let A be a 3×3 matrix with characteristic equation λ − 5λ = 0.
3 2
(i) Show that the rank of A is either 1 or 2.
(ii) Provide examples of two matrices A1 and A2 such that the
rank of A1 is 1, rank of A2 is 2 and Ai has characteristic
equation λ3 - 5λ2 = 0 for i = 1, 2.
M8. Let {0,1}* be the set of all binary strings (i.e. finite sequences of 0s
and 1s). The empty string denoted by λ is also in {0,1}*. The
lexicographic ordering on {0,1}*, denoted by <L, is defined as:
for x = x1 x2Ö xm , y = y1 y2Ö yl ∈ {0,1}* , x <L y if and only if one of
the following conditions is satisfied:
(i) m < l,
(ii) m = l and there is a k < m such that xi = yi , i = 1, Ö , k and xk+1
< yk+1.
8
Let < be the natural ordering on the set of natural numbers N =
{0,1,2,Ö }. For n ∈ N let (n)b be the binary representation of n and if
n ∈ [0,2 k − 1] , for some k ≥ 0 , let (n)bk be the k-bit binary string
obtained from (n)b by adding leading 0s if needed.
(a) Show that, for any integers r, s ∈ [0,2k − 1] , for k > 0, (r)bk <L
(s)bk if and only if r < s.
(b) Using <L and (a) give an explicit definition of a one-to-one, onto
map f : N → {0,1}* . Justify your answer.
M9. Let G be the group of all 2×2 non-singular matrices with matrix
multiplication as the binary operation. Provide an example of a
normal subgroup H of G such that H ≠ G and H is not a singleton.
M10. Let R be the field of reals. Let R[x] be the ring of polynomials over
R, with the usual operations.
(a) Let I ⊆ R[x] be the set of polynomials of the form a0 +a1x
+....+ anxn with a0 = a1 = 0. Show that I is an ideal.
(b) Let P be the set of polynomials over R of degree ≤ 1. Define ⊕
and Θ on P by (a0 +a1x) ⊕ (b0 +b1 x) = (a0 + b0)+(a1 +b1)x and
(a0 +a1x) Θ (b0 + b1x) = a0b0 + (a1b0 +a0b1)x. Show that (P, ⊕,
Θ ) is a commutative ring. Is it an integral domain? Justify your
answer.
M11. (a) If G is a group of order 24 and H is a subgroup of G of order 12,
prove that H is a normal subgroup of G.
(b) Show that a field of order 81 cannot have a subfield of order 27.
M12. (a) Consider the differential equation:
d2y dy
2
cos x + sin x − 2 y cos 3 x = 2 cos5 x.
dx dx
By a suitable transformation, reduce this equation to a second
order linear differential equation with constant coefficients.
Hence or otherwise solve the equation.
(b) Find the surfaces whose tangent planes all pass through the
origin.
9
M13. (a) Consider the following two linear programming problems:
P1: Minimize x1 subject to
x1 + x2 ≥ 1
− x1 − x2 ≥ 1
where both x1 and x2 are unrestricted.
P2: Minimize x1 subject to
x1 + x2 ≥ 1
− x1 − x2 ≥ 1
x1 ≥ 0, x2 ≥ 0.
Solve both the LPs. Write the duals of both the LPs and solve
the duals.
(b) If an LP is infeasible, what can you say about the solution of its
dual?
M14. Solve the following linear programming problem without using
Simplex method:
minimize 6 w1 + 8 w2 + 7 w3 + 15 w4 + w5
subject to w1 + w3 + 3 w4 ≥ 4,
w2 + w3 + w4 ñ w5 ≥ 3,
w1, w2, w3, w4, w5 ≥ 0.
M15. (a) Show that a tree on n vertices has at most n−2 vertices with
degree > 1.
(b) Show that in an Eulerian graph on 6 vertices, a subset of 5
vertices cannot form a complete subgraph.
M16. (a) Show that the edges of K4 can be partitioned into 2 edge-disjoint
spanning trees.
(b) Use (a) to show that the edges of K6 can be partitioned into 3
edge-disjoint spanning trees.
(c) Let Kn denote the complete undirected graph with n vertices and
let n be an even number. Prove that the edges of Kn can be
partitioned into exactly n/2 edge-disjoint spanning trees.
10
Statistics
S1. A safety device is designed to have a high conditional probability of
operating when there is a failure (dangerous condition) and high
conditional probability of not operating when a failure does not
occur. For a particular brand of safety device both these probabilities
are 0.98. Given that a dangerous condition occurs with probability
0.01, find the conditional probability that there was a failure when
the safety device worked.
S2. (a) Let X0, X1, X2, Ö be independent and identically distributed
random variables with common probability density function f. A
random variable N is defined as
N = n if X1 ≤ X 0 , X 2 ≤ X 0 , , X n−1 ≤ X 0 , X n > X 0 , n = 1, 2, 3,
Find the probability of N = n .
(b) Let X and Y be independent random variables distributed
uniformly over the interval [0,1]. What is the probability that
the integer closest to YX is 2?
S3. If a die is rolled m times and you had to bet on a particular number of
sixes occurring, which number would you choose? Is there always
one best bet, or could there be more than one?
S4. Let X 1 , X 2 and X3 be independent random variables with Xi
following a uniform distribution over (0, iθ), for i = 1 , 2, 3 . Find the
maximum likelihood estimate of θ based on observations x1 , x 2 , x3
on X 1 , X 2 , X 3 respectively. Is it unbiased? Find the variance of the
estimate.
S5. New laser altimeters can measure elevation to within a few inches,
without bias. As a part of an experiment, 25 readings were made on
the elevation of a mountain peak. These averaged out to be 73,631
inches with a standard deviation (SD) of 10 inches. Examine each of
the following statements and ascertain whether the statement is true
or false, giving reasons for your answer.
(a) 73631 ± 4 inches is a 95% confidence interval for the elevation of
the mountain peak.
(b) About 95% of the readings are in the range 73631 ± 4 inches.
11
(c) There is about 95% chance that the next reading will be in the
range of 73631 ± 4 inches.
S6. Consider a randomized block design with two blocks and two
treatments A and B. The following table gives the yields:
Treatment A Treatment B
Block 1 a b
Block 2 c d
(a) How many orthogonal contrasts are possible with a, b, c and d?
Write down all of them.
(b) Identify the contrasts representing block effects, treatment
effects and error.
(c) Show that their sum of squares equals the total sum of squares.
S7. Let X be a discrete random variable having the probability mass
function
p(x) = Λx(1- Λ)1-x, x = 0, 1,
where Λ takes values ≥ 0.5 only. Find the most powerful test, based
1 2
on 2 observations, for testing H0 : Λ = against H1 : Λ = , with
2 3
level of significance 0.05.
S8. Let X1, X2, Ö , Xn be n independent N(θ,1) random variables where
−1 ≤ θ ≤ 1. Find the maximum likelihood estimate of θ and show
that it has smaller mean square error than the sample mean X .
S9. Let t1, t2, Ö tk be k independent and unbiased estimators of the same
k
t
parameter θ with variances σ 12 , σ 22 ,Kσ k2 . Define t as ∑ i . Find
i =1 k
k
E( t ) and the variance of t . Show that ∑ (t
i =1
i − t ) 2 /{k (k − 1)} is an
unbiased estimator of var( t ).
S10. Consider a simple random sample of n units, drawn without
replacement from a population of N units. Suppose the value of Y1 is
unusually low whereas that of Yn is very high. Consider the following
estimator of Y , the population mean.
12
y + c, if the sample contains unit 1 but not unit N ;
à
Y = y − c, if the sample contains unit N but not unit 1;
y , for all other samples;
where y is sample mean and c is a constant. Show that Yà is
unbiased. Given that
à S2 2c
V (Y ) = (1 − f ) − (Y N −Y 1− nc)
n N −1
n 1 N
where f =
N
and S =
2
∑
N − 1 i =1
(Yi − Y ) 2 , comment on the choice
of c.
S11. In order to compare the effects of four treatments A, B, C, D, a block
design with 2 blocks each having 3 plots was used. Treatments A, B,
C were given randomly to the plots of one block and treatments A, B,
D were given randomly to the plots of the other block. Write down a
set of 3 orthogonal contrasts with the 4 treatment effects and show
that all of them are estimable from the above design.
S12. Let y1, y2 and y3 be independent and identically distributed random
variables with distribution N ( µ ,1) . Find a1, a2 and b1, b2, b3,such
that U1 = a1 y1 + a2 y2 and U 2 = b1 y1 + b2 y2 + b3 y3 are independent
N (0,1) . Hence express
( y12 + y22 + y 32 ) 2
y1 + y 2 + y3 −
2 2 2
in terms of U1 and U2 and show that
3
( y12 + y22 + y 32 ) 2
y
1
2
+ y 2
2
+ y 2
3
− follows the χ2 distribution with two
3
degrees of freedom.
13
S13. In a factory, the distribution of workers according to age-group and
sex is given below.
Sex Age-group Row
↓ 20-40 yrs. 40-60 yrs. total
Male 60 40 100
Female 40 10 50
Column Total 100 50 150
Give a scheme of drawing a random sample of size 5 so that both
the sexes and both the age-groups are represented. Compute the
first-order inclusion probabilities for your scheme.
Physics
P1. A beam of X-rays of frequency v falls upon a metal and gives rise to
photoelectrons. These electrons in a magnetic field of intensity H
describe a circle of radius γ. Show that
1
2 1+ e
2 2
H 2 2
h (v − v 0 ) = m 0 c − 1
2 4
m0 c
where v0 is the frequency at the absorption limit and m0 is the rest mass
of the electron, e being expressed in e.s.u.
P2. An ideal gas goes through a cycle consisting of alternate isothermal
and adiabatic curves as shown in the figure.
AB, CD, and EF are isothermal curves at temperatures T1 , T2 and T3
respectively, while BC, DE, and FA are adiabatic curves. Find the
efficiency of such a cycle, if in each isothermal expansion the gas
volume increases by the same factor.
14
P3. A parallel plate air capacitor is charged to 100 volts. The plate
separation distance is 2mm and the area of each plate is 120 cm2.
Calculate and account for the change of stored energy when the plate
separation is reduced to 1mm,
(a) at constant voltage,
(b) at constant current.
P4. (a) Show that it is impossible for a photon to give up all its energy and
momentum to a free electron.
(b) Find the proper length of a rod in the laboratory frame of reference
if its velocity is v = c/2, its length is l = 1 metre, and the angle
between the rod and its direction of motion is 45 deg.
P5. (a) Determine the time period of small oscillation of a pendulum of
length l, if it is located in a liquid whose density is η times less
than that of the material of the pendulum bob. (Neglect the
resistance of the liquid).
(b) A body of mass m fell from a height h onto the pan of a spring
balance, the spring having the stiffness value k. Having stuck to
the pan the body starts performing harmonic oscillations in the
vertical direction. Find the amplitude and mechanical energy of
the oscillation. (Neglect the masses of the pan and the spring).
P6. A particle of mass m is moving in a one dimensional potential U(x)
given by
U ( x) = ∞ , x = 0
= 0, 0 < x < l
= U 0, x = l
(a) Show that the bound state energy values E are given by the
equation
ηk
sin(kl ) = ±
2mU 0
2mE
where k = .
η
(b) Show that the minimum value of U0 at which the first bound state
η 2π 2
appears is .
8ml 2
15
P7. Consider the following circuit in which an a.c. source of V volts at a
frequency of 106/π cycles/sec is applied across the combination of
resistances and inductances. The total rms current flowing through the
circuit as measured by an a.c. ammeter is 10 amp. Find the rms
current I1 flowing through the upper branch of impedances. The self
inductance of the two coils are as shown in the figure. The mutual
inductance between the coils is 2 mH and is such that the
magnetization of the two coils are in opposition.
P8. A relay has a resistance 20 Ω and an inductance 0.5H. It is energised
by a d.c. voltage pulse which rises from 0 to 10 volts instantaneously,
remains constant for 0.25 s and then instantly falls to zero value. The
relay closes when the current in it attains a value 200mA and opens
when it drops to 100mA. Find the time for which the relay remains
closed.
P9. A silicon based p-n junction has an equal concentration of donor and
acceptor atoms. Its depletion zone of width d is symmetrical about its
junction plane.
(a) What is the maximum electrical field Emax in depletion zone, if k is
the dielectric constant of silicon?
(b) What is the potential difference, V, existing across the depletion
zone?
(c) If the potential difference across the depletion zone is 0.4 volt and
the concentration of donor/acceptor atoms 3 x 1022 m-3, find the
width d of the depletion zone and maximum electric field in the
zone.
16
P10. A conducting rod AB makes contact with metal rails AD and BC
r
which are 50cm apart in a uniform magnetic field B = 1.0 wb/m2
perpendicular to the place ABCD. The total resistance (assumed
constant) of the circuit ADCB is 0.4Ω.
(c) What is the direction and magnitude of e.m.f. induced in the rod
when it is moved to the left with a velocity of 8m/s?
(d) What force is required to keep the rod in motion?
(e) Compare the rate at which mechanical work is done by the force
r
F with the rate of development of electric power in the circuit.
P11. An elementary particle called ∑-, at rest in laboratory frame, decays
spontaneously into two other particles according to Σ− → π − + n .
The masses of ∑-, π- and n are M1, m1, and m2 respectively.
(a) How much kinetic energy is generated in the decay process?
(b) What are the ratios of kinetic energies and momenta of π and
−
n?
P12. A combinational network is given with four inputs A, B, C, and D,
three intermediate outputs U, V, and W, and two final outputs X =
Σ(0,1,3,4,5,7,11,15) and Y = Σ(2,3,6,7,11,15), as shown in the figure
below.
(a) Assume that G1 and G2 are both AND gates, show the map for
the smallest function Vmin (with minimum number of minterms)
which makes it possible to produce X and Y.
(b) Show the maps for U and W corresponding to the above Vmin.
17
P13. (a) Find the relationship between L, C and R in the circuit shown in
the figure such that the impedance of the circuit is independent of
frequency. Find out the impedance.
(b)
Find the value of R and the current flowing through R shown in
the figure when the current is zero through R′.
Computer Science
C1. (a) A grammar is said to be left recursive if it has a non-terminal A
such that there is a derivation A ⇒ + Aα for some sequence of
symbols α. Is the following grammar left-recursive? If so, write
an equivalent grammar that is not left-recursive.
A → Bb A → a
B →Cc B → b
C → Aa C → c
18
(b) An example of a function definition in C language is given below:
19
C5. a) Consider a pipelined processor with m stages. The processing time
at every stage is the same. What is the speed-up achieved by the
pipelining?
b) In a certain computer system with cache memory, 750 ns
(nanosec) is the access time for main memory for a cache miss
and 50 ns is the access time for a cache hit. Find the percentage
decrease in the effective access time if the hit ratio is increased
from 80% to 90%.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and 1000
cylinders. The speed of rotation of the disk is 6000 rpm. The
average seek time is 10 millisecs. A file of size 50 MB is written
from the beginning of a cylinder and a new cylinder will be
allocated only after the first cylinder is totally occupied.
i) Find the maximum transfer rate.
ii) How much time will be required to transfer the file of 50 MB
written on the disk? Ignore the rotational delay but not the seek
time.
(b) Following are the solutions for the two process (pi and pj) critical
section problem. Find the errors (if any) in these solutions and
rectify them. The notations have usual meanings and i = 0, 1; j =
1-i.
Solution 1
Pi: repeat
while flag [j] do skip;
flag [i] = true;
critical section;
flag [i] = false;
exit section;
until false;
Solution 2
Pi: repeat
flag[i] = true;
while flag [j] do skip ;
critical section:
flag [i] = false ;
exit section;
until false;
20
C7. (a) A computer on a 6 Mbps network is regulated by a token bucket.
The bucket is filled at a rate of 2 Mbps. It is initially filled to
capacity with 8 Megabits. How long can the computer transmit at
the full 6 Mbps?
(b) Sketch the Manchester encoding for the bit stream 0001110101.
(c) If delays are recorded in 8-bit numbers in a 50-router network, and
delay vectors are exchanged twice a second, how much bandwidth
per (full-duplex) line is consumed by the distributed routing
algorithm? Assume that each router has 3 lines to other routers.
C8. (a) The order of a regular language L is the smallest integer k for
which Lk = Lk+1, if there exists such a k, and ∞ otherwise.
(i) What is the order of the regular language a + (aa)(aaa)*?
(ii) Show that the order of L is finite if and only if there is an
integer k such that Lk = L*, and that in this case the order of L
is the smallest k such that Lk = L*.
(b) Solve for T(n) given by the following recurrence relations:
T(1) = 1;
T(n) = 2T(n/2) + n log n, where n is a power of 2.
C9. (a) Minimize the switching function w′xy′z + wx′y′z + w′xyz′ +
wx′yz′.
(b) A certain four-input gate G realizes the switching function
G(a, b, c, d) = abc + bcd. Assuming that the input variables are
available in both complemented and uncomplemented forms:
(i) Show a realization of the function f(u, v, w, x) = Σ (0, 1, 6,
9, 10, 11, 14, 15) with only three G gates and one OR gate.
(ii) Can all switching functions be realized with {G, OR} logic
set ?
C10. Let L1 and L2 be two arrays each with n = 2k elements sorted
separately in ascending order. If the two arrays are placed side by
side as a single array of 2n elements, it may not be found sorted. All
the 2n elements are distinct. Considering the elements of both the
arrays, write an algorithm with k + 1 comparisons to find the n-th
smallest element among the entire set of 2n elements.
C11. Assume the following characteristics of instruction execution in a
given computer:
• ALU/register transfer operations need 1 clock cycle each,
• each of the load/store instructions needs 3 clock cycles, and
21
• branch instructions need 2 clock cycles each.
(a) Consider a program which consists of 40% ALU/register
transfer instructions, 30% load/store instructions, and 30%
branch instructions. If the total number of instructions in this
program is 10 billion and the clock frequency is 1GHz, then
compute the average cycles per instruction (CPI), total
execution time for this program, and the corresponding MIPS
rate.
(b) If we now use an optimizing compiler which reduces the total
number of ALU/register transfer instructions by a factor of 2,
keeping the number of other instruction types unchanged, then
compute the average CPI, total time of execution and the
corresponding MIPS rate for this modified program.
Engineering and Technology
E1. A rocket weighing 50,000 kg has been designed so as to eject gas at a
constant velocity of 250 meters/sec. Find the minimum rate at which
the rocket should lose its mass (through ejection of gas) so that the
rocket can just take off.
E2. A particle of mass m is attached to a fixed point by means of a string
of length l and hangs freely. Show that if it is pushed horizontally
with a velocity greater than 5 gl , it will completely describe a
vertical circle.
E3. (a) A uniform cylinder of radius R is spun about its axis with angular
velocity ω and placed at a corner. The coefficient of friction
between the corner walls and the cylinder is k. Find the number of
turns (without rolling) the cylinder completes before it stops.
(b) A two-step pulley weighs 290 Kg and has a radius of gyration
40cm. If a string wound over the pulley, as shown in the figure
22
below, suspends two weights of 40 Kg each, determine the
acceleration of the weights.
E4. A flywheel of mass 100 kg and radius of gyration 20 cm is mounted
on a light horizontal axle of radius 2 cm, and is free to rotate on
bearings whose friction may be neglected. A light string wounded on
the axle carries at its free end a mass of 5 kg. The system is released
from rest with the 5 kg mass hanging freely. If the string slips off the
axle after the weight has descended 2 m, prove that a couple of
moment of 10/π2 kg.wt.cm. must be applied in order to bring the
flywheel to rest in 5 revolutions.
E5. The truss shown in the figure rotates around the pivot O in a vertical
plane at a constant angular speed ω. Four equal masses (m) hang from
the points B, C, D and E. The members of the truss are rigid,
weightless and of equal length. Find a condition on the angular speed
ω so that there is compression in the member OE.
23
E6. In the circuit shown below, the Op-Amp is an ideal one.
(a) Show that the conditions for free oscillation can be met in the
circuit.
(b) Find the ideal value of R to meet the conditions for oscillation.
(c) Find the frequency of oscillation. (Assume π = 3.14).
E7. Two bulbs of 500cc capacity are connected by a tube of length 20 cm
and internal radius 0.15 cm. The whole system is filled with oxygen,
the initial pressures in the bulbs before connection being 10 cm and
15 cm of Hg, respectively. Calculate the time taken for the pressures
to become 12 cm and 13 cm of Hg, respectively. Assume that the
coefficient of viscosity η of oxygen is 0.000199 cgs unit.
E8. Two identical watch glasses with negligible thickness are glued
together.
The rear one is silvered [see Figure(a)]. Sharp focus is obtained when
both object and image distance are equal to 20 cm. Suppose the space
between the glasses is filled with water (refractive index = 4/3) [see
Figure (b)]. Calculate d [Figure (b)] for which a sharp real image is
formed.
24
E9. (a) Two systems of equal mass m1 and m2 and heat capacity C are at
temperatures T1 and T2 respectively (T1 > T2). If the first is used as
source and the second as sink, find the maximum work obtainable
from such an arrangement.
(b) A Carnot engine A operates between temperatures T1 and T2 whose
dissipated heat at T2 is utilised by another Carnot engine B
operating between T2 and T3. What is the efficiency of a third
engine that operates between T1 and T3 in terms of the efficiencies
hA and hB of engines A and B respectively?
E10. (a) A system receives 10 Kcal of heat from a reservoir to do 15 Kcal
of work. How much work the system must do to reach the initial
state by an adiabatic process?
(b) A certain volume of Helium at 15"C is suddenly expanded to 8
times its volume. Calculate the change in temperature (assume
that the ratio of specific heats is 5/3).
E11. A spherical charge distribution has a volume density ρ, which is a
function of r, the radial distance from the center of the sphere, as
given below.
A / r , A is constant for 0 ≤ r ≤ R
ρ =
0 , for r > R
Determine the electric field as a function of r, for r ≥ R. Also deduce
the expression for the electrostatic potential energy U(r), given that
U(∞) = 0 in the region r ≥ R.
E12. Consider the distribution of charges as shown in the figure below.
Determine the potential and field at the point p.
E13. A proton of velocity 107 m/s is projected at right angles to a uniform
magnetic induction field of 0.1 w/m2. How much is the path of the
particle deflected from a straight line after it has traversed a distance
of 1 cm? How long does it take for the proton to traverse a 900 arc?
25
E14. Calculate the diamagnetic susceptibility of neon at standard
temperature and pressure (00C and 1 atmospheric pressure) on the
assumption that only the eight outer electrons in each atom
contribute and their mean radius is 4.0 X 10-9 cm.
E15. A circular disc of radius 10cm is rotated about its own axis in a
uniform magnetic field of 100 weber/m2, the magnetic field being
perpendicular to the plane of the disc. Will there be any voltage
developed across the disc? If so, then find the magnitude of this
voltage when the speed of rotation of the disc is 1200 rpm.
E16. A 3-phase, 50-Hz, 500-volt, 6-pole induction motor gives an output
of 50 HP at 900 rpm. The frictional and windage losses total 4 HP
and the stator losses amount to 5 HP. Determine the slip, rotor
copper loss, and efficiency for this load.
E17. A 20 KVA, 2000/200 V two-winding transformer is to be used as an
auto-transformer with a constant source voltage of 2000 V. At full
load with unity power factor, calculate the power output, power
transformed and power conducted. If the efficiency of the two-
winding transformer at 0.7 power factor is 90%, find the efficiency
of the auto-transformer.
E18. An alternator on open-circuit generates 360 V at 60 Hz when the
field current is 3.6 A. Neglecting saturation, determine the open-
circuit e.m.f. when the frequency is 40 Hz and the field-current is 24
A.
E19. A 150 KVA, 4400/440 volt single phase transformer has primary and
secondary resistance and leakage reactance values as follows:
Rp = 2.4 Ω, Rs = 0.026 Ω, Xp =5.8 Ω, and Xs = 0.062 Ω.
This transformer is connected with a 290 KVA transformer in
parallel to deliver a total load of 330 KVA at a lagging power factor
of 0.8. If the first transformer alone delivers 132 KVA, calculate the
equivalent resistance, leakage reactance and percentage regulation of
the second transformer at this load. Assume that both the
transformers have the same ratio of the respective equivalent
resistance to equivalent reactance.
26
E20. The hybrid parameters of a p-n-p junction transistor used as an
amplifier in the common-emitter configuration are: hie = 800Ω, hfe =
46, hoe = 8 x 10-5 mho, hre = 55.4 x 10-4. If the load resistance is 5 kΩ
and the effective source resistance is 500 Ω, calculate the voltage
and current gains and the output resistance.
E21. Find the equivalent resistance between the points A and D of the
circuit shown in the diagram.
E22. (a) Design a special purpose counter to count from 6 to 15 using a
decade counter. Inverter gates may be used if required.
(b) For a 5 variable Boolean function the following minterms are
true: (0, 2, 3, 8, 10, 11, 16, 17, 18, 24, 25 and 26). Find a
minimized Boolean expression using Karnaugh map.
E23. In the figure, consider that FF1 and FF2 cannot be set to a desired
value by reset/preset line. The initial states of the flip-flops are
unknown. Determine a sequence of inputs (x1, x2) such that the
output is zero at the end of the sequence.
Output
27
Test Code: CS (Short answer type) 2010
The candidates for M.Tech. in Computer Science will have to take two
tests – Test MIII (objective type) in the forenoon session and Test CS
(short answer type) in the afternoon session. The CS test booklet will have
two groups as follows.
GROUP A
A test for all candidates in analytical ability and mathematics at the B.Sc.
(pass) level, carrying 28 marks.
GROUP B
The syllabi and sample questions for the CS test are given below.
Note: Not all questions in the sample set are of equal difficulty. They
may not carry equal marks in the test.
Syllabus
GROUP A
1
GROUP B
Mathematics
(B.Sc. Hons. level)
Statistics
(B.Sc. Hons. level)
2
Descriptive statistical measures, product-moment correlation, partial and
multiple correlation; regression (simple and multiple); elementary theory
and methods of estimation (unbiasedness, minimum variance, sufficiency,
maximum likelihood method, method of moments, least squares methods).
Tests of hypotheses (basic concepts and simple applications of Neyman-
Pearson Lemma). Confidence intervals. Tests of regression. Elements of
non-parametric inference. Contingency tables and Chi-square, ANOVA,
basic designs (CRD/RBD/LSD) and their analyses. Elements of factorial
designs. Conventional sampling techniques, ratio and regression methods
of estimation.
Physics
(B.Sc. Hons. level)
3
Atomic and molecular physics – quantum states of an electron in an atom,
Hydrogen atom spectrum, electron spin, spin–orbit coupling, fine
structure, Zeeman effect, lasers.
Condensed matter physics – crystal classes, 2D and 3D lattice, reciprocal
lattice, bonding, diffraction and structure factor, point defects and
dislocations, lattice vibration, free electron theory, electron motion in
periodic potential, energy bands in metals, insulators and semiconductors,
Hall effect, thermoelectric power, electron transport in semiconductors,
dielectrics, Claussius Mossotti equation, Piezo, pyro and ferro electricity.
Nuclear and particle physics – Basics of nuclear properties, nuclear forces,
nuclear structures, nuclear reactions, interaction of charged particles and
e-m rays with matter, theoretical understanding of radioactive decay,
particle physics at the elementary level.
Computer Science
(B.Tech. level)
Data structures - array, stack, queue, linked list, binary tree, heap, AVL
tree, B-tree.
Programming languages - Fundamental concepts – abstract data types,
procedure call and parameter passing, languages like C and C++.
Design and analysis of algorithms – Asymptotic notation, sorting,
selection, searching.
Computer organization and architecture - Number representation,
computer arithmetic, memory organization, I/O organization,
microprogramming, pipelining, instruction level parallelism.
Operating systems - Memory management, processor management,
critical section problem, deadlocks, device management, file systems.
Formal languages and automata theory - Finite automata and regular
expressions, pushdown automata, context-free grammars, Turing
machines, elements of undecidability.
Principles of Compiler Construction - Lexical analyzer, parser, syntax-
directed translation, intermediate code generation.
Database management systems - Relational model, relational algebra,
relational calculus, functional dependency, normalization (up to 3rd
normal form).
Computer networks - OSI, LAN technology - Bus/tree, Ring, Star; MAC
protocols; WAN technology - circuit switching, packet switching; data
communications - data encoding, routing, flow control, error
detection/correction, Internetworking, TCP/IP networking including IPv4.
4
Switching Theory and Logic Design - Boolean algebra, minimization of
Boolean functions, combinational and sequential circuits – synthesis and
design.
5
Sample Questions
GROUP A
Mathematics
A1. If 1, a1, a2,…, an-1 are the n roots of unity, find the value of
(1 - a1) (1 - a2)…(1 - an-1).
A2. Let
S = {( a1 , a 2 , a3 , a 4 ) : ai ∈ ℜ , i = 1, 2, 3, 4 and a1 + a 2 + a3 + a 4 = 0}
and
Γ = {( a1 , a 2 , a 3 , a 4 ) : a i ∈ ℜ , i = 1, 2 , 3, 4 and a1 − a 2 + a 3 − a 4 = 0}.
Find a basis for S ∩ Γ .
A3. Provide the inverse of the following matrix:
c0 c1 c2 c3
c 2 c3 c0 c1
c − c c1 − c0
3 2
c − c − c2
1 0 c3
1+ 3
Where c 0 = , c1 = 3 + 3 , c 2 = 3 − 3 , and c 3 = 1 − 3 .
4 2 4 2 4 2 4 2
(Hint: What is c0 + c1 + c 2 + c3 ?)
2 2 2 2
A4. For any real number x and for any positive integer n show that
6
A7. Find the following limit:
1 1 1
lim + + ... +
n →∞
n +1 n2 + 2 n2 + n
2
A8. Find the total number of English words (all of which may not have
proper English meaning) of length 10, where all ten letters in a word
are not distinct.
a1 a 2 a
A9. Let a0 + + + ..... + n = 0, where ai’s are some real constants.
2 3 n +1
Prove that the equation a 0 + a 1 x + a 2 x + ... + a n x = 0 has at least one
2 n
7
Let f : [0,1] → [-1,1] be such that f(0) = 0 and f(x) = sin x for x > 0.
1
A14.
Is it possible to get three sequences {an}, {bn}, {cn} satisfying all
the three properties P1, P2 and P3 stated below? If so, provide an
example sequence for each of the three sequences. Otherwise,
prove that it is impossible to get three such sequences.
is divisible by 11.
A16. Let a < b < c < d be four real numbers, such that all six pairwise
sums are distinct. The values of the smallest four pairwise sums are
1, 2, 3, and 4 respectively. What are the possible values of d?
Justify your answer.
Let a set of ten distinct elements b1, b2, …, b10 be chosen from A
such that exactly two elements are chosen from each row and
exactly one from each column. Show that b1 + b2 + … + b10 is
always equal to 255.
8
GROUP B
Mathematics
x n +3
M1. Let 0 < x1 < 1. If xn+1 = , n = 1,2,3, …
3x n + 1
5x n +3
(i) Show that xn+2 = , n = 1,2,3, …
3x n + 5
(ii) Hence or otherwise, show that lim xn exists.
n→∞
M3. Let
( x − 1) ( x 4 + 4 x + 7) if x is rational.
f ( x) =
(1 − x) ( x + 4 x + 7)
4
if x is irrational.
M4. Let h be any fixed positive real number. Show that there is no
differentiable function f : ℜ → ℜ satisfying both the following
conditions:
(a) f ′(0) = 0.
(b) f ′( x) > h for all x > 0.
M5. Find the volume of the solid given by 0 ≤ y ≤ 2 x , x + y ≤ 4 and
2 2
0≤ z≤ x.
9
M6. (a) Let A, B and C be 1×n, n×n and n×1 matrices respectively. Prove
or disprove: Rank(ABC) ≤ Rank(AC).
(b) Let S be the subspace of R4 defined by
S = {(a1, a2, a3, a4) : 5a1 - 2a3 -3a4 = 0}.
Find a basis for S.
d2y 2 dy
2
( x + 1) = 2 x .
dx dx
a 0 0
0 a 0
b c a
10
(b) Find out the number of skew-symmetric matrices this basis
must contain.
11
M14. Let A be any n × n real symmetric positive definite matrix. Let λ be
the largest eigenvalue of A.
(a) Show that || Ax ||≤ λx, ∀ || x ||≠ 0 .
|| Ax ||
(b) Find Sup|| x|| ≠0 .
|| x ||
Statistics
S1. (a) X and Y are two independent and identically distributed random
variables with Prob[X = i] = pi, for i = 0, 1, 2, ……… Find
Prob[X < Y] in terms of the pi values.
(b) Based on one random observation X from N(0, σ2), show that
√π/2 |X| is an unbiased estimate of σ.
S2. (a) Let X0, X1, X2, … be independent and identically distributed
random variables with common probability density function f. A
random variable N is defined as
N = n if X1 ≤ X 0 , X 2 ≤ X 0 , , X n−1 ≤ X 0 , X n > X 0 , n = 1, 2, 3,
12
choosing a number randomly from A using the given coin, such
1
that P({1}) = P({2}) = P({3}) = . Justify your answer.
3
S4. (a) Let X 1 , K , X n be the iid U (θ − 1, θ + 1) where θ is an unknown
real number. Show that for any real number α ∈ (0,1) ,
α ( X ( n ) − 1) + (1 − α )( X (1) + 1)
is a maximum likelihood estimator for the unknown θ , where
X (1) and X ( n ) are the smallest and largest sample observations
respectively.
(b) Let X 1 , K , X n be iid N ( µ ,1) where µ is only known to belong
to the set of all integers. Find a maximum likelihood estimator
for µ based on X 1 , K , X n .
S6. Consider a randomized block design with two blocks and two
treatments A and B. The following table gives the yields:
Treatment A Treatment B
Block 1 a b
Block 2 c d
13
S7. Let X be a discrete random variable having the probability mass
function
p(x) = Λx(1- Λ)1-x, x = 0, 1,
where Λ takes values ≥ 0.5 only. Find the most powerful test, based
1 2
on 2 observations, for testing H0 : Λ = against H1 : Λ = , with
2 3
level of significance 0.05.
S9. Let X=(X1,…, Xn) be a sample from the uniform distribution on (0,
θ). Show the following:
(a) For testing H0: θ ≤θ0 against H1: θ ≥θ0, any test is UMP at level
α for which Eθ 0 (φ ( X )) = α , Eθ 0 (φ ( X )) ≤ α for θ ≤ θ 0 , and φ(x) =
1 when max ( x1 ,...., x n ) > θ0.
14
(b) For testing H0: θ = θ0 against H1: θ ≠ θ0, a unique UMP test
exits, and is given by φ(x) = 1 when max ( x1 ,...., x n ) > θ0 or max
( x1 ,...., x n ) ≤ θ0 α 1 / n and φ(x) = 0 otherwise.
y1 y2
2 + if the sample consists of units 1 and 2
2
y1 2 y3
(b) Yˆ = + if the sample consists of units 1 and 3
2 3
y2 +
y3
if the sample consists of units 2 and 3
2 3
(i) Show that both estimators are unbiased for the population mean.
(ii) Show that Var(Yˆ ) < Var( y ) if y 3(3 y 2 − 3 y1 − y 3) > 0.
(Hint: Suppose x is the sample mean for a simple random sample
without replacement of size n from a population of size N with
population unit values x1 , K , x N . Then
N 2
N −n
∑ (x i
− X)
Var( x ) = i =1
,
Nn N −1
N
∑x i
where X = i =1
.)
N
15
(b) Given α (0 < α < 1), use (a) to obtain a (1-α) confidence interval
for θ.
S12. Let X1, X2,…,Xn (Xi= (xi1, xi2, …, xip), i=1, 2, …, n) be n random
samples from a p-variate normal population with mean vector µ and
covariance matrix I.
1 n
xj =∑ xij ,1 ≤ j ≤ p.
n i =1
Obtain the distribution of l Sl where l ∈ ℜ , l ≠ 0.
' k
µ1 σ 11 σ 12 σ 13
µ~ = µ 2 , ∑ = σ 21 σ 22 σ 23
µ σ
3 31 σ 32 σ 33
Show that E(X1,X2,X3) = µ1µ 2 µ 3 + µ1σ 23 + µ 2σ 31 + µ 3σ 12 .
(b) Suppose X = (X1, X2, X3, X4)T ∼ N4( 0, ∑ ), where ∑ = ((σ ij )).
~
16
Physics
P2. (a) Consider a material that has two solid phases, a metallic phase
and an insulator phase. The phase transition takes place at the
temperature T0 which is well below the Debye temperature for
either phase. The high temperature phase is metastable all the
way down to T = 0 and the speed of sound, cs, is the same for
each phase. The contribution to the heat capacity coming from
the free electrons to the metal is
k
C e = ρ eVγ T , γ = 3π 2
4T F
17
P3. (a) A particle of mass m moves under a force directed towards a
fixed point and this force depends on the distance from the fixed
point. Show that
(i) the particle will be constrained to move in a plane, and
(ii) the areal velocity of the particle is constant.
(b) If the force F varies as the inverse of the square of the distance,
show that
∇ × F = 0.
Discuss its implications.
(c) Assuming the trajectory of planets to be circular, deduce the
force law from Kepler's third law.
P4. (a) A mass m is attached to a massless spring of spring constant K via
a frictionless pulley of radius R and mass M as shown in following
figure. The mass m is pulled down through a small distance x and
released, so that it is set into simple harmonic motion. Find the
frequency of the vertical oscillation of the mass m.
18
potential at that point due to the mass of the sphere.
(b) In a Millikan's oil drop experimental setup, two small negatively
charged spherical oil droplets having radii 3r and 5r were
allowed to fall freely in the closed chamber filled with air. The
downward terminal velocities attained by them were v1 and v2
respectively. Subsequently, under the action of a strong electric
field, the droplets attained upward terminal velocities v1/6 and
v2/20 respectively. Neglecting the bouyant force of air and
assuming the charges to be uniformly distributed over the surface
of the droplets, compare their surface charge densities.
P6. (a) A dielectric sphere of radius R and permittivity ε carries a
volume charge density ρ(r) = kr (where k is a constant). Deduce an
expression for the energy of the configuration.
(b) Two spherical cavities of radii a and b are hollowed out from
the interior of a neutral conducting sphere of radius R. Two point
charges of magnitude qa and qb are now placed at the centres of the
two cavities as shown in the figure.
P7. A train passes a platform with velocity v. Two clocks are placed on
the edge of the platform separated by a distance L and synchronized
relative to platform inertial system. Clock 1 reads time t1 when it
coincides with the front of the train and clock 2 reads time t2 when it
coincides with the rear of the train. Answer the following questions
relative to an observer on the train.
19
(b) What is the reading of clock 2 when the clock1 coincides with
the front of the train?
(c) What is the time interval between the two end events?
P8. (a) A perfect gas expands in a manner such that its elasticity is
always equal to the sum of the isothermal and adiabatic
elasticity. Find its specific heat under this condition in terms of
the specific heats at constant pressure and constant volume.
P9. In the circuit shown below, the peak current flowing through the
different branches are indicated. Derive the value of the total
power delivered by the source.
P10. Two heavy bodies A and B , each having charge − Q , are kept
rigidly fixed at a distance 2a apart. A small particle C of mass m
and charge + q ( << Q ), is placed at the midpoint of the straight
line joining the centers of A and B . C is now displaced slightly
along a direction perpendicular to the line joining A and B , and
then released. Find the period of the resultant oscillatory motion of
C , assuming its displacement y << a .
If instead, C is slightly displaced towards A , then find the
instantaneous velocity of C , when the distance between A and C
a
is .
2
20
P11. An elementary particle called ∑-, at rest in laboratory frame,
decays spontaneously into two other particles according to
Σ− → π − + n . The masses of ∑-, π- and n are M1, m1, and m2
respectively.
(a)How much kinetic energy is generated in the decay process?
(b)What are the ratios of kinetic energies and momenta of π and
−
n?
P12. Consider the following truth table where A, B and C are Boolean
inputs and T is the Boolean output.
A B C T
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Express T in a product-of-sum form and hence, show how T can be
implemented using NOR gates only.
(b) Find the value of R and the current flowing through R shown
in the figure when the current is zero through R′.
21
τ B(τ )
P14. A gas obeys the equation of state P = + where B(τ ) is a
V V2
function of temperature τ only. The gas is initially at temperature
τ and volume V0 and is expanded isothermally and reversibly to
volume V1 = 2V0 .
(a) Find the work done in the expansion.
(b) Find the heat absorbed in the expansion.
∂S ∂P
(Hint: Use the relation ∂V = ∂τ where the symbols have
τ V
their usual meaning.)
22
P16. (a) A particle of mass m is moving in a plane under the action of an
attractive force proportional to 1/r2, r being the radial distance of
the particle from the fixed point. Write the Lagrangian of the
system and using the Lagrangian show that the areal velocity of the
particle is conserved (Kepler's second law).
Computer Science
A → Bb A→a
B →Cc B→b
C → Aa C→c
23
C2. The following functional dependencies are defined on the relation
ℜ( A, B, C , D, E , F ) :
{ A → B, AB → C, BC → D, CD → E, E → A }
(c) Let the relation have 5000 tuples with 10 tuples/page. In case of
a hashed file, each bucket needs 10 pages. In case of B+ tree,
the index structure itself needs 2 pages. If it takes 25 msecs. to
read or write a disk page, what would be the disk access time
for answering the above queries?
(d) Relation R(A,B,C) supports the following functional
dependencies:
A → B, B → C and C→A.
24
(i) Identify the key attributes.
(ii) Explain whether R is in BCNF.
(iii) If R is not in BCNF, decompose to create a set of
normalized relations satisfying BCNF.
(iv) If R does not support the functional dependencies B → C,
but the other two are maintained, would R be in BCNF? If not,
decompose R to normalized relations satisfying BCNF.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and
1000 cylinders. The speed of rotation of the disk is 6000 rpm.
The average seek time is 10 millisecs. A file of size 50 MB is
written from the beginning of a cylinder and a new cylinder
will be allocated only after the first cylinder is totally occupied.
i) Find the maximum transfer rate.
ii) How much time will be required to transfer the file of 50
MB written on the disk? Ignore the rotational delay but not
the seek time.
25
Suppose that we model the crossing as follows:
- each vehicle is modeled by a process,
- the crossing is modeled as a shared data structure. Assume that
the vehicles can only move straight through the intersection (no
left or right turns). Using read-write locks (or any standard
synchronization primitive), you have to device a
synchronization scheme for the processes. Your scheme should
satisfy the following criteria:
i) prevent collisions,
ii) prevent deadlock, and
iii) maximize concurrency but prevent indefinite waiting
(starvation).
Write down the algorithm that each vehicle must follow in order
to pass through the crossing. Justify that your algorithm satisfies
the given criteria.
26
(ii) What is the rate at which application data is transferred to
host HZ? Ignore errors, acknowledgements, and other
overheads.
C8. Consider a binary operation shuffle on two strings, that is just like
shuffling a deck of cards. For example, the operation shuffle on
strings ab and cd, denoted by ab || cd, gives the set of strings
{abcd, acbd, acdb, cabd, cadb, cdab}.
27
with only three G gates and one OR gate.
(ii) Can all switching functions be realized with {G, OR}
logic set?
28
(d) Express the following numbers in IEEE 754-1985 single
precision floating-point format:
(i) -0 (ii) 2.5 × 2-130 (iii) 230 (iv) 0.875 (v) (-3)1/8.
C14. (a) The order of a regular language L is the smallest integer k for
which Lk = Lk+1, if there exists such a k, and ∞ otherwise.
(i) What is the order of the regular language a + (aa)(aaa)*?
(ii) Show that the order of L is finite if and only if there is an
integer k such that Lk = L*, and that in this case the order of L
is the smallest k such that Lk = L*.
C15. (a) You are given an unordered sequence of n integers with many
duplications, such that the number of distinct integers in the
sequence is O(log n). Design a sorting algorithm and its
necessary data structure(s), which can sort the sequence using
at most O(n log(log n)) time. (You have to justify the time
complexity of your proposed algorithm.)
(b) Let A be a real-valued matrix of order n x n already stored in
memory. Its (i, j)-th element is denoted by a[i, j]. The
elements of the matrix A satisfy the following property:
Let the largest element in row i occur in column li. Now, for
any two rows i1, i2, if i1 < i2, then li1 ≤ li2 .
29
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12
(a)
Row I l(i)
1 2
2 3
3 3
4 4
5 5
(b)
30
C16. You are given the following file abc.h:
#include <stdio.h>
#define SQR(x) (x*x)
#define ADD1(x) (x=x+1)
#define BeginProgram int main(int ac,char *av[]){
#define EndProgram return 1; }
For each of the following code fragments, what will be the output?
(i) #include "abc.h"
main()
{ int y = 4; printf("%d\n", SQR(y+1)); }
(ii) #include "abc.h"
BeginProgram
int y=3; printf("%d\n", SQR(ADD1(y)));
EndProgram
31
(b) A composite shaft of Aluminium and Brass is rigidly supported
at the ends A and C, as shown in the figure below. The shaft is
subjected to a shearing stress by the application of a torque T.
Calculate the ratio of lengths AB : BC if each part of the shaft is
stressed to its maximum limit (beyond which the composite shaft
will break). Assume the maximum shear stress of Brass and
Aluminium to be 560 kg/cm2 and 420 kg/cm2 respectively. Also
assume that the modulus of rigidity of Brass is twice that of
Aluminium.
E3. Find the acceleration of the block of mass M in the situation shown
below. The coefficient of friction between the blocks is µ1 and that
between the bigger block and the ground is µ2.
E5. The truss shown in the figure rotates around the pivot O in a vertical
plane at a constant angular speed ω. Four equal masses (m) hang from
32
the points B, C, D and E. The members of the truss are rigid,
weightless and of equal length. Find a condition on the angular speed
ω so that there is compression in the member OE.
E6. If the inputs A and B to the circuit shown below can be either 0 volt
or 5 volts,
(i) what would be the corresponding voltages at output Z, and
(ii) what operation is being performed by this circuit ?
Assume that the transistor and the diodes are ideal and base to
emitter saturation voltage = 0.5 volts.
33
to become 12 cm and 13 cm of Hg, respectively. Assume that the
coefficient of viscosity η of oxygen is 0.000199 cgs unit.
300 × 3.6
E8. (a) Ice in a cold storage melts at a rate of kg/hour when the
80 × 4.2
external temperature is 27oC. Find the minimum power output of
the refrigerator motor, which just prevents the ice from melting.
(Latent heat of fusion of ice = 80 cal/gm.)
34
E12. A proton of velocity 107 m/s is projected at right angles to a uniform
magnetic induction field of 0.1 w/m2. How much is the path of the
particle deflected from a straight line after it has traversed a distance
of 1 cm? How long does it take for the proton to traverse a 900 arc?
E13. (a) State the two necessary conditions under which a feedback
amplifier circuit becomes an oscillator.
(b) A two-stage FET phase shift oscillator is shown in the diagram
below.
E14. A circular disc of radius 10cm is rotated about its own axis in a
uniform magnetic field of 100 weber/m2, the magnetic field being
perpendicular to the plane of the disc. Will there be any voltage
developed across the disc? If so, then find the magnitude of this
voltage when the speed of rotation of the disc is 1200 rpm.
35
E16. A d.c. shunt motor running at a speed of 500rpm draws 44KW
power with a line voltage of 220V from a d.c. shunt generator. The
field resistance and the armature resistance of both the machines are
55 Ω and 0.025 Ω respectively. However, the voltage drop per brush
is 1.05V in the motor, and that in the generator is 0.95V. Calculate
(a) the speed of the generator in rpm, and
(b) the efficiency of the overall system ignoring losses other
than the copper-loss and the loss at the brushes.
36
(b) Find the open-circuit transfer impedance of the lattice shown in
the figure below and determine the condition for having no zeros in
the right-half plane, i.e., for positive frequencies.
E21. A logic circuit operating on Binary Coded Decimal (BCD) digits has
four inputs X1, X2, X3, and X4, where X1X2X3X4 represents a BCD
digit. The circuit has two output lines Z1 and Z2. Output Z1 is 1 only
when the decimal digit corresponding to the inputs X1, X2, X3, X4 is
0 or a power of 2. Output Z2 is 1 only when the decimal digit
corresponding to the inputs is 1 or a power of 3. Find a minimum
cost realization of the above circuit using NAND gates.
37
E23. Write a C program to generate a sequence of positive integers
between 1 and N, such that each of them has only 2 or/and 3 as
prime factors. For example, the first seven elements of the sequence
are: 2, 3, 4, 6, 8, 9, 12. Justify the steps of your algorithm.
E24. Design a circuit using the module, as shown in the figure below, to
compute a solution of the following set of equations:
3x + 6y – 10 = 0
2x – y – 8 = 0
A module consists of an ideal OP-AMP and 3 resistors, and you may
use multiple copies of such a module. Voltage inverters and sources
may be used, if required.
38
Test Code: CS (Short answer type) 2012
The selection test for M.Tech. in Computer Science will consist of two parts:
• Group A : A test for all candidates in analytical ability and mathematics primarily at the B.Sc.
(pass) level, carrying 30 marks.
• Group B: A test, divided into several sections, carrying equal marks of 70 in Mathematics,
Statistics, and Physics primarily at the B. Sc. (Hons.) level, and in Computer Science, and En-
gineering and Technology primarily at the B.Tech. level. A candidate has to answer questions
from only one of these sections according to his/her choice.
The syllabus and sample questions for the MIII test are available separately. The syllabus and sample
questions for the CS test are given below.
Note:
1. Not all questions in the sample set are of equal difficulty. They may not carry equal marks in
the test.
2. Each of the tests, MIII and CS, will have individual qualifying marks.
SYLLABUS for Test CS
Group A
Elements of set theory. Permutations and combinations. Functions and relations. Theory of equa-
tions. Inequalities.
Limits, continuity, sequences and series, differentiation and integration with applications, maxima-
minima.
Elementary Euclidean geometry and trigonometry.
Elementary number theory, divisibility, congruences, primality.
Determinants, matrices, solutions of linear equations, vector spaces, linear independence, dimen-
sion, rank and inverse.
Group B
Mathematics
1
improper integrals, double and multiple integrals and applications, sequences and series of func-
tions, uniform convergence.
Linear algebra - vector spaces and linear transformations, matrices and systems of linear equations,
characteristic roots and characteristic vectors, Cayley-Hamilton theorem, canonical forms, quadratic
forms.
Graph Theory - connectedness, trees, vertex coloring, planar graphs, Eulerian graphs, Hamiltonian
graphs, digraphs and tournaments.
Abstract algebra - groups, subgroups, cosets, Lagrange’s theorem, normal subgroups and quotient
groups, permutation groups, rings, subrings, ideals, integral domains, fields, characteristics of a
field, polynomial rings, unique factorization domains, field extensions, finite fields.
Differential equations - solutions of ordinary and partial differential equations and applications.
Statistics
Notions of sample space and probability, combinatorial probability, conditional probability, Bayes’
theorem and independence.
Random variable and expectation, moments, standard univariate discrete and continuous distribu-
tions, sampling distribution of statistics based on normal samples, central limit theorem, approxima-
tion of binomial to normal, Poisson law.
Multinomial, bivariate normal and multivariate normal distributions.
Descriptive statistical measures, product-moment correlation, partial and multiple correlation.
Regression - simple and multiple.
Elementary theory and methods of estimation - unbiasedness, minimum variance, sufficiency, max-
imum likelihood method, method of moments, least squares methods.
Tests of hypotheses - basic concepts and simple applications of Neyman-Pearson lemma, confidence
intervals.
Tests of regression, elements of non-parametric inference, contingency tables and Chi-square, ANOVA,
basic designs (CRD/RBD/LSD) and their analyses, elements of factorial designs.
Conventional sampling techniques, ratio and regression methods of estimation.
Physics
2
Nuclear and particle physics - Basics of nuclear properties, nuclear forces, nuclear structures, nu-
clear reactions, interaction of charged particles and e-m rays with matter, theoretical understanding
of radioactive decay, particle physics at the elementary level.
Electronics - semiconductor physics, diode as a circuit element, clipping, clamping, rectification,
Zener regulated power supply, transistor as a circuit element, CC CB CE configuration, transistor as
a switch, OR and NOT gates feedback in amplifiers.
Operational Amplifier and its applications - inverting, noninverting amplifiers, adder, integrator, dif-
ferentiator, waveform generator comparator and Schmidt trigger.
Digital integrated circuits - NAND, NOR gates as building blocks, XOR gates, combinational cir-
cuits, half and full adder.
Computer Science
Data structures - array, stack, queue, linked list, binary tree, heap, AVL tree, B-tree.
Programming languages - Fundamental concepts abstract data types, procedure call and parameter
passing, languages like C and C++.
Design and analysis of algorithms Asymptotic notation, sorting, selection, searching.
Computer organization and architecture - Number representation, computer arithmetic, memory or-
ganization, I/O organization, microprogramming, pipelining, instruction level parallelism.
Operating systems - Memory management, processor management, critical section problem, dead-
locks, device management, file systems.
Formal languages and automata theory - Finite automata and regular expressions, pushdown au-
tomata, context-free grammars, Turing machines, elements of undecidability.
Principles of Compiler Construction - Lexical analyzer, parser, syntax-directed translation, interme-
diate code generation.
Database management systems - Relational model, relational algebra, relational calculus, functional
dependency, normalization (up to 3rd normal form).
Computer networks - OSI, LAN technology - Bus/tree, Ring, Star; MAC protocols; WAN tech-
nology - circuit switching, packet switching; data communications - data encoding, routing, flow
control, error detection/correction, Internetworking, TCP/IP networking including IPv4.
Switching Theory and Logic Design - Boolean algebra, minimization of Boolean functions, combi-
national and sequential circuits synthesis and design.
Moments of inertia, motion of a particle in two dimensions, elasticity, friction, strength of materials,
surface tension, viscosity and gravitation.
Laws of thermodynamics and heat engines.
Electrostatics, magnetostatics and electromagnetic induction.
Magnetic properties of matter - dia, para and ferromagnetism.
Laws of electrical circuits - RC, RL and RLC circuits, measurement of current, voltage and resis-
tance.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
p-n junction, bipolar & FET devices, transistor amplifier, oscillator, multi-vibrator, operational am-
plifier.
Digital circuits - logic gates, multiplexer, de-multiplexer, counter, A/D and D/A converters.
Boolean algebra, minimization of switching functions, combinational and sequential circuits.
C Programming language.
3
SAMPLE QUESTIONS
Group A
A1. Imagine a cubic array made up of an n × n × n arrangement of unit cubes: the cubic array is n
cubes wide, n cubes high and n cubes deep. A special case is a 3 × 3 × 3 Rubik’s cube, which
you may be familiar with. How many unit cubes are there on the surface of the n × n × n
cubic array?
A2. The integers 1, 2, . . . , 10 are circularly arranged in an arbitrary order. Show that there are
always three successive integers in this arrangement, whose sum is at least 17.
A3. A piece of wire 16 inches long is cut into two pieces. One piece is bent to form a square and
the other is bent to form a circle. Where should the cut be made in order to minimize the total
area of the square and the circle?
A5. Prove that the positive integers that cannot be written as sums of two or more consecutive
integers are precisely the powers of 2.
4
Group B
Mathematics
(b) If (2x − 1)(f (x) − x) ≥ 0, ∀ x ∈ [0, 1], show that x0 as in part 1(a) cannot be less than
or equal to 12 .
(c) Define x1 such that Z Z
x1 1
1
f (x)x2 dx = f (x)x2 dx.
0 3 0
2. (a) Let ( )
∞
X xi
A= : xi = 0 or 2, ∀i = 1, 2, · · · .
i=1
3i
3
Show that 4 ∈ A.
(b) For two real numbers a, b (both greater than 1), evaluate
à 1 1
!n
an + bn
lim .
n→∞ 2
x21 + (x2 − x1 )2 + (1 − x2 )2
f (x1 , x2 ) = .
max{x1 , x2 − x1 , 1 − x2 }
Determine the maximum value of f (x1 , x2 ) and give all possible values of the pair
(x1 , x2 ) for which this maximum value is achieved.
(b) Suppose that f : R → R is a monotonic function such that
f (2x)
lim = 1.
x→∞ f (x)
Show that
f (cx)
lim =1
x→∞ f (x)
for any c > 0.
4. (a) Let G be a simple graph with 23 vertices. The degree of every vertex is at least 11.
(i) Can G be a regular graph of degree 11? Justify your answer.
(ii) Argue whether G can be disconnected.
5
(b) Consider a simple connected planar graph with 10 vertices and 17 edges. Show that,
using two colours, its vertices cannot be properly coloured, i.e., no two neighbouring
vertices have the same colour.
(c) In how many ways can one distribute 8 identical chocolates among 5 children - A, B, C,
D and E?
5. (a) Given three matrices Am×n , Bn×k , Ck×p , the product A ∗ B ∗ C can be computed in
two ways:
(i) (A ∗ B) ∗ C, and
(ii) A ∗ (B ∗ C).
Establish the conditions on m, n, k and p under which (i) requires fewer arithmetic
operations (additions and multiplications) than (ii).
(b) Let V be the linear space of all functions of the form
6. (a) Is the polynomial x10 +x5 +1 irreducible over Q (the field of rational numbers)? Justify
your answer.
(b) (i) Consider the additive group Z24 (the set of integers modulo 24). What are the orders
of the elements 4, 12 and 16 in Z24 ?
(ii) Let (G, ∗) be a finite abelian group and ◦(g) denote the order of the element g in
G. Consider u, v ∈ G such that ◦(u) = m and ◦(v) = n. If the greatest common
divisor gcd(m, n) = 1, then derive the order of u ∗ v.
(iii) For the group G in (ii) above, if gcd(m, n) = d > 1, then find an element in G
whose order is lcm(m, n). Justify your answer. lcm denotes the least common
multiple.
Statistics
1. (a) A passenger airline company has found from past experience that 20% of the customers
who buy tickets for a flight do not show up for the journey. The company wishes to
ensure that a particular flight is at least 95% full with a probability of 0.9. How many
tickets should it sell if the capacity of the flight is 300?
(b) 18 boys and 2 girls are made to stand in a line in a random order. Let X be the number
of boys standing between the girls. Find
(i) P (X = 5),
(ii) E(X).
6
2. (a) The mean µ of a normal population is unknown, but its standard deviation σ is known.
The length of a 100(1 − 2α)% confidence interval for µ based on a random sample of
size n from the population is found to be equal to L. By what factor should n be changed
to ensure that a 100(1 − α)% confidence interval for µ will be of length L/2?
(b) If X1 , X2 , . . . , Xn are independent and identically distributed random variables from
the exponential distribution with mean θ > 0, find the most powerful test based on them
for testing H0 : θ = 2 against H1 : θ = 1. Find the power of the test.
3. (a) X1 and X2 are independent and identically distributed random variables from a Bernoulli
distribution with parameter θ. Is the statistic X1 + X22 sufficient for θ? Justify your an-
swer.
(b) Let X1 , X2 , . . . , Xn be independent random variables, identically distributed as
½ 1
3θ if − θ ≤ x ≤ 2θ,
g(x) =
0 otherwise.
where β and σ are unknown parameters. Find the values of c1 , c2 , c3 and c4 for which
4
X
ck Yk
k=1
is unbiased for β and has the smallest variance among all linear unbiased estimators for
β.
5. (a) X is a random variable having a normal distribution with mean 0 and variance 25. Let
Y be another random variable, independent of X, taking values −1 and +1 with equal
probability. Define
X X
Z = XY + and W = XY − .
Y Y
¡ Z+W ¢2
Find the probability distributions of (i) Z and (ii) 10 .
(b) Let X1 and X2 be independent samples from the uniform distribution over (0, 1). Find
the probability distribution of the geometric mean of X1 and X2 .
6. (a) A researcher wishes to conduct an experiment to compare the effects of 4 different treat-
ments. He is given 20 experimental units for this purpose, which are not entirely ho-
mogeneous. Assuming that there is only one significant source of heterogeneity among
the units, suggest a suitable experimental design, with proper justification. Also give the
analysis of variance for the design.
(b) A population contains 10 units, labeled U1 , U2 , · · · , U10 . For Ui , the value of a character
Y under study, is Yi , 1 ≤ i ≤ 10. In order to estimate the population mean, Ȳ , a sample
of size 4 is drawn in two steps as follows:
7
(I) A simple random sample of size 2 is drawn without replacement from the units
U2 , U3 , . . . , U9 ;
(II) The sample drawn in step (I) is augmented by the units U1 and U10 .
Based on this sample, suggest an unbiased estimator of Ȳ and obtain its variance.
Physics
1. (a) An npn transistor shown in the figure below, is used in common-emitter mode with
β = 49, Vcc = 10 V , and RL = 2 KΩ. A 100 KΩ resistor RB is connected between
the collector and the base of the transistor. Calculate
(i) the quiescent collector current, and
(ii) the collector to emitter voltage drop between points A and B.
Assume base to emitter voltage drop is 0.7 V .
(b) The set of Boolean functions {OR, N OT } is functionally complete, i.e., the set can
implement any Boolean function. Prove algebraically that the set {XOR, AN D} also
forms a functionally complete set of operations.
2. (a) Find the amount of pressure that is to be applied to change the boiling point of water by
3◦ K, using the information given below:
Latent heat of vaporization = 539 cal/gm; specific volume of
vapor= 1677 cc/gm; specific volume of water = 1 cc/gm;
T = 371◦ K .
(b) Sketch the isotherms for a gas obeying Van der Waal’s equations of state and discuss the
phase transition.
(c) A classical system of N distinguishable non-interacting particles, each of mass m, is
placed in a three-dimensional harmonic well having potential energy
x2 + y 2 + z 2
U= ,
2V 2/3
where V is a parameter. Find the partition function and Helmholtz free energy.
3. (a) Show that the rotational frequency spectrum of a diatomic molecule consists of equally
spaced lines separated by an amount ∆r = 4πh2 I , where I is the moment of inertia of
the molecule.
−
→ − →
(b) Express L · S in terms of J, L, and S, where the symbols carry their usual meaning.
−
→ → −
Hence, for L = 1, S = 12 , obtain the possible values of L · S .
8
4. (a) Two spheres, each of radius R, carry uniform charge densities +q and −q respectively.
−
→
The spheres are placed such that they partially overlap each other (see figure). D denotes
the vector from the centre of the positive charged sphere to the centre of the negative
charged sphere. Derive the electrostatic field at any point in the shaded (overlapping)
region.
(b) The potential V0 (θ) = κ sin2 (θ/2) ( κ is a constant), is specified on the surface of a
hollow sphere of radius R. Find the potential inside the sphere.
(c) The electric field of an electromagnetic wave in vacuum is given by:
2π
Ex = 0, Ey = 30 cos(2π 108 t − x), Ez = 0.
3
Here E is in V olts/metre, t is in seconds and x is in metres. Determine
(i) the frequency of the wave, and
ii) the direction of propagation of the wave.
5. (a) From the reaction Π− + p → n + γ, determine the possible values of the spin of a Π−
meson.
(b) Explain why the reaction Σ0 → Λ0 + γ is observed but not the decays Σ0 → p + Π− or
Σ 0 → n + Π0 .
(c) Determine the mass difference between two mirror nuclei which have N and Z differing
by one unit.
(All the symbols carry their usual meaning in the above cases).
−
→ −
→r be a central force per unit mass.
6. (a) Let F = |k−→
r |3
(i) Show that for a particle of mass m moving under this force F , the angular momen-
tum is conserved.
(ii) Write the Lagrangian for the above particle.
(b) The mean distance of Mars from the Sun is 1.5 times that of the Earth from the Sun.
Find the time of revolution of Mars about the Sun with respect to that of the Earth about
the Sun.
(c) A rocket when moving parallel to a long platform measures the length of the platform to
be 9L
10 , where L is the length measured by a stationary observer. Find the time taken by
the rocket to cross the platform.
9
Computer Science
1. (a) Given the values of two nodes in a binary search tree, write an algorithm to find their least
(nearest) common ancestor. For example, in the figure below, the least common ancestor
of the nodes 4 and 14 is 8. Your algorithm should take care of boundary conditions.
(b) Given a singly-linked list, devise a time and space efficient algorithm to find the mth
element from the end of the list.
If m = 0, then your algorithm should return the last element of the list. It should also
take care of boundary conditions. Analyze the time complexity of your algorithm.
[N OTE: An algorithm that has minimum additional storage overhead and does not make redundant
passes over the list will score full credit. Can you do it with constant additional space?]
int main()
{
int a=3;
int b=2;
printf("Ans: %d\n", MUL (MUL(a+1,b), Pow(b+1)));
return 0;
}
(b) Consider the declaration below:
typedef char *Str_typed;
#define Str_defined char*
Str_typed s1, s2;
Str_defined s3, s4;
Which one of the following statements is correct?
I. s1, s2, s3 and s4 are character pointers
10
II. s1, s2, s3 and s4 are characters
III. s1, s2, s3 are character pointers while s4 is a character
IV. None of the above
(c) Consider the following list of parameter passing conventions in any programming lan-
guage.
I. Call by name
II. Call by value
III. Call by reference
If the following piece of code in a certain programming language printed 16 for j, which
of the above parameter passing conventions may have been used? Justify your answer.
program test (input, output);
var i, j;
begin (main)
i = 2;
j = 3;
calc (i, j);
print (j);
end (main)
[ NOTE : You will get partial credit if the time complexity of your algorithm is quadratic or more
in the length of the string.]
3. (a) A processor chip is used for applications in which 30% of execution time is spent on
floating point additions, 20% on floating point multiplications, and 15% on floating point
divisions. To enhance the performance of the processor, a design team examines the
following three options, each costing about the same in design effort and manufacturing.
I. The floating point adder is made four times faster.
II. The floating point multiplier is made three times faster.
III. The floating point divider is made twenty times faster.
If only two of the above options can be implemented, which one should be discarded
and why?
(b) Consider the following grammar with two missing productions:
11
S → aS | ... (1)
A → ... (2) | ²
X → cS | ²
Y → dS | ²
Z → eS
Reconstruct the grammar by filling in the missing productions (1) and (2), using the
F irst and F ollow sets for this grammar given below:
First Follow
S {a,b,c,d,e} {$} ∪ F ollow(X) ∪ F ollow(Y) ∪ F ollow(Z)
A {c,d,e,²} {b}
X {c,²} (F irst(Y) \ ²) ∪ F irst(Z)
Y {d,²} F irst(Z)
Z {e} F ollow(A)
a {a} F irst(S)
b {b} F ollow(S)
c {c} F irst(S)
d {d} F irst(S)
e {e} F irst(S)
Note that you can define only two productions. (Recall that X → A | B represents two
productions). Justify your answer.
4. (a) Consider the languages L1 , L2 ⊆ Σ∗ , where Σ = {a, b, c}. Define
Which of the following regular expressions represents all possible sequences of steps
taken by this program? Justify your answer.
I. A(T BI)∗
II. AT + B ∗ I ∗
III. AT (BIT )+
12
IV. AT (BIT )∗
V. A(T BI)+
5. (a) Consider a relation R(ABCD) as follows:
A B C D
A1 B1 C1 D1
A1 B2 C1 D2
A2 B1 C2 D1
A3 B3 C1 D3
A2 B3 C2 D3
A4 B2 C3 D2
A3 B4 C1 D3
A5 B1 C1 D1
Assume that the four attributes A, B, C, and D are atomic and (A, B) is the key of R.
(i) Show that the relation is not in 3N F .
(ii) Provide a lossless decomposition of R, so that the decomposed relations are in
3N F , and determine their primary keys.
(iii) Write the following query in SQL: find the distinct values of A and the count of
such values, for each value of C.
(b) Determine the minimum number of elementary logic gates (AND / OR / NOT) required
to implement the Boolean expression
AB ∨ AB̄ ∨ ĀC, where x̄ denotes the complement of x.
(c) A logic circuit has three Boolean inputs X,Y and Z. Its output is F(X,Y,Z) such that:
F(X,Y,Z) = 1 if aX + bY +cZ > d
= 0 otherwise.
a,b,c,d are real constants.
For which of the following values of a,b,c,d does this circuit represent an implemen-
tation of a three-input NAND gate with inputs X,Y and Z?
I. a = b = c = 1; d = 2.5
II. a = b = c = 1; d = 1.5
III. a = b = c = -1; d = 0
IV. None of the above
6. (a) Consider a channel with a capacity of 1 MHz and an SNR of 63.
(i) What is the upper limit on the data rate that the channel can carry?
(ii) How many signal levels are needed to achieve the data rate of 23 of the upper limit
obtained in 6a(i) above?
(b) Consider the use of 1000-bit frames on a 1 M bps satellite channel whose propagation
time from the earth to the satellite is 270 msec. Assume that headers and acknowl-
edgement frames are of negligible length. Calculate the maximum achievable channel
utilization for the following two cases:
(i) Stop-and-wait protocol where P = 10−3 is the probability that a single frame is in
error. Assume that acknowledgement frames are never in error.
(ii) Error-free operation of stop-and-wait protocol where acknowledgements are always
piggybacked onto the data frames.
13
(c) A virtual memory system is able to support virtual address space of 256 GB. An entry
in the page table is 4 bytes long.
(i) Calculate the minimum page size required for a three-level paging scheme.
(ii) Draw a diagram indicating how the bits of a virtual address will be interpreted by
the address translation mechanism. Indicate which bits (and how many) are used to
index the page tables at each level, and which bits form the page offset for the case
above.
1. (a) A BCD seven segment decoder takes four inputs A,B,C,D and has seven outputs. The
inputs represent the binary equivalent of an integer between 0 and 9. Each of the seven
outputs a, b, c, d, e, f , and g corresponds to one of the seven LEDs in a seven-segment
display as shown below.
(i) Give the truth table for segment g.
(ii) Draw its K-map and write minimum SOP form.
a c
g
f d
(b) Prove algebraically that the set of XOR and AND operations form a functionally com-
plete set of Boolean operations.
2. (a) A perfectly spherical ice ball at rest at the top of a plane of length l, inclined at an angle
α with the horizontal, is set to roll freely. If the rate of decrease of its volume Vt at any
1/3 √
instance t is proportional to its surface at that instant, prove that Vt = (V0 − k l)3 ,
where V0 is the initial volume of the ice ball and k is a constant. Assume that the ice ball
remains spherical all through its downward journey and it suffers no friction.
(b) A particle of mass m slides down from rest at the highest point of a smooth plane.
The plane is inclined at an elevation θ fixed in an elevator which is going up with an
acceleration a0 . The base of the inclined plane has a length b. Find the time taken by the
particle to reach the bottom.
3. (a) A uniform rod of mass M and length l lies on a smooth horizontal plane. A particle
of mass m moving on the plane with a speed v perpendicular to the length of the rod,
strikes it at a distance l/4 from the centre and stops after the collision. Find
(i) the velocity of the centre of the rod, and
(ii) the angular velocity of the rod about its centre just after the collision.
14
(b) A homogeneous wooden bar of length 10 cm, thickness 4 cm and weight 1 Kg is bal-
anced on the top of a semicircular cylinder of radius R as shown below. Calculate the
minimum radius of the semicircular cylinder if the wooden bar is at stable equilibrium.
10 cm
4 cm Wooden Bar
4. (a) The mean distance of Mars from the Sun is 1.5 times that of the Earth from the Sun.
Find the time of revolution of Mars about the Sun with respect to that of the Earth about
the Sun.
(b) A cyclic heat engine receives 300 KJ from an energy reservoir at 900◦ K. It rejects
100 KJ to an energy reservoir at 300◦ K. The machine produces 250 KJ of work as
output. Argue whether this cycle is reversible, irreversible or impossible.
(c) A heat engine has a solar collector receiving 0.2 KW/m2 , inside which a material is
heated to 450◦ K. The collected energy powers a heat engine which rejects heat at 52◦ C.
If the heat engine is supposed to deliver 2.5 KW , compute the minimum area of the solar
collector.
15
5. (a) Find the capacitance across terminals A and B of the infinite ladder shown below.
C C C
A
o
C C C C
B
o
(b) Consider the portion of a circuit shown in the figure in steady state with the currents
flowing in the branches having resistances as indicated. Calculate the energy stored in
the capacitor C.
6. (a) An npn transistor shown in the following figure is used in common-emitter mode with
β = 49, Vcc = 10 V , and RL = 2 KΩ. A 100 KΩ resistor RB is connected between
the collector and the base of the transistor. Calculate the quiescent collector current.
Assume that the base to emitter voltage drop is 0.7 V .
16
(b) Consider the circuit shown in the following figure. Derive the output voltage v0 for the
circuit in terms of v and R.
7. A 7.92 KW , 220 V , 1000 r.p.m. shunt motor has a full-load efficiency of 90%, an armature
resistance of 0.1 Ω and a shunt field resistance of 110 Ω. The speed of this motor is reduced
to 500 r.p.m. by inserting an external resistance in series with the armature keeping the load
torque constant.
(i) Calculate the value of the external resistance, and the corresponding efficiency of the
motor.
(ii) Assuming that the constant loss is proportional to the armature current, re-calculate the
efficiency of the motor.
8. Consider the following C function (recall that ’&’ denotes bit-wise AND, and ’>>n’ denotes
right-shift by n bits):
int mystery(int x)
{
int y = 0;
while (x != 0)
{
if (x & 1) y++;
x = x >> 1;
}
return y;
}
(i) What does the function mystery compute when invoked on a positive integer x?
(ii) What is the value of y returned by mystery when it is called as mystery(65)?
(iii) How many times (denoted by k) is the while loop executed when called as mystery(65)?
(iv) Can you modify the code to reduce k, for example to 2 for x=65? If yes, present the
code for the new mystery function. If not, give reasons.
17
Sample Questions 2020
Test Code PCB (Short Answer Type)
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.
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.
|LEFT-HEIGHT(v) - RIGHT-HEIGHT(v)| ≤ 1.
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:
PUSH a Pushes a to the stack, i.e., if [x, y, z] be the stack,
after PUSH a, the stack becomes [a, x, y, z].
DUP Duplicates the top, i.e., if [a, b, c] be the stack, after
DUP the stack becomes [a, a, b, c].
ADD Adds the two topmost elements, removes them and
pushes the result, i.e., if [a, b, c] be the stack, after
ADD it becomes [a + b, c].
SUB 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].
REV Reverses the order of the three topmost elements in
the stack, i.e., if [a, b, c, z] be the stack, after REV the
configuration becomes [c, b, a, z] (if the stack contains
less than 3 elements, REV is undefined).
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
PUSH a; PUSH b; . . .
1
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.
(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.
2
C9. Consider a byte addressable memory with 16 bit addresses and a 2-
way set associative L1 cache of size 8 kB (kilobyte). Each cache line
is 4 words long. A process sequentially accesses the following memory
addresses:
0x1000, 0x1004, 0x1010, 0x11C0, 0x2000, 0x3000, 0x1006, 0x2001
Assuming the L1 cache is initially empty and the LRU (least recently
used) page replacement policy is used, indicate whether the cache ac-
cess will result in a hit or a miss for each of the above addresses.
C12. You can climb up a staircase of n stairs by taking steps of one or two
stairs at a time.
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.
3
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.
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;
4
}
}
}
}
C17. A context switch from a process Pold to a process Pnew consists of the
following steps:
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-
to-run processes. The scheduling policy is round-robin with a time
slice of 10ms. Compute the CPU utilization for the following scenario:
k processes become ready at almost the same instant in the order
P1 , P2 , . . . , Pk ; each process requires exactly one CPU burst of 20ms
and no I/O burst.
C18. Consider a 5-stage instruction pipeline. The stages and the corre-
sponding stage delays are given below.
(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.
5
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:
ind val
2 1
3 3
5 2
6
Group B
Non Computer Science
NC1. Let {an } be a decreasing sequence such that ∞
P
n=1 an is convergent.
Prove that the sequence {nan } goes to zero as n → ∞.
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.
NC4. Show that for every θ ∈ (0, π2 ), there exists a unique real number xθ
such that
3
(sin θ)xθ + (cos θ)xθ = .
2
NC5. Suppose f and g are continuous real valued functions on [a, b] and are
differentiable on (a, b). Assume that g 0 (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)
7
NC8. Let f be a real valued function on R. If for all real x,
f (x) + 3f (1 − x) = 5
Prove that cm ∈ [a, b], for all m ≥ 1, limm→∞ cm exists and find its
value.
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
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
NC14. Let
1 2 1 −1
A= 2 0 t 0 .
0 −4 5 2
If rank( A) = 2, calculate t.
NC19. Let G be a finite group and H the only subgroup of G of order |H|.
Prove that H is normal in G.
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
2) is 12,
• the sum of the numbers lying between 2 and 3 (including 2 and
3) is 23,
• the sum of the numbers lying between 3 and 4 (including 3 and
4) is 34,
• the sum of the numbers lying between 4 and 5 (including 4 and
5) is 45.
9
NC23. Let X ∼ Bin (n, p), and Y ∼ P oisson (λ). Let
T = X1 + X2 + · · · + XY ,
S = Y1 + Y2 + · · · + YX ,
10
Test Code: PCB (short answer type) 2015
The selection test for M.Tech. in Computer Science will consist of two parts.
• Test MMA (objective type) in the forenoon session is the 1st part, and
• Test PCB (short answer type) in the afternoon session is the 2nd part.
The PCB test will consist of two groups.
The syllabus and sample questions for the MMA test are available separately. The
syllabus and sample questions for the PCB test are given below.
Note:
1. Not all questions in this sample set are of equal difficulty. They may not carry
equal marks in the test. More sample questions are available on the website
for M.Tech(CS) at http://www.isical.ac.in/∼deanweb/MTECHCSSQ.html
2. Each of the two tests MMA and PCB, will have individual qualifying marks.
1
Group B
Mathematics
Calculus and real analysis – real numbers, basic properties, convergence of se-
quences and series, limits, continuity, uniform continuity of functions, differentia-
bility of functions of one or more variables and applications, indefinite integral,
fundamental theorem of Calculus, Riemann integration, improper integrals, double
and multiple integrals and applications, sequences and series of functions, uniform
convergence.
Linear algebra – vector spaces and linear transformations, matrices and systems
of linear equations, characteristic roots and characteristic vectors, Cayley-Hamilton
theorem, canonical forms, quadratic forms.
Graph Theory – connectedness, trees, vertex coloring, planar graphs, Eulerian
graphs, Hamiltonian graphs, digraphs and tournaments.
Abstract algebra – groups, subgroups, cosets, Lagrange’s theorem, normal sub-
groups and quotient groups, permutation groups, rings, subrings, ideals, integral
domains, fields, characteristics of a field, polynomial rings, unique factorization
domains, field extensions, finite fields.
Differential equations – solutions of ordinary and partial differential equations and
applications.
Statistics
Notions of sample space and probability, combinatorial probability, conditional
probability, Bayes’ theorem and independence.
Random variable and expectation, moments, standard univariate discrete and con-
tinuous distributions, sampling distribution of statistics based on normal samples,
central limit theorem, approximation of binomial to normal, Poisson law.
Multinomial, bivariate normal and multivariate normal distributions.
Descriptive statistical measures, product-moment correlation, partial and multiple
correlation.
Regression – simple and multiple.
Elementary theory and methods of estimation – unbiasedness, minimum variance,
sufficiency, maximum likelihood method, method of moments, least squares meth-
ods.
Tests of hypotheses – basic concepts and simple applications of Neyman-Pearson
lemma, confidence intervals.
Tests of regression, elements of non-parametric inference, contingency tables and
Chi-square, ANOVA, basic designs (CRD/RBD/LSD) and their analyses, elements
of factorial designs.
Conventional sampling techniques, ratio and regression methods of estimation.
2
Physics
Computer Science
Data structures - array, stack, queue, linked list, binary tree, heap, AVL tree, B-
tree.
Discrete Mathematics - recurrence relations, generating functions, graph theory -
paths and cycles, connected components, trees, digraphs.
Programming languages - Fundamental concepts - abstract data types, procedure
call and parameter passing, languages like C and C++.
3
Design and analysis of algorithms - Asymptotic notation, sorting, selection, search-
ing, graph traversal, minimum spanning tree.
Switching Theory and Logic Design - Boolean algebra, minimization of Boolean
functions, combinational and sequential circuits - synthesis and design.
Computer organization and architecture - Number representation, computer arith-
metic, memory organization, I/O organization, microprogramming, pipelining, in-
struction level parallelism.
Operating systems - Memory management, processor management, critical section
problem, deadlocks, device management, file systems.
Formal languages and automata theory - Finite automata and regular expressions,
pushdown automata, context-free grammars, Turing machines, elements of unde-
cidability.
Database management systems - Relational model, relational algebra, relational
calculus, functional dependency, normalization (up to 3-rd normal form).
Computer networks - OSI, LAN technology - Bus/tree, Ring, Star; MAC proto-
cols; WAN technology - circuit switching, packet switching; data communications
- data encoding, routing, flow control, error detection/correction, Internet working,
TCP/IP networking including IPv4.
Engineering and Technology
C Programming language.
Gravitation, moments of inertia, particle dynamics, elasticity, friction, strength of
materials, surface tension and viscosity.
Laws of thermodynamics and heat engines.
Electrostatics, magnetostatics and electromagnetic induction.
Laws of electrical circuits – transient and steady state responses of resistive and
reactive circuits.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
Diode circuits, bipolar & FET devices and circuits, transistor circuits, oscillator,
multi-vibrator, operational amplifier.
Digital circuits – combinatorial and sequential circuits, multiplexer, de-multiplexer,
counter, A/D and D/A converters.
Boolean algebra, minimization of switching functions.
SAMPLE QUESTIONS
Group A
A1. How many times will the digit ‘7’ be written when listing the integers from 1
to 1000? Justify your answer.
4
A2. For sets A and B, define A∆B = (Ā ∩ B) ∪ (A ∩ B̄). Show the following
for any three sets A, B and C.
(a) A∆A = ∅.
(b) A∆(B∆C) = (A∆B)∆C.
(c) If A∆B = A∆C then B = C.
A3. In a group of n persons, each person is asked to write down the sum of the
ages of all the other (n − 1) persons. Suppose the sums so obtained are
s1 , . . . , sn . It is now desired to find the actual ages of the persons from these
values.
A7. Find all pairs of prime numbers p, q such that p + q = 18(p − q). Justify your
answer.
• P2 = P,
• Q2 = Q, and
• I − P − Q is invertible, where I is a n × n identity matrix.
5
Group B
Computer Science
C1. (a) How many asterisks (*) in terms of k will be printed by the following C
function, when called as count(m) where m = 3k ? Justify your answer.
Assume that 4 bytes are used to store an integer in C and k is such that
3k can be stored in 4 bytes.
void count(int n)
{
printf("*");
if(n>1)
{
count(n/3);
count(n/3);
count(n/3);
}
}
6
Design an algorithm that takes a positive integer y as input and finds the
position of y in X. Your algorithm should return “Not found” if y is not in
the array. You will get no credit if the complexity of your algorithm is linear
(or higher) in the number of positive integers in X.
C4. (a) Prove or disprove the following statement: The union of a regular lan-
guage with a disjoint non-regular language over the same alphabet can
never be regular.
[Hint: You may use the closure properties of regular languages.]
(b) It is known that the language L1 = {0n 1n 2i | i 6= n} is not a context free
language (CFL). Now consider the language
L2 = {0i 1n 2n | i 6= n}. We can prove L2 is not a CFL by convert-
ing L2 into L1 by applying two operations, both known to be closed on
CFLs. What are the two operations you will use for this conversion?
Justify your answer.
C5. Consider three relations R1(X, Y, Z), R2(M , N, P ), and R3(N, X). The
primary keys of the relations are underlined. The relations have 100, 30, and
400 tuples, respectively. The space requirements for different attributes are:
X = 30 bytes, Y = 10 bytes, Z = 10 bytes, M = 20 bytes, N = 20 bytes,
and P = 10 bytes. Let V (A, R) signify the variety of values that attribute
A may have in the relation R. Let V (N, R2) = 15 and V (N, R3) = 300.
Assume that the distribution of values is uniform.
(a) If R1, R2, and R3 are to be joined, find the order of join for the min-
imum cost. The cost of a join is defined as the total space required by
the intermediate relations. Justify your answer.
(b) Calculate the minimum number of disk accesses (including both reading
the relations and writing the results) required to join R1 and R3 using
block-oriented loop algorithm. Assume that (i) 10 tuples occupy a block
and (ii) the smaller of the two relations can be totally accommodated in
main memory during execution of the join.
C6. (a) Consider three processes, P1 , P2 , and P3 . Their start times and execu-
tion times are given below.
Process Start time Execution time
P1 t = 0 ms 100 ms
P2 t = 25 ms 50 ms
P3 t = 50 ms 20 ms
Let ∆ be the amount of time taken by the kernel to complete a context
switch from any process Pi to Pj . For what values of ∆ will the average
7
turnaround time for P1 , P2 , P3 be reduced by choosing a Shortest Re-
maining Time First scheduling policy over a Shortest Job First policy?
(b) The circuit shown in the following figure computes a Boolean function
F . Assuming that all gates cost Rs. 5 per input (i.e., an inverter costs Rs.
5, a 2-input gate costs Rs. 10, etc.), find the minimum cost realization
of F using only inverters, AND / OR gates.
A
D
F
C
8
sn−1 ⊕ (an−1 sn−1 ) = bn−1 (sn−1 ⊕ an−1 )
where ⊕ denotes the Boolean XOR operation. You may use the Boolean
identity: X + Y = X ⊕ Y ⊕ (XY ) to prove your result.
(b) Consider a machine with 5 stages F , D, X, M , W , where F denotes
instruction fetch, D - instruction decode and register fetch, X - exe-
cute/address calculation, M - memory access, and W - write back to
a register. The stage F needs 9 nanoseconds (ns), D needs 3 ns, X
requires 7 ns, M needs 9 ns, and W takes 2 ns. Let M1 denote a non-
pipelined implementation of the machine, where each instruction has to
be executed in a single clock cycle. Let M2 denote a 5-stage pipelined
version of the machine. Assume that pipeline overhead is 1 ns for each
stage. Calculate the maximum clock frequency that can be used in M1
and in M2 .
C9. (a) Read the C code given below. Use the four integers corresponding to
the four digits of your question booklet number as input to the program.
For example, if your question booklet number is 9830, then your input
would be this: 9 8 3 0
#include<stdio.h>
#define STACKSIZE 2
STACK index[STACKSIZE];
STACK *ptr = index;
9
ptr[count].item.N = i;
ptr[count].item.D = j;
ptr[count].number = count+1;
}
if(count == 0) return(1.0);
else{
if ((Type)ptr[count-1].item.D == 0)
return 1.0;
val = (Type)ptr[count-1].item.N/
(Type)ptr[count-1].item.D;
return(Doit(--count) * val);
}
}
void main() {
int i, j, count=0;
C10. (a) A palindrome over the alphabet Σ = {a, b, . . . , z}, (|Σ| = 26) is a string
that reads the same both forwards and backwards. For example, tenet is
a palindrome over Σ. Let P (n) be the number of palindromes of length
n over Σ. Derive an expression for P (n) in terms of n. You may use
recurrence relations.
10
(b) For any two languages L1 , L2 ⊆ {0, 1}∗ , their symmetric difference
SD(L1 , L2 ) is the set of strings that are in exactly one of L1 and L2 . For
example, if L1 = {00, 101} and L2 = {11, 00}, then SD(L1 , L2 ) = {11,
101}.
(i) Suppose A is the set of all strings of the form 0∗ 1∗ , and B is the set
of all strings of the form 1∗ 0∗ .
• List all the strings of length 3 or less in SD (A, B).
• Write a regular expression for SD(A, B).
(ii) Is SD (L1 , L2 ) necessarily a Context-Free language? Justify your
answer.
C11. (a) You are given a sorted list A of n real numbers a1 , a2 , . . . , an with values
in the range (α, β). Write an O(n) time algorithm to partition A into two
disjoint non-empty subsets A1 and A2 such that
maxai ∈A1 |α − ai | + maxaj ∈A2 |β − aj |
is minimum among all such possible partitions.
(b) Let A[1 . . . n] be a given array of n integers, where n = 2m . The follow-
ing two operations are the only ones to be applied to A:
• Add(i, y): Increment the value of A[i] by y.
• Partial-sum(k): Print the current value of ki=1 A[i].
P
One needs to perform these two operations multiple times in any given
order. Design a data structure to store A such that each invocation of
these two operations can be done in O(m) steps.
C12. Consider a singly linked list, with each node containing an integer and a
pointer to the next node. The last node of the list points to N U LL. You
are given two such lists A and B containing m and n nodes, respectively. An
intersection point between two linked lists is a node common to both.
You are not allowed to modify A and B. Partial credit may be given if your
algorithm uses more than Θ(1) additional space.
C13. (a) Let R and S be two relations, and l be an attribute common to R and S.
Let c be a condition over the attributes common to R and S. Prove or
disprove the following:
11
(i) Πl (R − S) = Πl (R) − Πl (S);
(ii) σc (R ./ S) = σc (R) ./ σc (S).
(b) Following are the steps executed by the CPU in a certain order, to pro-
cess an interrupt received from a device. Mention the
correct order of execution of these steps.
I. CPU executes the Interrupt Service Routine.
II. CPU uses the vector number to look up the address of the Interrupt
Service Routine to be executed.
III. CPU returns to the point of execution where it was interrupted.
IV. Interrupt Service Routine restores the saved registers from the stack.
V. CPU grants the interrupt for the device and sends interrupt ac-
knowledge to the device (IACK).
VI. Interrupt Service Routine saves the registers onto a stack.
VII. CPU receives the vector number from the device.
C14. (a) Consider two processes P1 and P2 entering the ready queue with the
following properties:
• P1 needs a total of 12 time units of CPU execution and
20 time units of I/O execution. After every 3 time units of CPU
work, 5 time units of I/O are executed for P1.
• P2 needs a total of 15 time units of CPU execution and no I/O. P2
arrives just after P1.
Report the schedules, and the corresponding completion times of P1 and
P2 for each of the following two scheduling strategies:
(i) Shortest Remaining Time First (preemptive), and
(ii) Round Robin, with a slice of 4 time units.
(b) What will happen to a packet sent to the IPv4 address 127.0.0.1?
(c) A 2km long LAN has 10Mbps bandwidth and uses CSMA/CD. The
signal travels along the wire at 2×108 m/s. What is the minimum packet
size that can be used on this network?
C15. (a) Calculate how many integers in the set {1, 2, 3, ..., 1000} are not divisi-
ble by 2, 5, or 11.
(b) Let 5 points be randomly placed in a square box of size 2 × 2. √ Show
that the distance of the closest pair of these five points is at most 2.
12
(c) Show that, given 2n + 1 points with integer coordinates in IRn , there
exists a pair of points among them such that all the coordinates of the
midpoint of the line segment joining them are integers.
(d) Find the number of functions from the set {1, 2, 3, 4, 5} onto the set
{1, 2, 3}.
13
Engineering and Technology
E1. (a) A 50kW compound generator works on half-load with a terminal volt-
age of 250V. The shunt, series and armature windings have resistances
of 126Ω, 0.02Ω and 0.05Ω respectively. Calculate the total power gen-
erated at the armature when the machine is connected to short-shunt.
(b) A single phase 60kVA transformer delivers full load at 0.75 power factor
with 90% efficiency. If the same transformer works at half load at 0.70
power factor, its efficiency increases to 91.3%. Calculate the iron loss
of the transformer.
E2. Two long straight parallel wires stand 2 meters apart in air and carry currents
I1 and I2 in the same direction. The field intensity at a point midway between
the wires is 7.95 Ampere-turn per meter. The force on each wire per unit
length is 2.4 ×10−4 N. Assume that the absolute permeability of air is 4π ×
10−7 H per meter.
(a) Explain the nature of the force experienced between the two wires, i.e.
attractive or repulsive.
(b) Determine I1 and I2 .
(c) Another parallel wire carrying a current of 50 A in the opposite direction
is now placed midway between the two wires and in the same plane.
Determine the resultant force on this wire.
E3. A choke coil connected across a 500 V, 50 Hz supply takes 1 A current at a
power factor of 0.8.
(a) Determine the capacitance that must be placed in series with the choke
coil so that it resonates at 50 Hz.
(b) An additional capacitor is now connected in parallel with the above
combination in (a) to change the resonant frequency. Obtain an ex-
pression for the additional capacitance in terms of the new resonant fre-
quency.
E4. (a) The mechanical system shown in the figure below is loaded by a hori-
zontal 80 N force. The length of the spring is 500 mm. Each arm of the
mechanical system is also of length 500 mm as shown in the figure. Un-
der the influence of 80 N load, the spring is stretched to 600 mm but the
entire mechanical system including the spring remains in equilibrium.
Determine the stiffness of the spring. Note that the spring and the frame
are fixed at the pin position P. The other end of the spring is at R which
is a frictionless roller free to move along the vertical axis. Assume that
the mechanical joints between the arms are frictionless.
14
(b) A brake system is shown in the figure below. The solid disk of radius
1000 mm is being rotated at 196 rpm. The bar AB, of length 4000 mm,
is fixed at the end A and subjected to a downward load of 100 N at
the end B to stop the rotation of the disk. The bar AB (assumed to be
horizontal) touches the rotating disk at a point 500 mm from the fixed
end of the bar. The weight of the disk is 10 Kg and the coefficient of
friction between the bar and the disk is 0.5. Calculate the number of
revolutions the disk will make before coming to rest.
E5. (a) Air at 90◦ C and 605 Kg per square meter pressure is heated to 180◦ C
keeping the volume constant at 21 cubic meter. Find
(i) the final pressure, and
(ii) the change in the internal energy.
Note that the specific heat at constant pressure (Cp ), the specific heat at
constant volume (Cv ), and the mechanical equivalent of heat are 0.3, 0.2
and 420 Kg-meter per Kcal, respectively.
(b) A molten metal is forced through a cylindrical die at a
pressure of 168×103 Kg per square meter. Given that the density of
the molten metal is 2000 Kg per cubic meter and the specific heat of the
metal is 0.03, find the rise in temperature during this process. Assume
that the mechanical equivalent of heat is 420 Kg-meter per Kcal.
E6. (a) Calculate the current I flowing through the resistor R shown in the fol-
lowing figure (e1 < e2 < · · · < en ).
15
r r r
I
r1 + e1 r2 + e2 rn + n
e
− − − R
E8. (a) Consider the following circuit with an ideal Op-amp. Calculate Vo .
10 K
2V 5K
Vo
2K
1V 2K
(b) The following network uses four transconductor amplifiers and two ca-
pacitors to produce the output voltage Vo for the input voltage Vi .
16
Vo
gm gm gm gm
1 2 3 4
V
i _
+ + +
_ _ _
+
C C
1 2
Vo gm1 /gm4 .
H(s) = = gm2 C2
Vi 1 + ( gm gm )s + ( gmC1 gCm2 )s2
3 4 3 4
QQ1
+ +
QQ2 RE1K
VI VO
- -
(i) Draw the equivalent circuit using the small-signal hybrid parameter
model.
(ii) For the following values of h parameters for both transistors: hie =
1000 Ω, hf e = 100, hre = hoe = 0, determine the voltage amplifi-
cation Av and the input resistance Rin .
E10. The following is the skeleton of a C program that outputs the number of
occurrences of each of the ten digits in a given string of digits. Write the
codes for the portions marked as B1, B2, B3 and B4 with appropriate C
constructs.
#include<stdio.h>
#define base 10
17
/* This program outputs the numbers of 0’s, 1’s */
/* ,....., 9’s in an input string ending in $ */
int main() {
char b;
int i, a[base];
18
Mathematics
{x : Ax = 0} = {x : A2 x = 0}.
(c) Let
2 −1 −1
1
A = −1 2 −1 .
3
−1 −1 2
Which of the following statements are true? In each case, justify your
answer.
(i) The rank of A is equal to the trace of A.
(ii) The determinant of A is equal to the determinant of An for all n >
1.
M4. (a) Let a1 , a2 , . . . be integers and suppose there exists an integer N such
∞
X an
that an = (n − 1) for all n ≥ N . Show that is rational.
n=1
n!
19
(b) Let 0 < s1 , s2 , s3 < 1. Show that there exists exactly one x ∈ (0, ∞)
such that
sx1 + sx2 + sx3 = 1.
M7. (a) Let S and T be two subsets of a finite group (G, +) such that |S|+|T | >
|G|. Here |X| is the number of elements in a set X. Then prove that
S + T = G, where S + T = {s + t : s ∈ S, t ∈ T }.
20
M9. (a) Let f : R → R be a function satisfying
x
f (x) = f for all x 6= 1.
1−x
Assuming that f is continuous at 0, find all possible such f .
(b) Z
For
any
Z real-valued
continuous function f on R, show that
x u Z x
f (t)dt du = (x − u)f (u)du for 0 < u < x.
0 0 0
M10 (i) GL(2, Z2 ) denotes the group of 2 × 2 invertible matrices with en-
tries in Z2 = {0, 1}:
1 0 0 1 1 1 1 0 1 1 0 1
, , , , , .
0 1 1 0 0 1 1 1 1 0 1 1
The operation in GL(2, Z2 ) is matrix multiplication with all the
arithmetic done in Z2 .
1 1
Is the cyclic subgroup generated by a normal subgroup?
0 1
Justify your answer.
(ii) Consider the set A = {(0, 0), (1, 1), (2, 2)}.
(i) Prove that A is a subring of Z3 × Z3 .
(ii) Prove or disprove: A is an ideal of Z3 × Z3 .
M11 (i) Given a simple graph G = (V, E) with V = {v1 , v2 , · · · , vn } and
E = {e1 , e2 , · · · , em }, let B = (bij )n×m be the matrix such that
bij = 1 if vi ∈ ej
= 0 otherwise .
Let A be the adjacency matrix of G, and D the diagonal matrix
with the degree sequence [d(v1 ), d(v2 ), · · · , d(vn )] on the diagonal.
Show that BB T = A + D.
(ii) Show that in a tree, there is a vertex common to all the longest paths
in the tree.
M12 (a) Consider the differential equation:
ex sin ydx + ex cos ydy = y sin(xy)dx + x sin(xy)dy.
Find the equation of the particular curve that satisfies the above
differential equation and passes through the point 0, π2 .
(b) Let the function f be four times continuously differentiable on
[−1, 1] with f (4) (0) 6= 0. For each n ≥ 1, let
1 1 1 00 1
f = f (0) + f 0 (0) + 2 f (0) + 3 f (3) (θn ),
n n 2n 6n
21
where 0 < θn < n1 .
1
Show that nθn → 4
as n → ∞.
22
Physics
P1. (a) Consider two partially overlapping spherical charge distributions with
constant charge densities +ρ and −ρ. Each sphere is of radius R. The
vector connecting the center of the negative charge sphere to the center
~ Find the electrostatic field at any
of the positive charge sphere is D.
point in the overlapping region.
(b) Consider two wire loops L1 and L2 . Show that the magnetic flux linked
to L1 when current I flows in L2 , is same as the magnetic flux linked to
L2 when current I flows in L1 .
(c) There are two co-axial solenoids. The inner short solenoid has radius
R, length L, N1 number of turns per unit length. The outer solenoid is
very long with N2 number of turns per unit length. Find the magnetic
flux linked with the outer solenoid when current I flows in the inner
solenoid. What is the coefficient of mutual inductance of the system of
solenoids?
(Hint: You can use the answer of (b) in (c).)
P2. (a) A particle is falling freely from a height h at 30◦ latitude in the northern
q
3
hemisphere. Show that the particle will undergo a deflection of ω 2h 3g
in the eastward direction, where ω is the rotational velocity of the earth
about its own axis and g is the acceleration due to gravity.
→
−
(b) A particle of mass m is moving in a plane in the field of force F =
−brkr cos θ, where k is a constant, rb is the radial unit vector and θ is the
polar angle.
(i) Write the Lagrangian of the system.
(ii) Show that the Lagrange’s equations of motion are:
A. mr̈ − mrθ̇2 + kr cos θ = 0;
B. mr2 θ̇ 6= constant.
(iii) Interpret (ii)B in the context of Kepler’s second law.
23
(b) A free particle of mass m moves in one dimension. At time t = 0, the
normalized wave function of the particle is
(b) Consider the following high energy reactions. Check whether the reac-
tions are allowed or forbidden. If allowed, mention the corresponding
decay process, and if forbidden, mention the law that is violated.
(i) µ+ → e+ + γ
(ii) p + p̄ → γ
(iii) p → e + + νe
(iv) p + n → p + Λ0
(v) p → e + + n + νe
P5. (a) How does one understand molecular mean free path in the context of
molecular kinetic theory of gases? Obtain the analytic form of the law
governing the distribution of free paths in an ideal gas.
(b) Calculate the mean free path, the collision rate and the molecular di-
ameter for Hydrogen gas molecules having the following particulars:
molecular weight of Hydrogen = 2.016 gm; viscosity, η = 85 × 10−6
dynes/cm2 /velocity gradient; mean speed, c = 16 × 104 cm/sec; density,
ρ = 0.000089 gm/cc.
24
(a) What is the probability of finding the electron in the region 0 < x < L4 ,
when it is in the lowest (ground) state of energy;
(b) Taking the mass of the electron me to be 9×10−31 Kg, Planck’s constant
h to be 6.6 × 10−34 Joule-sec and L = 1.1 cm, determine the electron’s
quantum number when it is in the state having an energy equal to 5 ×
10−32 Joule.
P7. (a) Consider the following circuit with an ideal Op-amp. Calculate Vo .
10 K
2V 5K
Vo
2K
1V 2K
(b) The circuit shown in the following figure computes a Boolean function
F . Assuming that all gates cost Rs. 5 per input (i.e., an inverter costs Rs.
5, a 2-input gate costs Rs. 10, etc.), find the minimum cost realization
of F using only inverters, AND / OR gates.
A
D
F
C
P8. (a) Lattice constant of a cubic lattice is a. Calculate the spacing between (2
1 1), (1 1 0), (1 1 1) and (1 0 1) planes.
(b) Show that for a crystal of cubic symmetry the direction [h, k, l] is per-
pendicular to the plane (h k l).
(c) The diamond crystal structure has the cube edge of 356Å. Calculate the
distance between the nearest-neighbor atoms.
P9. The zero-voltage barrier height of an abrupt p-n junction is 0.35 volt. Assume
that the concentration NA of acceptor atoms on the p-side is much smaller
25
19
than that of donor atoms on the n-side, and NA = 10π m−3 . Calculate the
width of the depletion layer for an applied reverse voltage of 14.65 volts.
If the cross-sectional area of the diode is 1 sq. mm, calculate the space charge
capacitance corresponding to this applied reverse voltage. (Assume that the
permittivity of the material is 12 × 10−9 /36π farad/metre).
26
Statistics
E(y1 ) = θ0 + θ1 + θ2 ,
E(y2 ) = θ0 + θ1 + θ3 ,
E(y3 ) = θ0 + θ2 + θ3 ,
E(y4 ) = θ0 + θ1 + θ2 .
3
X
(a) Determine the condition under which the parametric function ci θi is
i=0
estimable for known constants ci , i = 0, 1, 2, 3.
27
(b) Obtain the least squares estimates of the parameters θ0 , θ1 , θ2 and θ3 .
(c) Obtain the best linear unbiased estimator of (2θ1 − θ2 − θ3 ) and also
determine its variance.
(a) Find the most powerful test at level α = 0.05 to test whether the coin is
fair against the alternative that the coin is more likely to show up heads.
(b) What will be the conclusion of the test if there are exactly 7 heads in 10
tosses?
(c) Find the power function of this test.
S9. (a) Each time you buy a product, you get a coupon which can be any one
of N different types of coupons. Assuming that the probability that a
coupon of type i occurs is pi , find the distribution of the random variable
28
X which denotes the total number of products to be bought in order to
have all types of coupons.
(b) A box contains 6n tickets numbered 0, 1, 2, . . . , 6n − 1. Three tickets
are drawn at random without replacement. Find the probability that the
sum of the three numbers selected is 6n.
S10. Let
θk −θx k−1
p(x; θ, k) = e x , where 0 < x < ∞, θ > 0 and k > 0.
Γ(k)
S11. (a) Suppose in a coin tossing experiment with 2n trials, an unbiased coin
is flipped n times, while a different (possibly biased) spurious coin is
flipped remaining n times by mistake. The total number of heads is
found to be S2n in the 2n trials.
(i) Based on S2n , describe a test for the hypothesis that the spurious
coin is actually unbiased.
(ii) Give an approximate cut-off point at α = 0.05, assuming n is large.
(b) Let x1 , x2 , . . . , xm and y1 , y2 , . . . , yn be independent observations from
populations with continuous distribution functions F1 and F2 . Denote
by m1 and n1 the number of x’s and y’s exceeding the kth order statistic
of the combined sample.
Derive a nonparametric test of the null hypothesis H0 : F1 = F2 , based
on the propability distribution of (m1 , n1 ) under H0 .
S12. Consider a distribution of shots fired at a target point. Let (X, Y ) be the
coordinates (random variables) representing the errors of a shot with respect
to the two orthogonal axes through the target point.
29
Let the following hypotheses be true:
I. The marginal density functions p(x), q(y) of the errors X and Y are
continuous.
II. The probability density at (x, y) depends only on the distance r = (x2 +
y 2 )1/2 from the target point.
III. X and Y are independent.
Show that X and Y are identically distributed, and the probability distribution
function of X is
1 2 2
√ e−x /2σ for some σ > 0.
σ 2π
—–x—–
30
Test Code: CS (Short answer type) 2006
The candidates for M.Tech. in Computer Science will have to take two
tests – Test MIII (objective type) in the forenoon session and Test CS
(short answer type) in the afternoon session. The CS test booklet will have
two groups as follows.
GROUP A
A test for all candidates in analytical ability and mathematics at the B.Sc.
(pass) level, carrying 30 marks.
GROUP B
The syllabi and sample questions of the CS test are given below.
Note: All questions in the sample set are not of equal difficulty. They
may not carry equal marks in the test.
Syllabus
GROUP A
1
GROUP B
Mathematics
(B.Sc. Hons. level)
Statistics
(B.Sc. Hons. level)
2
Descriptive statistical measures, product-moment correlation, partial and
multiple correlation; regression (simple and multiple); elementary theory
and methods of estimation (unbiasedness, minimum variance, sufficiency,
maximum likelihood method, method of moments, least squares methods).
Tests of hypotheses (basic concepts and simple applications of Neyman-
Pearson Lemma). Confidence intervals. Tests of regression. Elements of
non-parametric inference. Contingency Chi-square, ANOVA, basic
designs (CRD/RBD/LSD) and their analyses. Elements of factorial
designs. Conventional sampling techniques, ratio and regression methods
of estimation.
Physics
(B.Sc. Hons. level)
Computer Science
(B.Tech. level)
Data structure - arrays, stack, queue, linked list, binary tree, heap, AVL
tree, B-tree.
Programming languages - fundamental concepts – abstract data types,
procedure call and parameter passing, languages like C and C++.
Design and analysis of algorithms: - sorting, selection, searching.
Computer organization and architecture: number representation, computer
arithmetic, memory organization, I/O organization, microprogramming,
pipelining, instruction level parallelism.
Operating systems: - memory management, processor management,
critical section, deadlocks, device management.
3
Formal languages and automata theory: - finite automata & regular
expression, pushdown automata, context-free grammars, Turing machines,
elements of undecidability.
Principles of Compiler Construction: - lexical analyzer, parser, code
optimization, symbol table.
Database management systems: - ER diagram, relational model, relational
algebra, relational calculus, functional dependency, normalization (up to
3rd normal form), concurrency control, crash recovery.
Computer networks: - Computer networks: OSI, TCP/IP protocol suite;
Internetworking (specially IPv4, IPv6); LAN technology - Bus/tree, Ring,
Star; ALOHA, CSMA, CSMA-CD; IEEE standards (802.3 to .5); WAN
technology - Circuit switching, packet switching; data communications -
data encoding, flow control, error detection/correction.
Switching Theory and Logic Design: Boolean algebra, minimization of
Boolean functions, combinational and sequential circuits – synthesis and
design.
4
Sample Questions
GROUP A
Mathematics
A1. If 1, a1, a2,…, an-1 are the n roots of unity, find the value of
(1 - a1) (1 - a2)…(1 - an-1).
A2. Let
S = {( a1 , a 2 , a3 , a 4 ) : ai ∈ ℜ , i = 1, 2, 3, 4 and a1 + a 2 + a3 + a 4 = 0}
and
Γ = {( a1 , a 2 , a3 , a 4 ) : ai ∈ ℜ , i = 1, 2 , 3, 4 and a1 − a 2 + a3 − a 4 = 0}.
Find a basis for S ∩ Γ .
c0 c1 c2 c3
c 2 c3 c0 c1
c − c c1 − c0
3 2
c − c c3 − c2
1 0
1+ 3 3+ 3 3− 3 1− 3
where c 0 = , c1 = , c2= , and c 3 = .
4 2 4 2 4 2 4 2
(Hint: What is c02 + c12 + c 22 + c32 ?)
A4. For any real number x and for any positive integer n show that
A8. Find the total number of English words (all of which may not have
proper English meaning) of length 10, where all ten letters in a word
are not distinct.
a1 a 2 a
A9. Let a0 + + + ..... + n = 0, where ai’s are some real constants.
2 3 n +1
Prove that the equation a 0 + a 1 x + a 2 x + ... + a n x = 0 has at least one
2 n
A10. Let φ (n) be the number of positive integers less than n and having
no common factor with n. For example, for n = 8, the numbers 1, 3,
5, 7 have no common factors with 8, and hence φ(8) = 4. Show that
(i) φ ( p) = p − 1 ,
(ii) φ ( pq ) = φ ( p)φ (q) , where p and q are prime numbers.
A11. A set S contains integers 1 and 2. S also contains all integers of the
form 3x+ y where x and y are distinct elements of S, and every
element of S other than 1 and 2 can be obtained as above. What is S?
Justify your answer.
g 0 ( x) = 0, g 1 ( x) = g ( x), g k +1 ( x) = g ( g k ( x)).
A13. Consider a square grazing field with each side of length 8 metres.
There is a pillar at the centre of the field (i.e. at the intersection of
the two diagonals). A cow is tied with the pillar using a rope of
length 83 metres. Find the area of the part of the field that the cow is
allowed to graze.
6
A14. Let f : [0,1] → [-1,1] be such that f(0) = 0 and f(x) = sin 1x for x > 0.
Is it possible to get three sequences {an}, {bn}, {cn} satisfying all
the three properties P1, P2 and P3 stated below? If so, provide an
example sequence for each of the three sequences. Otherwise,
prove that it is impossible to get three such sequences.
GROUP B
Mathematics
x n +3
M1. Let 0 < x1 < 1. If xn+1 = 3x + 1 , n = 1,2,3, …
n
5x n +3
(i) Show that xn+2 = 3x + 5 , n = 1,2,3, …
n
7
Let Pn = (1 + a11 )(1 + 1
a2
)L(1 + 1
an
)
Find lim Pn .
n→∞
M6. (a) Let A, B and C be 1×n, n×n and n×1 matrices respectively. Prove
or disprove: Rank(ABC) ≤ Rank(AC).
(b) Let S be the subspace of R4 defined by
S = {(a1, a2, a3, a4) : 5a1 - 2a3 -3a4 = 0}.
Find a basis for S.
8
(a) Show that there is a basis consisting of only symmetric and
skew-symmetric matrices.
(b) Find out the number of skew-symmetric matrices this basis
must contain.
M10. Let R be the field of reals. Let R[x] be the ring of polynomials over
R, with the usual operations.
(a) Let I ⊆ R[x] be the set of polynomials of the form a0 +a1x
+....+ anxn with a0 = a1 = 0. Show that I is an ideal.
(b) Let P be the set of polynomials over R of degree ≤ 1. Define ⊕
and Θ on P by (a0 +a1x) ⊕ (b0 +b1 x) = (a0 + b0)+(a1 +b1)x and
(a0 +a1x) Θ (b0 + b1x) = a0b0 + (a1b0 +a0b1)x. Show that (P, ⊕,
Θ ) is a commutative ring. Is it an integral domain? Justify your
answer.
9
Solve both the LPs. Write the duals of both the LPs and solve
the duals.
(b) If an LP is infeasible, what can you say about the solution of its
dual?
M15. (a) Show that a tree on n vertices has at most n−2 vertices with
degree > 1.
(b) Show that in an Eulerian graph on 6 vertices, a subset of 5
vertices cannot form a complete subgraph.
M16. (a) Show that the edges of K4 can be partitioned into 2 edge-disjoint
spanning trees.
(b) Use (a) to show that the edges of K6 can be partitioned into 3
edge-disjoint spanning trees.
(c) Let Kn denote the complete undirected graph with n vertices and
let n be an even number. Prove that the edges of Kn can be
partitioned into exactly n/2 edge-disjoint spanning trees.
Statistics
S1. (a) X and Y are two independent and identically distributed random
variables with Prob[X = i] = pi, for i = 0, 1, 2, ……… Find
Prob[X < Y] in terms of the pi values.
(b) Based on one random observation X from N(0, σ2), show that
√π/2 |X| is an unbiased estimate of σ.
S2. (a) Let X0, X1, X2, … be independent and identically distributed
random variables with common probability density function f. A
random variable N is defined as
N = n if X1 ≤ X 0 , X 2 ≤ X 0 , , X n−1 ≤ X 0 , X n > X 0 , n = 1, 2, 3,
S3. If a die is rolled m times and you had to bet on a particular number of
sixes occurring, which number would you choose? Is there always
one best bet, or could there be more than one?
S5. New laser altimeters can measure elevation to within a few inches,
without bias. As a part of an experiment, 25 readings were made on
the elevation of a mountain peak. These averaged out to be 73,631
inches with a standard deviation (SD) of 10 inches. Examine each of
the following statements and ascertain whether the statement is true
or false, giving reasons for your answer.
(a) 73631 ± 4 inches is a 95% confidence interval for the elevation
of the mountain peak.
(b) About 95% of the readings are in the range 73631 ± 4 inches.
(c) There is about 95% chance that the next reading will be in the
range of 73631 ± 4 inches.
S6. Consider a randomized block design with two blocks and two
treatments A and B. The following table gives the yields:
Treatment A Treatment B
Block 1 a b
Block 2 c d
11
S7. Let X be a discrete random variable having the probability mass
function
p ( x) = Λx(1- Λ)1-x, x = 0, 1,
where Λ takes values ≥ 0.5 only. Find the most powerful test, based
1 2
on 2 observations, for testing H0 : Λ = against H1 : Λ = , with
2 3
level of significance 0.05.
S9. Let t1, t2, …tk be k independent and unbiased estimators of the same
k
t
parameter θ with variances σ 12 ,σ 22 ,Kσ k2 . Define t as ∑ i . Find
i =1 k
k
E( t ) and the variance of t . Show that ∑ (t
i =1
i − t ) 2 /{k (k − 1)} is an
12
S11. In order to compare the effects of four treatments A, B, C, D, a block
design with 2 blocks each having 3 plots was used. Treatments A, B,
C were given randomly to the plots of one block and treatments A, B,
D were given randomly to the plots of the other block. Write down a
set of 3 orthogonal contrasts with the 4 treatment effects and show
that all of them are estimable from the above design.
S12. Let X1, X2, …Xn (Xi= (xi1, xi2, …, xip), i=1, 2, …, n) be n random
samples from a p-variate normal population with mean vector µ and
covariance matrix I.
1 n
xj = ∑ xij ,1 ≤ j ≤ p.
n i =1
Obtain the distribution of l ' Sl where l ∈ ℜ k , l ≠ 0.
4
S13. Let Yi = ∑ β j X ij + ∈i , i = 1,2,L, k ,
j =1
where Yi’s and X’ijs are known, and ∈i’s are independent and each
∈i’s follows N(0,σ2).
Physics
P1. A beam of X-rays of frequency v falls upon a metal and gives rise to
photoelectrons. These electrons in a magnetic field of intensity H
describe a circle of radius γ. Show that
1
2 1+ e
2 2
H
2 2
h(v − v 0 ) = m 0 c − 1
2 4
m0 c
where v0 is the frequency at the absorption limit and m0 is the rest
mass of the electron, e being expressed in e.s.u.
P2. (a) Two bodies A and B have constant heat capacities 2C and 23 C
respectively. The initial temperatures of A and B are 3T and
2T , respectively, in Kelvin scale. A refrigerator working
between these two bodies cools down B to a temperature of
TΟ
4
K . What is the minimum amount of work required to do this?
P3. The nucleus BZA decays by alpha ( He24 ) emission with a half-life T
to the nucleus C ZA−−24 which in turn, decays by beta (electron)
T
emission with a half-life to the nucleus DZA−−14 . If at time t = 0 , the
4
decay chain B → C → D had started with B0 number of B nuclei
only, then find out the time t at which the number of C nuclei will
be maximum.
14
P4. p1 and p 2 are two relativistic protons traveling along a straight line in
n 14n
the same direction with kinetic energies , and fractions
n +1 14n + 1
of their respective total energies. Upon entering a region where a
uniform magnetic field B acts perpendicularly on both, p1 and p 2
describe circular paths of radii r1 and r2 respectively. Determine the
r
ratio ρ = 1 . What is the value of ρ when n = 5 ?
r2
15
P7. An electron is confined to move within a linear interval of length L.
Assuming the potential to be zero throughout the interval except for
the two end points, where the potential is infinite, find the following:
(a) probability of finding the electron in the region 0 < x < L/4, when
it is in the lowest (ground) state of energy;
(b) taking the mass of the electron me to be 9 × 10-31 Kg, Planck's
constant h to be 6.6 × 10-34 Joule-sec and L = 1.1 cm, determine
the electron's quantum number when it is in the state having an
energy equal to 5 × 10-32 Joule.
P9. (a) Given the circuit shown in the figure, find out the current through
the resistance R = 3Ω between A and B .
(b) Suppose a metal ring of mean radius 100 cm is made of iron and
steel as shown in the figure. The cross-section of the ring is 10
16
sq.cm. If the ring is uniformly wound with 1000 turns, calculate
the current required to produce a flux of 1 milliweber. The
absolute permeability of air is 4π × 10 −7 H/m and relative
permeability of iron and steel are 250 and 1000 , respectively.
P11. Two heavy bodies A and B , each having charge − Q , are kept
rigidly fixed at a distance 2a apart. A small particle C of mass m
and charge + q ( << Q ), is placed at the midpoint of the straight
line joining the centers of A and B . C is now displaced slightly
along a direction perpendicular to the line joining A and B , and
then released. Find the period of the resultant oscillatory motion of
C , assuming its displacement y << a .
If instead, C is slightly displaced towards A , then find the
instantaneous velocity of C , when the distance between A and C
a
is .
2
17
Σ − → π − + n . The masses of ∑-, π- and n are M1, m1, and m2
respectively.
(a) How much kinetic energy is generated in the decay process?
(b) What are the ratios of kinetic energies and momenta of π
−
and n?
P14. (a) Find the relationship between L, C and R in the circuit shown in
the figure such that the impedance of the circuit is independent
of frequency. Find out the impedance.
(b) Find the value of R and the current flowing through R shown in
the figure when the current is zero through R′.
18
τ B(τ )
P15. A gas obeys the equation of state P = + where B (τ ) is a
V V2
function of temperature τ only. The gas is initially at temperature
τ and volume V0 and is expanded isothermally and reversibly to
volume V1 = 2V0 .
(a) Find the work done in the expansion.
(b) Find the heat absorbed in the expansion.
∂S ∂P
(Hint: Use the relation = where the symbols have
∂V τ ∂τ V
their usual meaning.
P16. (a) A spaceship moving away from the Earth at a speed of 0.80C
fires a missile parallel to its direction of motion. The missile
moves at a speed of 0.60C relative to the ship. What is the
speed of the missile as measure by an observer on the earth? (C
is the velocity of light in vacuum)
(b) What is the Kinetic energy of a proton (with rest energy 938
MeV) moving at a speed of v=0.86C?
Computer Science
A → Bb A→a
B →Cc B→b
C → Aa C→c
19
(b) An example of a function definition in C language is given
below:
20
(b) If the query is modified as πA,B(σB=10(R)), which one of the
three possible file structures given above should be chosen in
this case and why?
(c) Let the relation have 5000 tuples with 10 tuples/page. In case of
a hashed file, each bucket needs 10 pages. In case of B+ tree,
the index structure itself needs 2 pages. If the disk needs 25
msecs. to read or write a disk page, what would be the disk
access time for answering the above queries?
C4. Let A and B be two arrays, each of size n. A and B contain numbers
in sorted order. Give an O(log n) algorithm to find the median of
the combined set of 2n numbers.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and
1000 cylinders. The speed of rotation of the disk is 6000 rpm.
The average seek time is 10 millisecs. A file of size 50 MB is
written from the beginning of a cylinder and a new cylinder
will be allocated only after the first cylinder is totally occupied.
i) Find the maximum transfer rate.
ii) How much time will be required to transfer the file of 50
MB written on the disk? Ignore the rotational delay but not
the seek time.
21
- each vehicle is modeled by a process,
- the crossing is modeled as a shared data structure. Assume that
the vehicles can only move straight through the intersection (no
left or right turns). Using read-write locks (or any standard
synchronization primitive), you have to device a
synchronization scheme for the processes. Your scheme should
satisfy the following criteria:
i) prevent collisions,
ii) prevent deadlock, and
iii) maximize concurrency but prevent indefinite waiting
(starvation).
Write down the algorithm that each vehicle must follow in order
to pass through the crossing. Justify that your algorithm satisfies
the given criteria.
C8. Consider a binary operation shuffle on two strings, that is just like
shuffling a deck of cards. For example, the operation shuffle on
22
strings ab and cd, denoted by ab || cd, gives the set of strings
{abcd, acbd, acdb, cabd, cadb, cdab}.
C13. (a) The order of a regular language L is the smallest integer k for
which Lk = Lk+1, if there exists such a k, and ∞ otherwise.
(i) What is the order of the regular language a + (aa)(aaa)*?
(ii) Show that the order of L is finite if and only if there is an
integer k such that Lk = L*, and that in this case the order of L
is the smallest k such that Lk = L*.
(b) Solve for T(n) given by the following recurrence relations:
T(1) = 1;
T(n) = 2T(n/2) + n log n, where n is a power of 2.
24
(c) An A.P. is {p + qn|n = 0, 1, . . .} for some p, q ∈ IN . Show
that if L ⊆ {a}* and {n| an ∈ L} is an A.P., then L is regular.
C14. (a) You are given an unordered sequence of n integers with many
duplications, such that the number of distinct integers in the
sequence is O(log2 n). Design a sorting algorithm and its
necessary data structure(s) which can sort the sequence using
at most O(n log2(log2 n)) time. (You have to justify the time
complexity of your proposed algorithm.)
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12
(a)
Row I l(i)
1 2
2 3
3 3
4 4
5 5
(b)
25
C15. (a) You are given the following file abc.h:
#include <stdio.h>
#define SQR(x) (x*x)
#define ADD1(x) (x=x+1)
#define BeginProgram int main(int argc,char *argv[]){
#define EndProgram return 1; }
For each of the following code fragments, what will be the output?
(i) #include "abc.h"
main() { int y = 4; printf("%d\n", SQR(y+1)); }
(ii) #include "abc.h"
BeginProgram
int y=3; printf("%d\n", SQR(ADD1(y)));
EndProgram
#include <iostream.h>
main()
{
cout<<"MTech (CS)\n";
}
Sample Question
MTech (CS)
Indian Statistical Institute
26
stuck inside the bob and the string deflects with the total mass
through an angle of 120o keeping the string taut. Find
(i) the angle θ, and
(ii) the height of P from the horizontal plane.
Assume, g = 10 m / s 2 m, and friction in air is negligible.
E3. A chain of total length L = 4 meter rests on a table top, with a part
of the chain hanging over the edge, as shown in the figure below.
Let α be the ratio of the length of the overhanging part of the chain
to L.
If the coefficient of friction between the chain and the table top is
0.5, find the values of α for which the chain remains stationary. If α
= 0.5, what is the velocity of the chain when the last link leaves the
table?
27
E5. The truss shown in the figure rotates around the pivot O in a vertical
plane at a constant angular speed ω. Four equal masses (m) hang from
the points B, C, D and E. The members of the truss are rigid,
weightless and of equal length. Find a condition on the angular speed
ω so that there is compression in the member OE.
E6. If the inputs A and B to the circuit shown below can be either 0 Volt
or 5 Volt,
(i) what would be the corresponding voltages at output Z, and
(ii) what operation is being performed by this circuit ?
Assume that the transistor and the diodes are ideal and base to
emitter saturation voltage = 0.5 Volt
28
E7. Two bulbs of 500cc capacity are connected by a tube of length 20 cm
and internal radius 0.15 cm. The whole system is filled with oxygen,
the initial pressures in the bulbs before connection being 10 cm and
15 cm of Hg, respectively. Calculate the time taken for the pressures
to become 12 cm and 13 cm of Hg, respectively. Assume that the
coefficient of viscosity η of oxygen is 0.000199 cgs unit.
E8. Two identical watch glasses with negligible thickness are glued
together.
The rear one is silvered [see Figure(a)]. Sharp focus is obtained when
both object and image distance are equal to 20 cm. Suppose the space
between the glasses is filled with water (refractive index = 4/3) [see
Figure (b)]. Calculate d [Figure (b)] for which a sharp real image is
formed.
E9. (a) Two systems of equal mass m1 and m2 and heat capacity C are at
temperatures T1 and T2 respectively (T1 > T2). If the first is used as
source and the second as sink, find the maximum work obtainable
from such an arrangement.
(b) A Carnot engine A operates between temperatures T1 and T2 whose
dissipated heat at T2 is utilised by another Carnot engine B
operating between T2 and T3. What is the efficiency of a third
engine that operates between T1 and T3 in terms of the efficiencies
hA and hB of engines A and B respectively?
29
E11. A spherical charge distribution has a volume density ρ, which is a
function of r, the radial distance from the center of the sphere, as
given below.
A / r , A is constant for 0 ≤ r ≤ R
ρ=
0 , for r > R
Determine the electric field as a function of r, for r ≥ R. Also deduce
the expression for the electrostatic potential energy U(r), given that
U(∞) = 0 in the region r ≥ R.
E14. (a) State the two necessary conditions under which a feedback
amplifier circuit becomes an oscillator.
(b) A two-stage FET phase shift oscillator is shown in the diagram
below.
E15. A circular disc of radius 10cm is rotated about its own axis in a
uniform magnetic field of 100 weber/m2, the magnetic field being
perpendicular to the plane of the disc. Will there be any voltage
developed across the disc? If so, then find the magnitude of this
voltage when the speed of rotation of the disc is 1200 rpm.
E17. A shunt D.C. generator supplies a load of two motors each drawing
46 Amps and a lighting load consisting of twenty-two 60 watt lamps
at 220V. The resistance of shunt field, series field and armature are
110 ohms, 0.06 ohms and 0.05 ohms respectively.
(i) Find the electrical efficiency of the generator.
(ii) If the overall efficiency of the generator at the above load is
77%, find the total constant (iron and mechanical) loss.
E19. A 150 KVA, 4400/440 volt single phase transformer has primary and
secondary resistance and leakage reactance values as follows:
Rp = 2.4 Ω, Rs = 0.026 Ω, Xp =5.8 Ω, and Xs = 0.062 Ω.
This transformer is connected with a 290 KVA transformer in
parallel to deliver a total load of 330 KVA at a lagging power factor
of 0.8. If the first transformer alone delivers 132 KVA, calculate the
equivalent resistance, leakage reactance and percentage regulation of
the second transformer at this load. Assume that both the
transformers have the same ratio of the respective equivalent
resistance to equivalent reactance.
31
and the effective source resistance is 500 Ω, calculate the voltage
and current gains and the output resistance.
E21. Find the equivalent resistance between the points A and D of the
circuit shown in the diagram.
E23. In the figure, consider that FF1 and FF2 cannot be set to a desired
value by reset/preset line. The initial states of the flip-flops are
unknown. Determine a sequence of inputs (x1, x2) such that the
output is zero at the end of the sequence.
Output
___________________________________________________
32
Test Code: CS (Short answer type) 2009
The candidates for M.Tech. in Computer Science will have to take two
tests – Test MIII (objective type) in the forenoon session and Test CS
(short answer type) in the afternoon session. The CS test booklet will have
two groups as follows.
GROUP A
A test for all candidates in analytical ability and mathematics at the B.Sc.
(pass) level, carrying 30 marks.
GROUP B
The syllabi and sample questions for the CS test are given below.
Note: Not all questions in the sample set are of equal difficulty. They
may not carry equal marks in the test.
Syllabus
GROUP A
1
GROUP B
Mathematics
(B.Sc. Hons. level)
Statistics
(B.Sc. Hons. level)
2
Descriptive statistical measures, product-moment correlation, partial and
multiple correlation; regression (simple and multiple); elementary theory
and methods of estimation (unbiasedness, minimum variance, sufficiency,
maximum likelihood method, method of moments, least squares methods).
Tests of hypotheses (basic concepts and simple applications of Neyman-
Pearson Lemma). Confidence intervals. Tests of regression. Elements of
non-parametric inference. Contingency tables and Chi-square, ANOVA,
basic designs (CRD/RBD/LSD) and their analyses. Elements of factorial
designs. Conventional sampling techniques, ratio and regression methods
of estimation.
Physics
(B.Sc. Hons. level)
3
Atomic and molecular physics – quantum states of an electron in an atom,
Hydrogen atom spectrum, electron spin, spin–orbit coupling, fine
structure, Zeeman effect, lasers.
Condensed matter physics – crystal classes, 2D and 3D lattice, reciprocal
lattice, bonding, diffraction and structure factor, point defects and
dislocations, lattice vibration, free electron theory, electron motion in
periodic potential, energy bands in metals, insulators and semiconductors,
Hall effect, thermoelectric power, electron transport in semiconductors,
dielectrics, Claussius Mossotti equation, Piezo, pyro and ferro electricity.
Nuclear and particle physics – Basics of nuclear properties, nuclear forces,
nuclear structures, nuclear reactions, interaction of charged particles and
e-m rays with matter, theoretical understanding of radioactive decay,
particle physics at the elementary level.
Computer Science
(B.Tech. level)
Data structures - array, stack, queue, linked list, binary tree, heap, AVL
tree, B-tree.
Programming languages - Fundamental concepts – abstract data types,
procedure call and parameter passing, languages like C and C++.
Design and analysis of algorithms – Asymptotic notation, sorting,
selection, searching.
Computer organization and architecture - Number representation,
computer arithmetic, memory organization, I/O organization,
microprogramming, pipelining, instruction level parallelism.
Operating systems - Memory management, processor management,
critical section problem, deadlocks, device management, file systems.
Formal languages and automata theory - Finite automata and regular
expressions, pushdown automata, context-free grammars, Turing
machines, elements of undecidability.
Principles of Compiler Construction - Lexical analyzer, parser, syntax-
directed translation, intermediate code generation.
Database management systems - Relational model, relational algebra,
relational calculus, functional dependency, normalization (up to 3rd
normal form).
Computer networks - OSI, LAN technology - Bus/tree, Ring, Star; MAC
protocols; WAN technology - circuit switching, packet switching; data
4
communications - data encoding, routing, flow control, error
detection/correction, Internetworking, TCP/IP networking including IPv4.
Switching Theory and Logic Design - Boolean algebra, minimization of
Boolean functions, combinational and sequential circuits – synthesis and
design.
5
Sample Questions
GROUP A
Mathematics
A1. If 1, a1, a2,…, an-1 are the n roots of unity, find the value of
(1 - a1) (1 - a2)…(1 - an-1).
A2. Let
S = {( a1 , a 2 , a3 , a 4 ) : ai ∈ ℜ , i = 1, 2, 3, 4 and a1 + a 2 + a3 + a 4 = 0}
and
Γ = {( a1 , a 2 , a3 , a 4 ) : ai ∈ ℜ , i = 1, 2 , 3, 4 and a1 − a 2 + a3 − a 4 = 0}.
Find a basis for S ∩ Γ .
c0 c1 c2 c3
c 2 c3 c0 c1
c − c c1 − c0
3 2
c − c c3 − c2
1 0
1+ 3
c0 = ,3+ 3 3− 3 1− 3
where 4 2 c1 = , c2= , and c 3 = .
4 2 4 2 4 2
(Hint: What is c0 + c1 + c 2 + c3 ?)
2 2 2 2
A4. For any real number x and for any positive integer n show that
6
A6. A sequence {xn} is defined by x1 = 2, xn+1 = 2 + x n , n =1,2, …
Show that the sequence converges and find its limit.
1 1 1
lim + + ... +
n→∞
n +1 n2 + 2 n2 + n
2
A8. Find the total number of English words (all of which may not have
proper English meaning) of length 10, where all ten letters in a word
are not distinct.
a1 a 2 a
A9. Let a0 + + + ..... + n = 0, where ai’s are some real constants.
2 3 n +1
Prove that the equation a 0 + a 1 x + a 2 x + ... + a n x = 0 has at least one
2 n
A10. Let φ(n) be the number of positive integers less than n and having no
common factor with n. For example, for n = 8, the numbers 1, 3, 5, 7
have no common factors with 8, and hence φ(8) = 4. Show that
(i) φ ( p ) = p − 1 ,
(ii) φ ( pq) = φ ( p)φ (q) , where p and q are prime numbers.
7
g 0 ( x) = 0, g 1 ( x) = g ( x), g k +1 ( x) = g ( g k ( x)).
A13. Consider a square grazing field with each side of length 8 metres.
There is a pillar at the centre of the field (i.e. at the intersection of
the two diagonals). A cow is tied to the pillar using a rope of
8
length 3 metres. Find the area of the part of the field that the cow
is allowed to graze.
A14. Let f : [0,1] → [-1,1] be such that f(0) = 0 and f(x) = sin x for x > 0.
1
is divisible by 11.
8
GROUP B
Mathematics
x n +3
M1. Let 0 < x1 < 1. If xn+1 = , n = 1,2,3, …
3x n +1
5x n +3
(i) Show that xn+2 = , n = 1,2,3, …
3x n +5
(ii) Hence or otherwise, show that nlim
→∞
xn exists.
M3. Let
( x − 1) ( x 4 + 4 x + 7) if x is rational.
f ( x) =
(1 − x) ( x + 4 x + 7)
4
if x is irrational.
M4. Let h be any fixed positive real number. Show that there is no
differentiable function f : ℜ → ℜ satisfying both the following
conditions:
(a) f ′(0) = 0.
(b) f ′( x) > h for all x > 0.
M5. Find the volume of the solid given by 0 ≤ y ≤ 2 x , x + y ≤ 4 and
2 2
0≤ z≤ x.
9
M6. (a) Let A, B and C be 1×n, n×n and n×1 matrices respectively. Prove
or disprove: Rank(ABC) ≤ Rank(AC).
(b) Let S be the subspace of R4 defined by
S = {(a1, a2, a3, a4) : 5a1 - 2a3 -3a4 = 0}.
Find a basis for S.
d2y 2 dy
2
( x + 1) = 2 x .
dx dx
a 0 0
0 a 0
b c a
10
(a) Show that there is a basis consisting of only symmetric and
skew-symmetric matrices.
(b) Find out the number of skew-symmetric matrices this basis
must contain.
11
(d) Using definitions of characteristic root and characteristic vectors
only, find out all the characteristic roots of the matrix in (b).
Statistics
S1. (a) X and Y are two independent and identically distributed random
variables with Prob[X = i] = pi, for i = 0, 1, 2, ……… Find
Prob[X < Y] in terms of the pi values.
(b) Based on one random observation X from N(0, σ2), show that
√π/2 |X| is an unbiased estimate of σ.
S2. (a) Let X0, X1, X2, … be independent and identically distributed
random variables with common probability density function f. A
random variable N is defined as
N = n if X1 ≤ X 0 , X 2 ≤ X 0 , , X n−1 ≤ X 0 , X n > X 0 , n = 1, 2, 3,
12
S3. Let A = {1,2,3}. You are given a coin with probability of head as
p, where 0 < p < 1 and p is unknown. Suggest a procedure for
choosing a number randomly from A using the given coin, such
1
that P({1}) = P({2}) = P({3}) = . Justify your answer.
3
S4. Suppose X1,…, Xn are independent and have the same Cauchy
distribution with location parameter θ. The corresponding
probability density function is given by
1
f (x : θ ) = , x, θ ∈ ℜ .
π [1 + ( x − θ ) 2 ]
Suppose we want to find the MLE of θ.
(a) Show that, for each i
∂ log f ( X i ;θ ) ∂ 2 log f ( X i ;θ ) 1
Eθ
∂θ = 0, Eθ −
∂θ 2
=
2
S6. Consider a randomized block design with two blocks and two
treatments A and B. The following table gives the yields:
Treatment A Treatment B
Block 1 a b
Block 2 c d
13
(a) How many orthogonal contrasts are possible with a, b, c and d?
Write down all of them.
(b) Identify the contrasts representing block effects, treatment effects
and error.
(c) Show that their sum of squares equals the total sum of squares.
S9. Let X=(X1,…, Xn) be a sample from the uniform distribution on (0,
θ). Show the following:
14
(a) For testing H0: θ ≤θ0 against H1: θ ≥θ0, any test is UMP at level
α for which Eθ 0 (φ ( X )) = α , Eθ 0 (φ ( X )) ≤ α for θ ≤ θ 0 , and φ(x) =
1 when max ( x1 ,...., x n ) > θ0.
(b) For testing H0: θ = θ0 against H1: θ ≠ θ0, a unique UMP test
exits, and is given by φ(x) = 1 when max ( x1 ,...., x n ) > θ0 or max
( x1 ,...., x n ) ≤ θ0 α 1 / n and φ(x) = 0 otherwise.
of c.
S12. Let X1, X2,…,Xn (Xi= (xi1, xi2, …, xip), i=1, 2, …, n) be n random
samples from a p-variate normal population with mean vector µ and
covariance matrix I.
15
Further, let S = ((sjk)) denote the sample sums of squares and
products matrix, namely
s jk = ∑i =1 ( xij − x j )( xik − x k ),1 ≤ j , k ≤ p, where
n
1 n
xj = ∑ xij ,1 ≤ j ≤ p.
n i =1
Obtain the distribution of l Sl where l ∈ ℜ , l ≠ 0.
' k
µ1 σ 11 σ 12 σ 13
~
µ = µ2 , ∑ = σ 21 σ 22 σ 23
µ σ
3 31 σ 32 σ 33
Show that E(X1,X2,X3) = µ1µ 2 µ 3 + µ1σ 23 + µ 2σ 31 + µ 3σ 12 .
(b) Suppose X = (X1, X2, X3, X4)T ∼ N4( 0, ∑ ), where ∑ = ((σ ij )).
~
Physics
16
A 4
(b) The nucleus BZ decays by alpha ( He2 ) emission with a half-life
T to the nucleus C ZA−−24 which in turn, decays by beta (electron)
T A− 4
emission with a half-life to the nucleus DZ −1 . If at time t = 0 ,
4
the decay chain B → C → D had started with B0 number of B
nuclei only, then find out the time t at which the number of C
nuclei will be maximum.
P2. (a) Consider a material that has two solid phases, a metallic phase
and an insulator phase. The phase transition takes place at the
temperature T0 which is well below the Debye temperature for
either phase. The high temperature phase is metastable all the
way down to T = 0 and the speed of sound, cs, is the same for
each phase. The contribution to the heat capacity coming from
the free electrons to the metal is
k
C e = ρ e Vγ T , γ = 3π 2
4T F
(ii) If the wave function for the ground state of the hydrogen
atom is given by
17
−r
1 a0
ψ = e
πa 03
18
where m and ω are constants; x, y are the generalized co-ordinates
for which px, py are the respective conjugate momenta. Show that
the expressions (x py -y px)n, n=1,2,3,… are constants of motion
for this system.
P5. (a) A particle describes the curve rn = acosnθ under a force P towards
the pole, r, θ being the polar coordinates. Find the law of force.
(b) Two particles, each with speed v, move in a plane making an
angle 2θ with each other as seen from the laboratory frame.
Calculate the relative speed (under the formalism of special
relativity) of one with respect to the other.
(b) Two spherical cavities of radii a and b are hollowed out from
the interior of a neutral conducting sphere of radius R. Two point
charges of magnitude qa and qb are now placed at the centres of the
two cavities as shown in the figure.
P7. A person standing at the rear end of a train fires a bullet towards
the front of the train. The speed of the bullet and the length of the
train, as measured in the frame of the train, are 0.5c and 400m
respectively. The train is moving at 0.6c as measured by an
observer on the ground. What does the ground observer measure
for
19
(i) the length of the train,
(ii) the speed of the bullet, and
(iii) the time required for the bullet to reach the front of the train?
P9. In the circuit shown below, the peak current flowing through the
different branches are indicated. Derive the value of the total
power delivered by the source.
P10. Two heavy bodies A and B , each having charge − Q , are kept
rigidly fixed at a distance 2a apart. A small particle C of mass m
and charge + q ( << Q ), is placed at the midpoint of the straight
line joining the centers of A and B . C is now displaced slightly
along a direction perpendicular to the line joining A and B , and
then released. Find the period of the resultant oscillatory motion of
C , assuming its displacement y << a .
20
If instead, C is slightly displaced towards A , then find the
instantaneous velocity of C , when the distance between A and C
a
is .
2
n?
P12. Consider the following truth table where A, B and C are Boolean
inputs and T is the Boolean output.
A B C T
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Express T in a product-of-sum form and hence, show how T can be
implemented using NOR gates only.
P13. (a) Find the relationship between L, C and R in the circuit shown in
the figure such that the impedance of the circuit is independent
of frequency. Find out the impedance.
21
(b) Find the value of R and the current flowing through R shown in
the figure when the current is zero through R′.
τ B(τ )
P14. A gas obeys the equation of state P = + where B(τ ) is a
V V2
function of temperature τ only. The gas is initially at temperature
τ and volume V0 and is expanded isothermally and reversibly to
volume V1 = 2V0 .
(a) Find the work done in the expansion.
(b) Find the heat absorbed in the expansion.
∂S ∂P
(Hint: Use the relation ∂V = ∂τ where the symbols have
τ V
their usual meaning.)
22
(b) Also calculate the value of the common-mode rejection
ratio for R'/R = R1/R2.
Computer Science
A → Bb A→a
B →Cc B→b
C → Aa C→c
23
State any assumption that you may need to make.
(c) Let the relation have 5000 tuples with 10 tuples/page. In case of
a hashed file, each bucket needs 10 pages. In case of B+ tree,
the index structure itself needs 2 pages. If it takes 25 msecs. to
read or write a disk page, what would be the disk access time
for answering the above queries?
(d) Relation R(A,B,C) supports the following functional
dependencies:
24
A → B, B → C and C→A.
(i) Identify the key attributes.
(ii) Explain whether R is in BCNF.
(iii) If R is not in BCNF, decompose to create a set of
normalized relations satisfying BCNF.
(iv) If R does not support the functional dependencies B → C,
but the other two are maintained, would R be in BCNF? If not,
decompose R to normalized relations satisfying BCNF.
C6. (a) A disk has 500 bytes/sector, 100 sectors/track, 20 heads and
1000 cylinders. The speed of rotation of the disk is 6000 rpm.
The average seek time is 10 millisecs. A file of size 50 MB is
written from the beginning of a cylinder and a new cylinder
will be allocated only after the first cylinder is totally occupied.
i) Find the maximum transfer rate.
ii) How much time will be required to transfer the file of 50
MB written on the disk? Ignore the rotational delay but not
the seek time.
25
Suppose that we model the crossing as follows:
- each vehicle is modeled by a process,
- the crossing is modeled as a shared data structure. Assume that
the vehicles can only move straight through the intersection (no
left or right turns). Using read-write locks (or any standard
synchronization primitive), you have to device a
synchronization scheme for the processes. Your scheme should
satisfy the following criteria:
i) prevent collisions,
ii) prevent deadlock, and
iii) maximize concurrency but prevent indefinite waiting
(starvation).
Write down the algorithm that each vehicle must follow in order
to pass through the crossing. Justify that your algorithm satisfies
the given criteria.
26
connected through a 1 Mbps link, while Y and Z are connected
by a 512 Kbps link.
C8. Consider a binary operation shuffle on two strings, that is just like
shuffling a deck of cards. For example, the operation shuffle on
strings ab and cd, denoted by ab || cd, gives the set of strings
{abcd, acbd, acdb, cabd, cadb, cdab}.
27
(b) A certain four-input gate G realizes the switching function
G(a, b, c, d) = abc + bcd.
Assuming that the input variables are available in both
complemented and uncomplemented forms:
(i) Show a realization of the function
f(u, v, w, x) = Σ (0, 1, 6, 9, 10, 11, 14, 15)
with only three G gates and one OR gate.
(ii) Can all switching functions be realized with {G, OR}
logic set?
28
(c) Suppose the memory location to be accessed is 000D0237 (in
hex). What cache block will be accessed for this memory
location in the direct-mapped organization and what will be
the value of the tag field? If instead, the cache memory were
organized in a fully associative manner, what will be the
corresponding value of the tag field?
(d) Express the following numbers in IEEE 754-1985 single
precision floating-point format:
(i) -0 (ii) 2.5 × 2-130 (iii) 230 (iv) 0.875 (v) (-3)1/8.
C14. (a) The order of a regular language L is the smallest integer k for
which Lk = Lk+1, if there exists such a k, and ∞ otherwise.
(i) What is the order of the regular language a + (aa)(aaa)*?
(ii) Show that the order of L is finite if and only if there is an
integer k such that Lk = L*, and that in this case the order of L
is the smallest k such that Lk = L*.
C15. (a) You are given an unordered sequence of n integers with many
duplications, such that the number of distinct integers in the
sequence is O(log n). Design a sorting algorithm and its
necessary data structure(s), which can sort the sequence using
29
at most O(n log(log n)) time. (You have to justify the time
complexity of your proposed algorithm.)
(b) Let A be a real-valued matrix of order n x n already stored in
memory. Its (i, j)-th element is denoted by a[i, j]. The
elements of the matrix A satisfy the following property:
Let the largest element in row i occur in column li. Now, for
any two rows i1, i2, if i1 < i2, then li1 ≤ li2 .
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12
(a)
Row I l(i)
1 2
2 3
3 3
4 4
5 5
(b)
30
C16. You are given the following file abc.h:
#include <stdio.h>
#define SQR(x) (x*x)
#define ADD1(x) (x=x+1)
#define BeginProgram int main(int ac,char *av[]){
#define EndProgram return 1; }
For each of the following code fragments, what will be the output?
(i) #include "abc.h"
main()
{ int y = 4; printf("%d\n", SQR(y+1)); }
(ii) #include "abc.h"
BeginProgram
int y=3; printf("%d\n", SQR(ADD1(y)));
EndProgram
31
(b) A composite shaft of Aluminium and Brass is rigidly supported
at the ends A and C, as shown in the figure below. The shaft is
subjected to a shearing stress by the application of a torque T.
Calculate the ratio of lengths AB : BC if each part of the shaft is
stressed to its maximum limit (beyond which the composite shaft
will break). Assume the maximum shear stress of Brass and
Aluminium to be 560 kg/cm2 and 420 kg/cm2 respectively. Also
assume that the modulus of rigidity of Brass is twice that of
Aluminium.
E3. Find the acceleration of the block of mass M in the situation shown
below. The coefficient of friction between the blocks is µ1 and that
between the bigger block and the ground is µ2.
E5. The truss shown in the figure rotates around the pivot O in a vertical
plane at a constant angular speed ω. Four equal masses (m) hang from
32
the points B, C, D and E. The members of the truss are rigid,
weightless and of equal length. Find a condition on the angular speed
ω so that there is compression in the member OE.
E6. If the inputs A and B to the circuit shown below can be either 0 volt
or 5 volts,
(i) what would be the corresponding voltages at output Z, and
(ii) what operation is being performed by this circuit ?
Assume that the transistor and the diodes are ideal and base to
emitter saturation voltage = 0.5 volts.
33
to become 12 cm and 13 cm of Hg, respectively. Assume that the
coefficient of viscosity η of oxygen is 0.000199 cgs unit.
300 × 3.6
E8. (a) Ice in a cold storage melts at a rate of kg/hour when the
80 × 4.2
external temperature is 27oC. Find the minimum power output of
the refrigerator motor, which just prevents the ice from melting.
(Latent heat of fusion of ice = 80 cal/gm.)
34
E12. A proton of velocity 107 m/s is projected at right angles to a uniform
magnetic induction field of 0.1 w/m2. How much is the path of the
particle deflected from a straight line after it has traversed a distance
of 1 cm? How long does it take for the proton to traverse a 900 arc?
E13. (a) State the two necessary conditions under which a feedback
amplifier circuit becomes an oscillator.
(b) A two-stage FET phase shift oscillator is shown in the diagram
below.
E14. A circular disc of radius 10cm is rotated about its own axis in a
uniform magnetic field of 100 weber/m2, the magnetic field being
perpendicular to the plane of the disc. Will there be any voltage
developed across the disc? If so, then find the magnitude of this
voltage when the speed of rotation of the disc is 1200 rpm.
35
E16. A d.c. shunt motor running at a speed of 500rpm draws 44KW
power with a line voltage of 220V from a d.c. shunt generator. The
field resistance and the armature resistance of both the machines are
55 Ω and 0.025 Ω respectively. However, the voltage drop per brush
is 1.05V in the motor, and that in the generator is 0.95V. Calculate
(a) the speed of the generator in rpm, and
(b) the efficiency of the overall system ignoring losses other
than the copper-loss and the loss at the brushes.
36
(b) Find the open-circuit transfer impedance of the lattice shown in
the figure below and determine the condition for having no zeros in
the right-half plane, i.e., for positive frequencies.
E21. A logic circuit operating on Binary Coded Decimal (BCD) digits has
four inputs X1, X2, X3, and X4, where X1X2X3X4 represents a BCD
digit. The circuit has two output lines Z1 and Z2. Output Z1 is 1 only
when the decimal digit corresponding to the inputs X1, X2, X3, X4 is
0 or a power of 2. Output Z2 is 1 only when the decimal digit
corresponding to the inputs is 1 or a power of 3. Find a minimum
cost realization of the above circuit using NAND gates.
37
E23. Write a C program to generate a sequence of positive integers
between 1 and N, such that each of them has only 2 or/and 3 as
prime factors. For example, the first seven elements of the sequence
are: 2, 3, 4, 6, 8, 9, 12. Justify the steps of your algorithm.
E24. Design a circuit using the module, as shown in the figure below, to
compute a solution of the following set of equations:
3x + 6y – 10 = 0
2x – y – 8 = 0
A module consists of an ideal OP-AMP and 3 resistors, and you may
use multiple copies of such a module. Voltage inverters and sources
may be used, if required.
38
Test Code: PCB (short answer type) 2014
The selection test for M.Tech. in Computer Science will consist of two parts.
• Test MMA (objective type) in the forenoon session is the 1st part, and
• Test PCB (short answer type) in the afternoon session is the 2nd part.
The PCB test will consist of two groups.
The syllabus and sample questions for the MMA test are available separately. The
syllabus and sample questions for the PCB test are given below.
Note:
1. Not all questions in this sample set are of equal difficulty. They may not carry
equal marks in the test. More sample questions are available on the website
for M.Tech(CS) at http://www.isical.ac.in/∼deanweb/MTECHCSSQ.html
2. Each of the two tests MMA and PCB, will have individual qualifying marks.
1
Elementary Euclidean geometry and trigonometry.
Elementary number theory, divisibility, congruences, primality.
Determinants, matrices, solutions of linear equations, vector spaces, linear indepen-
dence, dimension, rank and inverse.
Group B
Mathematics
In addition to the syllabus for Mathematics in Group A, the syllabus includes:
Calculus and real analysis – real numbers, basic properties, convergence of se-
quences and series, limits, continuity, uniform continuity of functions, differentia-
bility of functions of one or more variables and applications, indefinite integral,
fundamental theorem of Calculus, Riemann integration, improper integrals, double
and multiple integrals and applications, sequences and series of functions, uniform
convergence.
Linear algebra – vector spaces and linear transformations, matrices and systems
of linear equations, characteristic roots and characteristic vectors, Cayley-Hamilton
theorem, canonical forms, quadratic forms.
Graph Theory – connectedness, trees, vertex coloring, planar graphs, Eulerian
graphs, Hamiltonian graphs, digraphs and tournaments.
Abstract algebra – groups, subgroups, cosets, Lagrange’s theorem, normal sub-
groups and quotient groups, permutation groups, rings, subrings, ideals, integral
domains, fields, characteristics of a field, polynomial rings, unique factorization
domains, field extensions, finite fields.
Differential equations – solutions of ordinary and partial differential equations and
applications.
Statistics
Notions of sample space and probability, combinatorial probability, conditional
probability, Bayes’ theorem and independence.
Random variable and expectation, moments, standard univariate discrete and con-
tinuous distributions, sampling distribution of statistics based on normal samples,
central limit theorem, approximation of binomial to normal, Poisson law.
Multinomial, bivariate normal and multivariate normal distributions.
Descriptive statistical measures, product-moment correlation, partial and multiple
correlation.
Regression – simple and multiple.
Elementary theory and methods of estimation – unbiasedness, minimum variance,
sufficiency, maximum likelihood method, method of moments, least squares meth-
ods.
Tests of hypotheses – basic concepts and simple applications of Neyman-Pearson
lemma, confidence intervals.
2
Tests of regression, elements of non-parametric inference, contingency tables and
Chi-square, ANOVA, basic designs (CRD/RBD/LSD) and their analyses, elements
of factorial designs.
Conventional sampling techniques, ratio and regression methods of estimation.
Physics
3
Computer Science
Data structures – array, stack, queue, linked list, binary tree, heap, AVL tree, B-
tree.
Programming languages – Fundamental concepts – abstract data types, procedure
call and parameter passing, languages like C and C++.
Design and analysis of algorithms – Asymptotic notation, sorting, selection, search-
ing.
Computer organization and architecture – Number representation, computer arith-
metic, memory organization, I/O organization, microprogramming, pipelining, in-
struction level parallelism.
Operating systems – Memory management, processor management, critical section
problem, deadlocks, device management, file systems.
Formal languages and automata theory – Finite automata and regular expressions,
pushdown automata, context-free grammars, Turing machines, elements of unde-
cidability.
Principles of Compiler Construction – Lexical analyzer, parser, syntax-directed
translation, intermediate code generation.
Database management systems – Relational model, relational algebra, relational
calculus, functional dependency, normalization (up to third normal form).
Computer networks – LAN technology – Bus/tree, Ring, Star; MAC protocols;
WAN technology – circuit switching, packet switching; data communications –
data encoding, routing, flow control, error detection/correction, Inter-networking,
TCP/IP networking including IPv4.
Switching Theory and Logic Design – Boolean algebra, minimization of Boolean
functions, combinational and sequential circuits - synthesis and design.
Engineering and Technology
C Programming language.
Gravitation, moments of inertia, particle dynamics, elasticity, friction, strength of
materials, surface tension and viscosity.
Laws of thermodynamics and heat engines.
Electrostatics, magnetostatics and electromagnetic induction.
Laws of electrical circuits – transient and steady state responses of resistive and
reactive circuits.
D.C. generators, D.C. motors, induction motors, alternators, transformers.
Diode circuits, bipolar & FET devices and circuits, transistor circuits, oscillator,
multi-vibrator, operational amplifier.
Digital circuits – combinatorial and sequential circuits, multiplexer, de-multiplexer,
counter, A/D and D/A converters.
Boolean algebra, minimization of switching functions.
4
SAMPLE QUESTIONS
Group A
A1. How many times will the digit ‘7’ be written when listing the integers from 1
to 1000? Justify your answer.
A2. For sets A and B, define A∆B = (Ā ∩ B) ∪ (A ∩ B̄). Show the following
for any three sets A, B and C.
(a) A∆A = ∅.
(b) A∆(B∆C) = (A∆B)∆C.
(c) If A∆B = A∆C then B = C.
A3. In a group of n persons, each person is asked to write down the sum of the
ages of all the other (n − 1) persons. Suppose the sums so obtained are
s1 , . . . , sn . It is now desired to find the actual ages of the persons from these
values.
A7. Find all pairs of prime numbers p, q such that p + q = 18(p − q). Justify your
answer.
• P2 = P,
• Q2 = Q, and
5
• I − P − Q is invertible, where I is a n × n identity matrix.
6
Group B
Mathematics
{x : Ax = 0} = {x : A2 x = 0}.
(c) Let
2 −1 −1
1
A = −1 2 −1 .
3
−1 −1 2
Which of the following statements are true? In each case, justify your
answer.
(i) The rank of A is equal to the trace of A.
(ii) The determinant of A is equal to the determinant of An for all n >
1.
M3. (a) (i) For 0 ≤ θ ≤ π/2, show that sin θ ≥ 2θ/π.
(ii) Hence or otherwise show that for λ < 1,
Z π/2
λ
lim x e−x sin θ dθ = 0.
x→∞ 0
P
P √an ≥−p 0, n = 1, 2, . . . be such that
(b) Let an converges. Show that
an n converges for every p > 1/2.
M4. (a) Let a1 , a2 , . . . be integers and suppose there exists an integer N such
X∞
an
that an = (n − 1) for all n ≥ N . Show that is rational.
n=1
n!
7
(b) Let 0 < s1 , s2 , s3 < 1. Show that there exists exactly one x ∈ (0, ∞)
such that
sx1 + sx2 + sx3 = 1.
M7. (a) Let S and T be two subsets of a finite group (G, +) such that |S|+|T | >
|G|. Here |X| is the number of elements in a set X. Then prove that
S + T = G, where S + T = {s + t : s ∈ S, t ∈ T }.
8
M9. (a) Let f : R → R be a function satisfying
x
f (x) = f for all x 6= 1.
1−x
Assuming that f is continuous at 0, find all possible such f .
(b) Z
For
any
Z real-valued
continuous
Z function f on R, show that
x u x
f (t)dt du = (x − u)f (u)du for 0 < u < x.
0 0 0
M10 (i) GL(2, Z2 ) denotes the group of 2 × 2 invertible matrices with en-
tries in Z2 = {0, 1}:
1 0 0 1 1 1 1 0 1 1 0 1
, , , , , .
0 1 1 0 0 1 1 1 1 0 1 1
The operation in GL(2, Z2 ) is matrix multiplication with all the
arithmetic done in Z2 .
1 1
Is the cyclic subgroup generated by a normal subgroup?
0 1
Justify your answer.
(ii) Consider the set A = {(0, 0), (1, 1), (2, 2)}.
(i) Prove that A is a subring of Z3 × Z3 .
(ii) Prove or disprove: A is an ideal of Z3 × Z3 .
M11 (i) Given a simple graph G = (V, E) with V = {v1 , v2 , · · · , vn } and
E = {e1 , e2 , · · · , em }, let B = (bij )n×m be the matrix such that
bij = 1 if vi ∈ ej
= 0 otherwise .
Let A be the adjacency matrix of G, and D the diagonal matrix
with the degree sequence [d(v1 ), d(v2 ), · · · , d(vn )] on the diagonal.
Show that BB T = A + D.
(ii) Show that in a tree, there is a vertex common to all the longest paths
in the tree.
M12 (a) Consider the differential equation:
ex sin ydx + ex cos ydy = y sin(xy)dx + x sin(xy)dy.
Find the equation of the particular curve that satisfies the above
differential equation and passes through the point 0, π2 .
(b) Let the function f be four times continuously differentiable on
[−1, 1] with f (4) (0) 6= 0. For each n ≥ 1, let
1 1 1 ′′ 1
f = f (0) + f ′ (0) + 2 f (0) + 3 f (3) (θn ),
n n 2n 6n
9
where 0 < θn < n1 .
1
Show that nθn → 4
as n → ∞.
10
Statistics
E(y1 ) = θ0 + θ1 + θ 2 ,
E(y2 ) = θ0 + θ1 + θ 3 ,
E(y3 ) = θ0 + θ2 + θ 3 ,
E(y4 ) = θ0 + θ1 + θ 2 .
3
X
(a) Determine the condition under which the parametric function ci θi is
i=0
estimable for known constants ci , i = 0, 1, 2, 3.
11
(b) Obtain the least squares estimates of the parameters θ0 , θ1 , θ2 and θ3 .
(c) Obtain the best linear unbiased estimator of (2θ1 − θ2 − θ3 ) and also
determine its variance.
(a) Find the most powerful test at level α = 0.05 to test whether the coin is
fair against the alternative that the coin is more likely to show up heads.
(b) What will be the conclusion of the test if there are exactly 7 heads in 10
tosses?
(c) Find the power function of this test.
S9. (a) Each time you buy a product, you get a coupon which can be any one
of N different types of coupons. Assuming that the probability that a
coupon of type i occurs is pi , find the distribution of the random variable
12
X which denotes the total number of products to be bought in order to
have all types of coupons.
(b) A box contains 6n tickets numbered 0, 1, 2, . . . , 6n − 1. Three tickets
are drawn at random without replacement. Find the probability that the
sum of the three numbers selected is 6n.
S10. Let
θk −θx k−1
p(x; θ, k) = e x , where 0 < x < ∞, θ > 0 and k > 0.
Γ(k)
S11. (a) Suppose in a coin tossing experiment with 2n trials, an unbiased coin
is flipped n times, while a different (possibly biased) spurious coin is
flipped remaining n times by mistake. The total number of heads is
found to be S2n in the 2n trials.
(i) Based on S2n , describe a test for the hypothesis that the spurious
coin is actually unbiased.
(ii) Give an approximate cut-off point at α = 0.05, assuming n is large.
(b) Let x1 , x2 , . . . , xm and y1 , y2 , . . . , yn be independent observations from
populations with continuous distribution functions F1 and F2 . Denote
by m1 and n1 the number of x’s and y’s exceeding the kth order statistic
of the combined sample.
Derive a nonparametric test of the null hypothesis H0 : F1 = F2 , based
on the propability distribution of (m1 , n1 ) under H0 .
S12. Consider a distribution of shots fired at a target point. Let (X, Y ) be the
coordinates (random variables) representing the errors of a shot with respect
to the two orthogonal axes through the target point.
13
Let the following hypotheses be true:
I. The marginal density functions p(x), q(y) of the errors X and Y are
continuous.
II. The probability density at (x, y) depends only on the distance r = (x2 +
y 2 )1/2 from the target point.
III. X and Y are independent.
Show that X and Y are identically distributed, and the probability distribution
function of X is
1 2 2
√ e−x /2σ for some σ > 0.
σ 2π
14
Physics
P1. (a) Consider two partially overlapping spherical charge distributions with
constant charge densities +ρ and −ρ. Each sphere is of radius R. The
vector connecting the center of the negative charge sphere to the center
~ Find the electrostatic field at any
of the positive charge sphere is D.
point in the overlapping region.
(b) Consider two wire loops L1 and L2 . Show that the magnetic flux linked
to L1 when current I flows in L2 , is same as the magnetic flux linked to
L2 when current I flows in L1 .
(c) There are two co-axial solenoids. The inner short solenoid has radius
R, length L, N1 number of turns per unit length. The outer solenoid is
very long with N2 number of turns per unit length. Find the magnetic
flux linked with the outer solenoid when current I flows in the inner
solenoid. What is the coefficient of mutual inductance of the system of
solenoids?
(Hint: You can use the answer of (b) in (c).)
P2. (a) A particle is falling freely from a height h at 30◦ latitude in the northern
q
3
hemisphere. Show that the particle will undergo a deflection of ω 2h 3g
in the eastward direction, where ω is the rotational velocity of the earth
about its own axis and g is the acceleration due to gravity.
→
−
(b) A particle of mass m is moving in a plane in the field of force F =
−brkr cos θ, where k is a constant, rb is the radial unit vector and θ is the
polar angle.
(i) Write the Lagrangian of the system.
(ii) Show that the Lagrange’s equations of motion are:
A. mr̈ − mrθ̇2 + kr cos θ = 0;
B. mr2 θ̇ 6= constant.
(iii) Interpret (ii)B in the context of Kepler’s second law.
15
(b) A free particle of mass m moves in one dimension. At time t = 0, the
normalized wave function of the particle is
ψ(x, 0, σx2 ) = (2πσx2 )−1/4 exp(−x2 /4σx2 )
where σx2 = hx2 i.
p
(i) Compute the momentum spread σp = hp2 i − hpi2 associated
with this wave function.
(ii) Show that at time t > 0 the probability density of the
particle has the form |ψ(x, 0, t)|2 = |ψ(x, 0, σx2 + σp2 t2 /m2 )|2 .
P4. (a) Calculate the following properties of the 2p − 1s electromagnetic tran-
sition in an atom formed by a muon and a strontium nucleus (Z = 38):
(i) the fine structure splitting energy;
(ii) the natural line-width (i.e., the part of the line-width of an absorp-
tion or emission line that results from the finite lifetimes of one or
both of the energy levels between which the transition takes place).
Given: the lifetime of the 2p state of hydrogen is 10−9 s.
(b) Consider the following high energy reactions. Check whether the reac-
tions are allowed or forbidden. If allowed, mention the corresponding
decay process, and if forbidden, mention the law that is violated.
(i) µ+ → e + + γ
(ii) p + p̄ → γ
(iii) p → e+ + νe
(iv) p + n → p + Λ0
(v) p → e+ + n + νe
P5. (a) How does one understand molecular mean free path in the context of
molecular kinetic theory of gases? Obtain the analytic form of the law
governing the distribution of free paths in an ideal gas.
(b) Calculate the mean free path, the collision rate and the molecular di-
ameter for Hydrogen gas molecules having the following particulars:
molecular weight of Hydrogen = 2.016 gm; viscosity, η = 85 × 10−6
dynes/cm2 /velocity gradient; mean speed, c = 16 × 104 cm/sec; density,
ρ = 0.000089 gm/cc.
P6. (a) A silicon semiconductor is in the shape of a rectangular bar with a
cross-section area of 100µm2 and a length of 0.1cm. It is doped with
5×1016 cm−3 arsenic atoms. The temperature is T = 300K. Assume that
electron has mobility µn = 1000cm2 V−1 s−1 and charge qe = 1.6×1019 .
If 5V is applied across the length of the bar, calculate
16
(i) the average drift velocity of the electrons, and
(ii) the current in the above semiconductor.
(b) Draw Karnaugh maps for f1 = xw + yw + x′ y ′ z and f2 = x′ y + yw′ .
Hence derive the Karnaugh maps for the functions g = f1 f2 and h =
f1 +f2 . Simplify the maps for g and h and give the resulting expressions
in the sum of products form.
17
Computer Science
C1. (a) How many asterisks (*) in terms of k will be printed by the following C
function, when called as count(m) where m = 3k ? Justify your answer.
Assume that 4 bytes are used to store an integer in C and k is such that
3k can be stored in 4 bytes.
void count(int n)
{
printf("*");
if(n>1)
{
count(n/3);
count(n/3);
count(n/3);
}
}
C2. Give an efficient implementation for a data structure STACK MAX to support
an operation max that reports the current maximum among all elements in
the stack. Usual stack operations (createEmpty, push, pop) are also to
be supported.
How many bytes are needed to store your data structure after the follow-
ing operations: createEmpty, push(5), push(6), push(7), pop, max,
push(6), push(8), pop, pop, max, push(5). Assume that an integer can
be stored in 4 bytes.
C3. You are given an array X[ ]. The size of the array is very large but unknown.
The first few elements of the array are distinct positive integers in sorted
order. The rest of the elements are 0. The number of positive integers in the
array is also not known.
18
Design an algorithm that takes a positive integer y as input and finds the
position of y in X. Your algorithm should return “Not found” if y is not in
the array. You will get no credit if the complexity of your algorithm is linear
(or higher) in the number of positive integers in X.
C4. (a) Prove or disprove the following statement: The union of a regular lan-
guage with a disjoint non-regular language over the same alphabet can
never be regular.
[Hint: You may use the closure properties of regular languages.]
(b) It is known that the language L1 = {0n 1n 2i | i 6= n} is not a context free
language (CFL). Now consider the language
L2 = {0i 1n 2n | i 6= n}. We can prove L2 is not a CFL by convert-
ing L2 into L1 by applying two operations, both known to be closed on
CFLs. What are the two operations you will use for this conversion?
Justify your answer.
C5. Consider three relations R1(X, Y, Z), R2(M , N, P ), and R3(N, X). The
primary keys of the relations are underlined. The relations have 100, 30, and
400 tuples, respectively. The space requirements for different attributes are:
X = 30 bytes, Y = 10 bytes, Z = 10 bytes, M = 20 bytes, N = 20 bytes,
and P = 10 bytes. Let V (A, R) signify the variety of values that attribute
A may have in the relation R. Let V (N, R2) = 15 and V (N, R3) = 300.
Assume that the distribution of values is uniform.
(a) If R1, R2, and R3 are to be joined, find the order of join for the min-
imum cost. The cost of a join is defined as the total space required by
the intermediate relations. Justify your answer.
(b) Calculate the minimum number of disk accesses (including both reading
the relations and writing the results) required to join R1 and R3 using
block-oriented loop algorithm. Assume that (i) 10 tuples occupy a block
and (ii) the smaller of the two relations can be totally accommodated in
main memory during execution of the join.
C6. (a) Consider three processes, P1 , P2 , and P3 . Their start times and execu-
tion times are given below.
Process Start time Execution time
P1 t = 0 ms 100 ms
P2 t = 25 ms 50 ms
P3 t = 50 ms 20 ms
Let ∆ be the amount of time taken by the kernel to complete a context
switch from any process Pi to Pj . For what values of ∆ will the average
19
turnaround time for P1 , P2 , P3 be reduced by choosing a Shortest Re-
maining Time First scheduling policy over a Shortest Job First policy?
(b) The circuit shown in the following figure computes a Boolean function
F . Assuming that all gates cost Rs. 5 per input (i.e., an inverter costs Rs.
5, a 2-input gate costs Rs. 10, etc.), find the minimum cost realization
of F using only inverters, AND / OR gates.
A
D
F
C
20
sn−1 ⊕ (an−1 sn−1 ) = bn−1 (sn−1 ⊕ an−1 )
where ⊕ denotes the Boolean XOR operation. You may use the Boolean
identity: X + Y = X ⊕ Y ⊕ (XY ) to prove your result.
(b) Consider a machine with 5 stages F , D, X, M , W , where F denotes
instruction fetch, D - instruction decode and register fetch, X - exe-
cute/address calculation, M - memory access, and W - write back to
a register. The stage F needs 9 nanoseconds (ns), D needs 3 ns, X
requires 7 ns, M needs 9 ns, and W takes 2 ns. Let M1 denote a non-
pipelined implementation of the machine, where each instruction has to
be executed in a single clock cycle. Let M2 denote a 5-stage pipelined
version of the machine. Assume that pipeline overhead is 1 ns for each
stage. Calculate the maximum clock frequency that can be used in M1
and in M2 .
C9. (a) Read the C code given below. Use the four integers corresponding to
the four digits of your question booklet number as input to the program.
For example, if your question booklet number is 9830, then your input
would be this: 9 8 3 0
#include<stdio.h>
#define STACKSIZE 2
STACK index[STACKSIZE];
STACK *ptr = index;
21
ptr[count].item.N = i;
ptr[count].item.D = j;
ptr[count].number = count+1;
}
if(count == 0) return(1.0);
else{
if ((Type)ptr[count-1].item.D == 0)
return 1.0;
val = (Type)ptr[count-1].item.N/
(Type)ptr[count-1].item.D;
return(Doit(--count) * val);
}
}
void main() {
int i, j, count=0;
C10. (a) A palindrome over the alphabet Σ = {a, b, . . . , z}, (|Σ| = 26) is a string
that reads the same both forwards and backwards. For example, tenet is
a palindrome over Σ. Let P (n) be the number of palindromes of length
n over Σ. Derive an expression for P (n) in terms of n. You may use
recurrence relations.
22
(b) For any two languages L1 , L2 ⊆ {0, 1}∗ , their symmetric difference
SD(L1 , L2 ) is the set of strings that are in exactly one of L1 and L2 . For
example, if L1 = {00, 101} and L2 = {11, 00}, then SD(L1 , L2 ) = {11,
101}.
(i) Suppose A is the set of all strings of the form 0∗ 1∗ , and B is the set
of all strings of the form 1∗ 0∗ .
• List all the strings of length 3 or less in SD (A, B).
• Write a regular expression for SD(A, B).
(ii) Is SD (L1 , L2 ) necessarily a Context-Free language? Justify your
answer.
C11. (a) You are given a sorted list A of n real numbers a1 , a2 , . . . , an with values
in the range (α, β). Write an O(n) time algorithm to partition A into two
disjoint non-empty subsets A1 and A2 such that
maxai ∈A1 |α − ai | + maxaj ∈A2 |β − aj |
is minimum among all such possible partitions.
(b) Let A[1 . . . n] be a given array of n integers, where n = 2m . The follow-
ing two operations are the only ones to be applied to A:
• Add(i, y): Increment the value of A[i] by y.
P
• Partial-sum(k): Print the current value of ki=1 A[i].
One needs to perform these two operations multiple times in any given
order. Design a data structure to store A such that each invocation of
these two operations can be done in O(m) steps.
C12. Consider a singly linked list, with each node containing an integer and a
pointer to the next node. The last node of the list points to N U LL. You
are given two such lists A and B containing m and n nodes, respectively. An
intersection point between two linked lists is a node common to both.
You are not allowed to modify A and B. Partial credit may be given if your
algorithm uses more than Θ(1) additional space.
C13. (a) Let R and S be two relations, and l be an attribute common to R and S.
Let c be a condition over the attributes common to R and S. Prove or
disprove the following:
23
(i) Πl (R − S) = Πl (R) − Πl (S);
(ii) σc (R ⊲⊳ S) = σc (R) ⊲⊳ σc (S).
(b) Following are the steps executed by the CPU in a certain order, to pro-
cess an interrupt received from a device. Mention the
correct order of execution of these steps.
I. CPU executes the Interrupt Service Routine.
II. CPU uses the vector number to look up the address of the Interrupt
Service Routine to be executed.
III. CPU returns to the point of execution where it was interrupted.
IV. Interrupt Service Routine restores the saved registers from the stack.
V. CPU grants the interrupt for the device and sends interrupt ac-
knowledge to the device (IACK).
VI. Interrupt Service Routine saves the registers onto a stack.
VII. CPU receives the vector number from the device.
C14. (a) Consider two processes P1 and P2 entering the ready queue with the
following properties:
• P1 needs a total of 12 time units of CPU execution and
20 time units of I/O execution. After every 3 time units of CPU
work, 5 time units of I/O are executed for P1.
• P2 needs a total of 15 time units of CPU execution and no I/O. P2
arrives just after P1.
Report the schedules, and the corresponding completion times of P1 and
P2 for each of the following two scheduling strategies:
(i) Shortest Remaining Time First (preemptive), and
(ii) Round Robin, with a slice of 4 time units.
(b) What will happen to a packet sent to the IPv4 address 127.0.0.1?
(c) A 2km long LAN has 10Mbps bandwidth and uses CSMA/CD. The
signal travels along the wire at 2×108 m/s. What is the minimum packet
size that can be used on this network?
24
Engineering and Technology
E1. (a) A 50kW compound generator works on half-load with a terminal volt-
age of 250V. The shunt, series and armature windings have resistances
of 126Ω, 0.02Ω and 0.05Ω respectively. Calculate the total power gen-
erated at the armature when the machine is connected to short-shunt.
(b) A single phase 60kVA transformer delivers full load at 0.75 power factor
with 90% efficiency. If the same transformer works at half load at 0.70
power factor, its efficiency increases to 91.3%. Calculate the iron loss
of the transformer.
E2. Two long straight parallel wires stand 2 meters apart in air and carry currents
I1 and I2 in the same direction. The field intensity at a point midway between
the wires is 7.95 Ampere-turn per meter. The force on each wire per unit
length is 2.4 ×10−4 N. Assume that the absolute permeability of air is 4π ×
10−7 H per meter.
(a) Explain the nature of the force experienced between the two wires, i.e.
attractive or repulsive.
(b) Determine I1 and I2 .
(c) Another parallel wire carrying a current of 50 A in the opposite direction
is now placed midway between the two wires and in the same plane.
Determine the resultant force on this wire.
E3. A choke coil connected across a 500 V, 50 Hz supply takes 1 A current at a
power factor of 0.8.
(a) Determine the capacitance that must be placed in series with the choke
coil so that it resonates at 50 Hz.
(b) An additional capacitor is now connected in parallel with the above
combination in (a) to change the resonant frequency. Obtain an ex-
pression for the additional capacitance in terms of the new resonant fre-
quency.
E4. (a) The mechanical system shown in the figure below is loaded by a hori-
zontal 80 N force. The length of the spring is 500 mm. Each arm of the
mechanical system is also of length 500 mm as shown in the figure. Un-
der the influence of 80 N load, the spring is stretched to 600 mm but the
entire mechanical system including the spring remains in equilibrium.
Determine the stiffness of the spring. Note that the spring and the frame
are fixed at the pin position P. The other end of the spring is at R which
is a frictionless roller free to move along the vertical axis. Assume that
the mechanical joints between the arms are frictionless.
25
(b) A brake system is shown in the figure below. The solid disk of radius
1000 mm is being rotated at 196 rpm. The bar AB, of length 4000 mm,
is fixed at the end A and subjected to a downward load of 100 N at
the end B to stop the rotation of the disk. The bar AB (assumed to be
horizontal) touches the rotating disk at a point 500 mm from the fixed
end of the bar. The weight of the disk is 10 Kg and the coefficient of
friction between the bar and the disk is 0.5. Calculate the number of
revolutions the disk will make before coming to rest.
E5. (a) Air at 90◦ C and 605 Kg per square meter pressure is heated to 180◦ C
keeping the volume constant at 21 cubic meter. Find
(i) the final pressure, and
(ii) the change in the internal energy.
Note that the specific heat at constant pressure (Cp ), the specific heat at
constant volume (Cv ), and the mechanical equivalent of heat are 0.3, 0.2
and 420 Kg-meter per Kcal, respectively.
(b) A molten metal is forced through a cylindrical die at a
pressure of 168×103 Kg per square meter. Given that the density of
the molten metal is 2000 Kg per cubic meter and the specific heat of the
metal is 0.03, find the rise in temperature during this process. Assume
that the mechanical equivalent of heat is 420 Kg-meter per Kcal.
E6. (a) Calculate the current I flowing through the resistor R shown in the fol-
lowing figure (e1 < e2 < · · · < en ).
26
r r r
I
r1 + e1 r2 + e2 rn + n
e
− − − R
E8. (a) Consider the following circuit with an ideal Op-amp. Calculate Vo .
10 K
2V 5K
Vo
2K
1V 2K
(b) The following network uses four transconductor amplifiers and two ca-
pacitors to produce the output voltage Vo for the input voltage Vi .
27
Vo
gm gm gm gm
1 2 3 4
V
i _
+ + +
_ _ _
+
C C
1 2
Vo gm1 /gm4 .
H(s) = = g m2 C 2
Vi 1 + ( gm gm )s + ( gmC1 C 2
)s 2
3 4 gm 3 4
Q1
+ +
Q2 Re = 1K
Vi Vo
- -
(i) Draw the equivalent circuit using the small-signal hybrid parameter
model.
(ii) For the following values of h parameters for both transistors: hie =
1000 Ω, hf e = 100, hre = hoe = 0, determine the voltage amplifi-
cation Av and the input resistance Rin .
E10. The following is the skeleton of a C program that outputs the number of
occurrences of each of the ten digits in a given string of digits. Write the
codes for the portions marked as B1, B2, B3 and B4 with appropriate C
constructs.
#include<stdio.h>
#define base 10
28
/* This program outputs the numbers of 0’s, 1’s */
/* ,....., 9’s in an input string ending in $ */
int main() {
char b;
int i, a[base];
—–x—–
29