Test Code : RC (Short Answer Type) 2008

JRF in Computer and Communication Sciences

The Candidates for Junior Research Fellowship in Computer Science and
Communication Sciences will have to take two tests - Test MIII (objective
type) in the forenoon session and Test RC (short answer type) in the after-
noon session. The RC test booklet will have two groups as follows:
GROUP A
A test for all candidates in logical reasoning and basics of programming,
carrying 20 marks.
GROUP B
A test, divided into ve sections, carrying equal marks of 80 in the following
areas at M.Sc./M.E./M.Tech. level:
(i) Mathematics, (ii) Statistics, (iii) Physics, (iv)
Radiophysics/ Telecommunication/ Electronics/ Electrical Engg., and
(v) Computer Science.
A candidate has to answer questions from only one of these sec-
tions, according to his/her choice.
The syllabi and sample questions of the RC test are given overleaf.
1
Syllabus
Elements of Computing:
Logical reasoning, basics of programming (using pseudo-codes), Elementary
data types and arrays.
Mathematics:
Graph theory and combinatorics: Graphs and digraphs, paths and cycles,
trees, Eulerian graphs, Hamiltonian graphs, chromatic numbers, planar
graphs, tournaments, inclusion-exclusion principle, pigeon-hole principle.
Linear programming: Linear programming, simplex method, duality.
Linear algebra: Vector spaces, basis and dimension, linear transformations,
matrices, rank, inverse, determinant, systems of linear equations, character-
istic roots (eigen values) and characteristic vectors (eigen vectors), orthog-
onality and quadratic forms.
Abstract algebra: Groups, subgroups, cosets, Lagranges theorem, normal
subgroups and quotient groups, permutation groups, rings, subrings, ideals,
integral domains, elds, characteristic of a eld, polynomial rings, unique
factorization domains, eld extensions, nite elds.
Elementary number theory: Elementary number theory, divisibility, congru-
ences, primality.
Calculus and real analysis: Real numbers, basic properties, convergence
of sequences and series, limits, continuity, uniform continuity of functions,
dierentiability of functions of one or more variables and applications, in-
denite integral, fundamental theorem of calculus, Riemann integration, im-
proper integrals, double and multiple integrals and applications, sequences
and series of functions, uniform convergence.
Dierential equations: Solutions of ordinary and partial dierential equa-
tions and applications.
Statistics:
Probability Theory and Distributions: Basic probability theory, discrete and
continuous distributions, moments, characteristic functions, Markov chains.
Estimation and Inference: Sucient statistics, unbiased estimation, max-
imum likelihood estimation, consistency of estimates, most powerful and
uniformly most powerful tests, unbiased tests and uniformly most powerful
unbiased tests, condence sets.
2
Linear Models: Gauss-Markov set up and least squares theory, multiple
linear regression, one and two way analysis of variance.
Multivariate Analysis: Multivariate normal distribution, Wishart distribu-
tion, Hotellings T
2
test, principal component analysis, multiple and canon-
ical correlations, discriminant analysis, cluster analysis, factor analysis.
Physics:
Classical Mechanics: Variational principle and Lagranges equation, central
force problem, rigid body motion, Hamilton equation of motion, canonical
transformations, Hamilton Jacobi theory and action angle variables, La-
grangian and Hamiltonian formulation for continuous systems and elds,
relativistic mechanics.
Electrodynamics: Electromagnetic elds and potentials, electromagnetic ra-
diation, scattering, dispersion, relativistic electrodynamics.
Thermodynamics and Statistical Mechanics: Reviews of thermodynamics,
statistical basis of thermodynamics, density matrix formulation, ensem-
bles, partition function and its uses, Maxwell-Boltzmann, Bose-Einstein and
Fermi Dirac statistics, simple gases, Ising model.
Non-Relativistic Quantum Mechanics: Basics of quantum mechanics, the
two body problem and central potential, quantum particles in electromag-
netic elds, matrix mechanics and spin, approximate methods: stationary
states, approximative methods: time dependent problems.
Solid State Physics: Crystal structures, interacting forces, lattice vibrations,
electronic band structures, density of states, elementary excitations, trans-
port properties.
Electronics: Basics of semiconductor physics, ampliers, communication
principles.
Vibrations and Waves: Forced vibrations, coupled vibrations, stretched
strings, small oscillations.
Radiophysics/Telecommunication/Electronics/Electrical Engg.:
Boolean algebra, digital circuits and systems, circuit theory, ampliers, oscil-
lators, digital communication, digital signal processing, linear control theory,
electrical machines.
Computer Science:
Discrete Mathematics: Elementary counting techniques, Principles of inclusion-
3
exclusion, recurrence relations, generating functions, propositional logic.
Data Structures: Stack, queue, linked list, binary tree, heap, AVL tree, B-
tree.
Design and Analysis of Algorithms: Order notation, sorting, selection, search-
ing, hashing, string handling algorithms, graph algorithms, NP-completeness.
Programming Languages: Fundamental concepts - abstract data types, pro-
cedure call and parameter passing, C language.
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, concurrency control.
Formal Languages and Automata Theory: Finite automata and regular ex-
pression, context-free grammars, Turing machines, elements of undecidabil-
ity.
Principles of Compiler Construction: Lexical analyzer, symbol table, parser,
code optimization.
Database Systems: Relational model, relational algebra, relational calculus,
functional dependency, normalization (upto 3rd normal form).
Computer Networks: Layered network structures, network security, LAN
technology - Bus/tree, Ring, Star; data communications - data encoding,
ow control, error detection/correction.
4
Sample Questions
Note that all questions in the sample set are not of equal diculty.
They may not carry equal marks in the test.
GROUP A
ELEMENTS OF COMPUTING
A1. The strength of a mug (made of glass) is dened as follows.
There is a building having an innite number of oors. A mug is said
to possess strength h units if it does not break when it is dropped from
the h-th oor, but it breaks when it is dropped from the -th oor,
where h + 1. The strength of a mug is known to be nite.
If you are given only one mug, you can determine its strength by
dropping it successively from 1st, 2nd, . . ., oors until it breaks. Thus,
if the strength of the mug is h, then the number of times you need
to perform the experiment is h + 1, where an experiment consists of
dropping the mug from a oor and observing whether it breaks after
reaching the ground. Note that we may use the same mug for many
experiments until it breaks.
Now consider that instead of one, you are given two mugs of the same
strength. Design a scheme to determine the strength of these mugs
with minimum number of experiments. Also report the exact number
of experiments you have performed in your scheme.
A2. How many isomers are there for the organic compound C
6
H
14
? In
other words, how many distinct non-isomorphic unlabelled trees are
there with 6 vertices of degree 4, and 14 vertices of degree 1?
A3. In the following table, nd the entry in the square marked with *.
Justify your answer.
BD
1
CE
5
DF
21
EG
2
FH
8
GI
34
HJ
3
IK
13
*
5
A4. Consider the pseudo-code given below.
Input: Integers b and c.
1. a
0
max(b, c), a
1
min(b, c).
2. i 1.
3. Divide a
i1
by a
i
. Let q
i
be the quotient and r
i
the remainder.
4. If r
i
= 0 then go to Step 8.
5. a
i+1
a
i1
q
i
a
i
.
6. i i + 1.
7. Go to Step 3.
8. Print a
i
.
What is the output of the above algorithm? What is the mathematical
relation between the output a
i
and the two inputs b and c?
A5. Write the output of the following pseudo-code:
1. for (n = 15, downto 2, step -2)
2. if (n > 10)
3. then n n + 1 and print n;
4. else n n 1 and print n;
5. endfor
A6. Given an array of n integers, write a pseudo-code for reversing the
contents of the array without using another array. For example, for
the array
10 15 3 30 3
the output should be
3 30 3 15 10.
You may use one temporary variable.
A7. Consider the sequence a
n
= a
n1
a
n2
+n for n 2, with a
0
= 1 and
a
1
= 1. Is a
2006
odd? Justify your answer.
A8. Derive an expression for the maximum number of regions that can be
formed within a circle by drawing n chords.
6
A9. A function PrintRec is dened as follows:
PrintRec(A, B, C, n)
begin
if n > 0
begin
print B;
PrintRec(B, A, C, n 1);
print A;
PrintRec(C, A, B, n 2);
end
end
Find the output for the function call PrintRec(x, y, z, 3). Show the
intermediate steps of your derivation.
GROUP B
(i) MATHEMATICS
M1. (a) Let f : R R be a dierentiable function for which there does
not exist any x [0, 1] such that both f(x) = 0 and f

(x) = 0.
Show that f has only a nite number of zeros in [0,1].
[f

(x) denotes the derivative of f at x].

(b) Let f : R R be such that f

(x) exists and is continuous in

[0,1). Show that
lim
x0
1
x
2
_
x
0
(x 3y)f(y)dy =
f(0)
2
.
[x 0 denotes: x decreases to zero.]
M2. (a) Let f : [0, 1] [0, 1] be such that
f(x) = nx [nx];
1
n
< x
1
n 1
; n = 2, 3, 4, . . . ; x ,= 0
and f(0) = 0. Show that
_
1
0
f(x)dx exists and nd its value.
Note: [y] = Largest integer y; y R.
(b) Let f : [0, 1] (0, ) be continuous. Let
a
n
=
__
1
0
(f(x))
n
dx
_
1
n
; n = 1, 2, 3, . . . .
Find lim
n
a
n
.
7
M3. (a) Suppose f is a continuous real valued function on [0, 1]. Show
that
_
1
0
f(x)xdx =
1
2
f()
for some [0, 1].
(b) For every x 0, prove that

x + 1

x =
1
2
_
x +(x)
,
for a unique (x), 0 < (x) < 1. Prove that, in fact
(i)
1
4
(x)
1
2
,
(ii) lim
x0
(x) =
1
4
and lim
x
(x) =
1
2
.
M4. (a) Show that f(x) = e
|x|
x
5
x 2 has at least two real roots,
where e is the base of natural logarithms.
(b) Let

a
n
be a convergent series such that a
n
0 for all n. Show
that

a
n
/n
p
converges for every p >
1
2
.
M5. (a) Let G be the set of all non-singular 2 2 matrices
_
a b
c d
_
where the elements a, b, c, d belong to the eld of order 3. Using
matrix multiplication as the operation in G what is the order of
group G? Is G abelian? Justify your answers.
(b) Prove that Aut(Q, +) Z
2
, where Z
2
is the group consisting of
only two elements; and Aut(Q, +) is the automorphism group of
(Q, +).
M6. Let R = (S, +, , 0, 1) be a commutative ring and n be a positive integer
such that n = 2
k
for some positive integer k.
(a) Show that for every a S
n1

i=0
a
i
=
k1

i=0
_
1 +a
2
i
_
.
(b) Let m = w
n
2
+ 1 where w S, w ,= 0. Show that for 1 p < n,
n1

i=0
w
ip
0 mod m.
8
M7. (a) Show that there is a basis consisting of only symmetric and skew-
symmetric matrices for the vector space of all nn real matrices
over R.
(b) Does there exist a linear transformation from R
3
to R
3
such that
(0,1,1), (1,1,0), (1,2,1) are mapped to (1,0,0), (0,1,0), (0,1,1) re-
spectively? Justify your answer.
M8. (a) Let A be a square matrix such that A
2
= A. Show that all eigen
values of A are 0 or 1.
(b) Let A be a symmetric matrix whose eigenvalues are 0 or 1. Show
that A
2
= A.
(c) Suppose A is an n n matrix such that A
2
= A. Show that
r +s = n, where rank(A) = r and rank(I A) = s.
M9. Let k be a positive integer. Let G = (V, E) be the graph where V is the
set of all strings of 0s and 1s of length k, and E = (x, y) : x, y V ,
x and y dier 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.
M10. Let T be a tree with n vertices. For vertices u, v of T, dene d(u, v)
to be the number of edges in the path from u to v. Let W(T) be the
sum of d(u, v) over all
_
n
2
_
pairs of vertices u, v.
(a) Suppose the tree T is the path on n vertices. Show that
W(T) =
1
2
n1

k=1
(k
2
+k).
(b) Now, suppose T is the star graph on n vertices. Show that
W(T) = (n 1)
2
. (N.B. The edge set of the star graph is equal
to (u
1
, u
i
) : 2 i n.)
(c) Hence, for any tree T, show that
(n 1)
2
W(T)
1
2
n1

k=1
(k
2
+k).
9
M11. (a) Show that, given 2
n
+ 1 points with integer coordinates in R
n
,
there exists a pair of points among them such that all the co-
ordinates of the midpoint of the line segment joining them are
integers.
(b) Find the number of functions from the set 1, 2, 3, 4, 5 onto the
set 1, 2, 3.
M12. Consider the following LP:
P : minimize x
1
+x
3
subject to
x
1
+ 2x
2
5,
x
2
+ 2x
3
= 6,
x
1
, x
2
, x
3
0.
(a) Write down the dual D of P and nd the optimal solution of D
graphically.
(b) Using the optimal solution of D, nd the optimal solution of P.
M13. (a) 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.
(b) Let (n) denote the number of positive integers m relatively
prime to n; m < n. Let n = pq where p and q are prime numbers.
Then show that
(n) = (p 1)(q 1) = pq(1
1
q
)(1
1
p
)
M14. Consider the n n matrix A = ((a
ij
)) with a
ij
= 1 for i < j and
a
ij
= 0 for i j. Let
V = f(A) : f is a polynomial with real coecients.
Note that V is a vector space with usual operations. Find the dimen-
sion of V , when
(a) n = 3,
(b) n = 4.
Justify your answer.
10
(iv) STATISTICS
S1. (a) Let X
n

n1
be a sequence of random variables satisfying X
n+1
=
X
n
+Z
n
(addition is modulo 5), where Z
n

n1
is a sequence of
independent and identically distributed random variables with
common distribution
P(Z
n
= 0) = 1/2, P(Z
n
= 1) = P(Z
n
= +1) = 1/4.
Assume that X
1
is a constant belonging to 0, 1, 2, 3, 4. What
happens to the distribution of X
n
as n ?
(b) Let Y
n

n1
be a sequence of independent and identically dis-
tributed random variables with a common uniform distribution
on 1, 2, . . . , m. Dene a sequence of random variables X
n

n1
as X
n+1
= MAXX
n
, Y
n
where X
1
is a constant belonging to
1, 2, . . . , m. Show that X
n

n1
is a Markov chain and classify
its states.
S2. Let there be r red balls and b black balls in a box. One ball is removed
at random from the box. In the next stage (a + 1) balls of the colour
same as that of the removed ball were put into the box (a 1). This
process was repeated n times. Let X
n
denote the total number of red
balls at the n-th instant.
(a) Compute E(X
n
).
(b) Show that if (r +b) is much larger than a and n,
1
r
E(X
n
) =
_
1 +
na
r +b
_
+O
_
1
r +b
_
.
S3. Let x
1
, x
2
, . . . , x
n
be a random sample of size n from the gamma dis-
tribution with density function
f(x, ) =

k
(k)
e
x
x
k1
, 0 < x < ,
where > 0 is unknown and k > 0 is known. Find a minimum variance
unbiased estimator for
1

.
S4. Let 0 < p < 1 and b > 0. Toss a coin once where the probability
of occurrence of head is p. If head appears, then n independent and
11
identically distributed observations are generated from Uniform (0, b)
distribution. If the outcome is tail, then n independent and identically
distributed observations are generated from Uniform (2b, 3b) distribu-
tion. Suppose you are given these n observations X
1
, . . . , X
n
, but not
the outcome of the toss. Find the maximum likelihood estimator of b
based on X
1
, . . . , X
n
. What happens to the estimator as n goes to ?
S5. Let X
1
, X
2
, . . . be independent and identically distributed random
variables with common density function f. Dene the random variable
N as
N = n, if X
1
X
2
X
n1
< X
n
; for n = 2, 3, 4, . . . .
Find Prob(N = n). Find the mean and variance of N.
S6. (a) Let X and Y be two random variables such that
_
log X
log Y
_
N(, ).
Find a formula for (t, r) = E(X
t
Y
r
), where t and r are real
numbers, and E denotes the expectation.
(b) Consider the linear model y
n1
= A
np

p1
+
n1
and the usual
Gauss-Markov set up where E() = 0 and D() =
2
I
nn
, E
denotes the Expectation and D denotes the dispersion.
Assume that A has full rank. Show that V ar
_

LS
1
_
= (

T
B
1
)
1

2
where
A
T
A =
_

11

T
1p1

1p1
B
p1p1
_
and
LS
1
= the least square estimate of
1
, the rst component of
the vector , V ar denotes the variance and
T
denotes transpose.
S7. Let p
1
(x) and p
2
(x) denote the probability density functions for classes
1 and 2 respectively. Let P and (1 P) be the prior probabilities of
the classes 1 and 2, respectively. Consider
p
1
(x) =
_

_
x, x [0, 1);
2 x, x [1, 2];
0, otherwise;
12
and
p
2
(x) =
_

_
x 1, x [1, 2);
3 x, x [2, 3];
0, otherwise.
(a) Find the optimal Bayes risk for this classication problem.
(b) For which values of P, is the above risk
(I) minimized?
(II) maximized ?
S8. Let X = (X
1
, . . . , X
n
) and Y = (Y
1
, . . . , Y
n
) be two independent and
identically distributed multivariate random vectors with mean 0 and
covariance matrix
2
I
n
, where
2
> 0 and I
n
is the n n identity
matrix.
(a) Show that X
T
Y/(|X| |Y|) and V =

(X
2
i
+Y
2
i
) are indepen-
dent.
(Here, |(a
1
, . . . , a
n
)| =
_
a
2
1
+ +a
2
n
).
(b) Obtain the probability density of
_
n
i=1
X
2
i
/

n
i=1
Y
2
i
_
.
S9. Let X
1
, X
2
, . . . , X
n
be independent random variables. Let E(X
j
) = j
and V (X
j
) = j
3

2
, j = 1, 2, . . . , n, < < and
2
> 0. Here
E(X) denotes the expectation and V (X) denotes the variance of the
random variable X. It is assumed that and
2
are unknown.
(a) Find the best linear unbiased estimator for .
(b) Find the uniformly minimum variance unbiased estimate for
under the assumption that X
i
s are normally distributed; 1
i n.
S10. A hardware store wishes to order Christmas tree lights for sale during
Christmas season. On the basis of past experience, they feel that the
demand v for lights can be approximately described by the probability
density function f(v). On each light ordered and sold they make a
prot of a cents, and on each light ordered but not sold they sustain
a loss of b cents. Show that the number of lights they should order to
maximize the expected prot is given by x, which is the solution of
the equation:
_
x
0
f(v)dv =
a
a +b
.
13
S11. Let (X, Y ) follow the bivariate normal distribution. Let mean of X
= mean of Y = 0. Let variance of X = variance of Y = 1, and the
correlation coecient between X and Y be . Find the correlation
coecient between X
3
and Y
3
.
S12. Let X have probability density function f(x)( < x < ), and
we have two hypotheses H
0
: f(x) = (2)
1/2
exp(x
2
/2) against
H
1
: f(x) = (1/2) exp([x[). Derive the most powerful test at level
= 0.05.
S13. Let X
1
, X
2
, . . . , X
n
be independent and identically distributed obser-
vations with a common exponential distribution with mean . Show
that there is no uniformly most powerful test for testing H
0
: = 1
against H
A
: ,= 1 at a given level 0 < < 1 but there exists a
uniformly most powerful unbiased test, and derive that test.
S14. (a) An unbiased die is rolled once. Let the score be N 1, 2, . . . , 6.
The die is then rolled N times. Let X be the maximum of these
N scores. Find the probability of the event (X = 6).
(b) The unit interval (0,1) is divided into two sub-intervals by picking
a point at random from the interval. Let Y and Z be the lengths
of the longer and shorter sub-intervals, respectively. Find the
distribution of Z and show that
Y
Z
does not have a nite expec-
tation.
S15. Let X
1
, X
2
, X
3
be independent and identically distributed observations
with a common double exponential distribution with density
f(x, ) =
1
2
exp([x [), < x < , < < .
Suppose that the observations are all distinct.
(a) Find the maximum likelihood estimator of . Give a complete
argument for your answer.
(b) Suppose it is known that 10 10. Find the maximum
likelihood estimator of . Justify your answer.
S16. Consider the following linear model
y
ij
=
i
+
j
+e
ij
, i = 1, 2; j = 1, 2, 3;
14
(a) What is the rank of the error-space? Justify your answer.
(b) Write down any linear function of observations that belongs to
(i) estimation space, (ii) error space.
(c) Write down a parametric function that is not estimable. Justify
your answer.
S17. Let A = HHH, HHT, HTH, HTT, THH, THT, TTH, TTT be the
space obtained by tossing a coin three times. Let f : A (0, ) and
x
1
A. For any x
i
A, x
i+1
is found in the following way.
Toss a fair coin three times and let the outcome be z.
If f(z) f(x
i
) then x
i+1
= z, otherwise x
i+1
= x
i
.
What can you say about lim
x0
f(x
i
)? Justify your answer.
S18. Let there be two classes C
1
and C
2
. Let the density function for class
C
i
be p
i
for i = 1, 2 where p
i
(x) = ie
ix
; x > 0, i = 1, 2. Let the prior
probability for C
1
be 0.4 and the prior probability for C
2
be 0.6. Find
the decision rule for classication of an observation, which provides
the minimum probability of misclassication and nd its value for
that decision rule.
(iii) PHYSICS
P1. (a) Two particles A and B of equal mass m are attached with two
identical massless springs of stiness constant k in a manner
shown in the gure below. When set in longitudinal vibration,
nd the frequencies and the ratio of the amplitudes, in the normal
modes, of the two particles.
15
A
B
(b) A uniform string xed at both ends is struck at its centre so as
to obtain an initial velocity which varies from zero at the ends
to v
0
at the centre. Find the equation of motion of the resulting
vibration.
(c) Show that the zero temperature spin susceptibility of a non-
interacting electron gas is
=
B
g(E
F
)
where
B
= Bohr magneton, g(E
F
) = density of states per unit
energy at the Fermi energy E
F
.
P2. (a) In the electron spin-orbit interaction the two possible values of j
are l +
1
2
and l
1
2
. Show that the expectation values of S
Z
in the
states j = l +
1
2
and j = l
1
2
are +
m
j

2l+1
and
m
j

2l+1
respectively.
[All the symbols have their usual meanings.]
(b) A particle in the innite square well has the initial wave function
(x, 0) = Asin
3
x
a
, (0 x a)
(i) Determine A.
(ii) Find (x, t).
(iii) Calculate < x > as a function of time.
(c) Consider the operator function
(a, a
+
) = (1 e

)e
a
+
a
,
where a, a
+
are the annihilation and creation operators of the
eld respectively. Prove that is a density operator.
16
P3. A horse-shoe magnet is formed out of a bar of wrought iron of 50 cm
length having cross section 6.28 cm
2
. An exciting coil of 500 turns is
placed on each limb and connected in series. Find the exciting current
necessary for the magnet to lift a load of 19.6 kg (see the gure given
below) assuming that the load has negligible reluctance and makes
close contact with the magnet. Relative permeability of iron is 700.
P4. (a) Consider a conducting electron gas at the absolute zero temper-
ature in a weak magnetic eld B. The concentrations of spin up
and spin down electrons may be parameterised respectively as
N
+
= (1/2)N(1 +x), N

= (1/2)N(1 x)
where N is the total number of electrons.
Evaluate the factor x and calculate the total energy of gas.
(b) Suppose that there are N spinless particles satisfying Bose-Einstein
statistics. The density of available states between E and E +dE
is g(E), where
g(E) =
_
0, E < 0;
N
0
E
0
, E > 0,
and N
0
is the number of particles at energy E
0
.
(i) Find the chemical potential as a function of N, E
0
, N
0
and .
(ii) Can this system have Bose Einstein condensation? Justify
your answer.
17
P5. (a) Three particles A, B and C of equal mass m are placed on a
smooth horizontal plane. A is joined to B and C by light threads
AB and AC respectively and BAC = 60
0
. An impulse I is
applied to A in the direction BA. Find the initial velocities (im-
mediately after the application of I) of the particles and show
that A begins to move in a direction making an angle tan
1

3
7
with BA.
(b) A particle on a frictionless horizontal plane at a latitude is
given an initial speed u in the northern direction. Prove that it
describes a circle of radius
u
2sin
with a period T =

sin
where
is the angular velocity of the earth.
P6. Two electrons are conned in a one dimensional box of length a. A
clever experimentalist has made arrangements such that both the elec-
trons are in the same spin state. Ignore the Coulomb interaction be-
tween the electrons.
(a) Write down the ground state wave function of the two-electron
system.
(b) What is the probability that both the electrons are found on the
same half of the box?
(c) Will the nature of construction of the wave function in (a) hold if
Coulomb interaction is included? Give reasons for your answer.
(d) In the above problem, consider two charged -mesons instead
of two electrons. Write down the ground state wave function
ignoring the Coulomb interactions.
P7. (a) Consider an eigenstate of a two-particle system, in one dimension,
represented by the wave function
(x
1
, x
2
) = e
iP(x
1
+x
2
)/(2)
e
(Mk/2)
1
2 (x
1
x
2
)
2
/(2)
.
Here x
1
and x
2
are the positions of the two particles of equal mass
(M) moving in one dimension and interacting with a harmonic
oscillator force F = k(x
1
x
2
).
(i) Calculate the total energy associated with the relative mo-
tion.
(ii) Also calculate the mean absolute value of the relative mo-
mentum.
18
(b) A particle of mass m
1
MeV/c
2
and kinetic energy k
1
MeV collides
with a stationary particle of mass m
2
MeV/c
2
. After the collision,
the two particles stick together. Calculate
(i) the initial momentum of the two-particle system, and
(ii) the nal velocity of the two-particle system.
P8. (a) A monatomic classical gas (made up of N atoms, each having
mass m) is contained in a cylinder with cross sectional area A and
height h. The system is subject to a linear potential U(z) = bz,
where z is the vertical coordinate. Assume that the temperature
T is uniform in the cylinder. Find the free energy of this system.
(b) Consider a sequence of 2N ions of alternating charges q arranged
on a line with a repulsive potential
A
R
n
between nearest neigh-
bours in addition to the usual Coulomb potential. Find the equi-
librium separation R
0
and the equilibrium energy. Also evalu-
ate the nearest neighbour distance when the potential energy is
zero.(Neglect the surface eect).
P9. (a) Consider an electromagnetic wave in free space of the form,

E(x, y, z, t) = (E
0
x
(x, y)

i +E
0
y
(x, y)

j)e
i(kzt)
,

B(x, y, z, t) = (B
0
x
(x, y)

i +B
0
y
(x, y)

j)e
i(kzt)
.
Here

E
0
and

B
0
are in the xy plane.
Show that

E
0
and

B
0
satisfy the time independent Maxwells
equations.
(b) Two point charges of magnitude e are located at the end points
of a line of length 2l in the xy plane with its midpoint passing
through the origin. The line is rotating about the z-axis in the
anti-clockwise direction with a constant angular velocity .
Calculate the following:
(i) electric dipole moment of the system.
(ii) magnetic dipole moment of the system.
(c) A parallel plate capacitor (having perfectly conducting plates)
with plate separation d is lled with layers of two dierent mate-
rials. The rst layer has dielectric constant
1
and conductivity

1
; the second layer has dielectric constant
2
and conductivity

2
. Their thicknesses are d
1
and d
2
, respectively. A potential
19
dierence of V is applied across the capacitor. Neglecting the
edge eect,
(i) calculate the electric eld in each of the two dielectric media.
(ii) what is the current owing through the capacitor?
(iii) what is the total surface charge density on the interface be-
tween the two layers?
P10. (a) Suppose a planet is moving in a circular orbit of radius R. It is
stopped suddenly in its orbit. Show that it would fall onto the
sun in a time which is

2
8
times of its period.
(b) A block of mass M is rigidly connected to a massless circular
track of radius a xed in a vertical plane on a horizontal table
as shown in the gure. A particle of mass m is conned to move
without friction on the circular track (in the vertical plane).
a
(i) Set up the Lagrangian using x and as the coordinates.
(ii) Find the equations of motion.
(iii) Solve the equation of motion for ( for small ).
P11. For an intrinsic semiconductor with a gap width of 1 eV, calculate the
position of Fermi level at T = 0
0
K and T = 300
0
K, if m
h
= m
e
, where
m
e
and m
h
are eective masses of an electron and a hole respectively.
Also calculate the density of free electrons and holes at T = 300
0
K
and T = 600
0
K, given that log
10
e = 0.40,
_
2

m
e
m
h
kT
h
2
_3
2
= 0.5
10
19
/cc. If the above semiconductor is now doped with a group V
element with a doping concentration of 10
14
/cc, then compute the
electron and hole densities of the doped semiconductor specimen.
P12. (a) A negative feedback amplier has a voltage gain of 100. Varia-
tions of the voltage gain up to 2% can be tolerated for some
specic application. If the open-loop gain variations of 10% are
20
expected owing to production spreads in device characteristics,
determine the minimum value of the feedback ratio and also
the open loop gain to satisfy the above specication.
(b) Calculate the output voltage V
0
for the following network:
5V
10K 20K
10K
20K
5V
20K
5V
+
-
V
V
V 2
1
o
+
-
-
-
-
+
+
+
P13. (a) Consider the following circuit for deriving a +5 volt power supply
to a resistive load R
L
from an input d-c voltage source whose
voltage may vary from 8V to 11V. The load R
L
may draw a
maximum power of 250 mW. The Zener diode has a breakdown
voltage of 5 volts.
DC
voltage
source
-
+
R
Zener
diode
R
L
5 V
+
-
8 - 11 V
Compute the maximum value of the resistance R and also the
power dissipation requirements for R and the Zener diode. As-
sume that the minimum breakdown current of the Zener diode is
negligible compared to the load current.
21
(b) Consider the following circuit. Calculate the potential dierence
between the points F and C, as shown by the ideal voltmeter.
10
2
2
4
2
2
4
5 V
+ -
A
E F
D
C B

1
(iv) RADIOPHYSICS/TELECOMMUNICATIONS/ELECTRONICS/
ELECTRICAL ENGINEERING
R1. Design a sequential machine that produces an output 1 whenever a
substring of 5 consecutive symbols in the input starts with two 1s
and contains exactly three 1s. If a substring of 5 symbols starts with
two 1s, the analysis of the next substring does not begin until the
processing of the current substring is complete. Realize this circuit
with the minimum number of NAND gates and ip ops.
R2. Consider the following circuit, where all the resistances are in ohms.
Calculate the potential dierence between A and B. Also compute the
current i drawn from the battery.
22
12V
8
10
8
8 8
4 4
i
6 6
4
-
A B
4
4
R3. Draw the state table for the synchronous sequential circuit shown in
the gure below.
R4. Consider the following circuit of an ideal OP-AMP and an RC two-
port network. Assume that the RC two-port network is represented
in terms of its y parameters, i.e., y
11
=
I
1
V
1
[
V
2
=0
, y
12
=
I
1
V
2
[
V
1
=0
,
y
21
=
I
2
V
1
[
V
2
=0
, and y
22
=
I
2
V
2
[
V
1
=0
. Show that the voltage gain of the
above circuit is given by
V
o
V
s
=
y
21
(1 +k) +ky
22
y
22
,
where k =
R

R
.
23
V
S
RC
R
R
V
1
V
2
V
0
I
1
I
2
+
+
+
- -
-
R5. Consider a voltage amplier circuit shown in the gure below, where
R
i
and R
0
represent the input and output impedances respectively,
C
0
is the total parasitic capacitance across the output port, is the
amplier gain and the output is terminated by a load resistance R
L
.
(a) Calculate the current, voltage and power gain in decibels (dB) of
the amplier, when
R
i
= 1M, R
L
= 600, R
o
= 100M, C
o
= 10pf, = 10.
(b) Calculate the 3-dB cuto frequency of the amplier when
R
i
= 5K, R
L
= 1K, R
o
= 100, C
o
= 10pf, = 2.
R6. A 50 HP (37.3 KW), 460 V DC shunt motor running freely takes a
current of 4 A and runs at a speed of 660 rpm. The resistance of the
armature circuit (including brushes) is 0.3 ohm and that of the shunt
eld circuit is 270 ohm.
(a) Determine (i) the total current, and (ii) the speed of the motor
when it is running at full load.
(b) Determine the armature current at which the eciency is maxi-
mum (ignore the eect of armature reaction).
24
R7. (a) Three 100 ohm, non-inductive resistances are connected in (i)
Star and (ii) Delta congurations across 400 V, 50 Hz, 3-phase
main. Calculate the power taken from the supply system in each
case.
(b) In the event of one of the three resistances getting open circuited,
what variation would be in the value of the total power taken in
each of the two congurations?
R8. Consider the following circuit with an OP-AMP.
R = 10 K
2
R = 100 K
1
V
in
V
out
The plot of output voltage V
out
vs. input voltage V
in
for the given
circuit is as follows.
V
in
V
out
V
A
V
B
V
c
V
d
Let V
A
= 10V and V
B
= 10V . Assume that V
in
< V
c
, and is
gradually increasing. The output voltage V
out
= V
A
until V
in
= V
d
and
then falls to V
B
. The output remains at V
B
for V
in
> V
d
. Similarly, if
V
in
is initially > V
d
and gradually reduced, V
out
remains at V
B
until
V
in
= V
c
, and then rises to V
A
for all values V
in
< V
c
.
25
(a) Explain why the circuit behaves in this fashion, and
(b) calculate the values of V
c
and V
d
.
R9. Assume that an analog voice signal which occupies a band from 300
Hz to 3400 Hz, is to be transmitted over a Pulse Code Modulation
(PCM) system. The signal is sampled at a rate of 8000 samples/sec.
Each sample value is represented by 7 information bits plus 1 parity
bit. Finally, the digital signal is passed through a raised cosine roll-o
lter with the roll-o factor of 0.25. Determine
(a) whether the analog signal can be exactly recovered from the dig-
ital signal;
(b) the bit duration and the bit rate of the PCM signal before lter-
ing;
(c) the bandwidth of the digital signal before and after ltering;
(d) the signal to noise ratio at the receiver end (assume that the
probability of bit error in the recovered PCM signal is zero).
R10. A logic circuit is to be designed having four inputs x
1
, x
0
, y
1
and y
0
and the three outputs z
1
, z
2
and z
3
. The pair of bits x
1
x
0
and y
1
y
0
represent two binary numbers X and Y with x
1
and y
1
as the most
signicant bits. z
1
is 1 if X is larger than Y and z
2
z
3
represent the
dierence between the two numbers X and Y . Find the minimum sum
of product expressions for z
1
, z
2
and z
3
.
R11. A message bbccfe needs to be encoded using arithmetic coding. The
probabilities of message symbols are shown in the following table.
symbol a b c d e f
Probability 0.05 0.2 0.1 0.05 0.3 0.2 0.1
Using the symbol probabilities shown in the above table, nd
(a) a fractional value that is to be transmitted after encoding the
message bbccfe,
(b) the exact decoding scheme of the message from the fractional
value estimated at the encoding stage, and
(c) the number of bits required to represent the encoded message
after arithmetic coding.
26
R12. Consider two identical parallel plate air capacitors in series. The com-
bination is maintained at the constant potential dierence of 35 volts.
Now a dielectric sheet of dielectric constant 4 and thickness equal to
0.8 of the air gap is inserted into one of the capacitors, so that it spans
the whole area of the plates of the capacitors. Calculate the voltage
across this capacitor and the ratio of electrostatic energies stored in
the two capacitors.
R13. Two linear, time-invariant (LTI) discrete-time systems with frequency
responses as indicated below, are cascaded to form another LTI system.
H
1
(e
j
) =
_
1 if[[ < /2,
0 otherwise.
H
2
(e
j
) =
_
j if0 < < ,
j if < < 0.
(a) Determine the overall frequency response.
(b) A continuous time signal x(t) bandlimited to 1kHz. has a Fourier
Transform as follows:
X(j) =
_
1 /21000 if[[ < 21000,
0 otherwise.
It is sampled at a rate of 2kHz. to obtain a discrete-time signal
x[n]. This passes through the cascaded system mentioned ear-
lier to produce a discrete-time signal y[n]. Draw [X(e
j
)[ and
[Y (e
j
)[.
(c) Is it possible to recover x[n] from y[n]? Explain.
R14. Determine the stability of the following closed loop system. S repre-
sents Laplace operator.
27
(v) COMPUTER SCIENCE
C1. (a) Write the smallest real number greater than 6.25 that can be
represented in the IEEE-754 single precision format (32-bit word
with 1 sign bit and 8-bit exponent).
(b) Convert the sign-magnitude number 10011011 into a 16-bit 2s
complement binary number.
(c) The CPU of a machine is requesting the following sequence of
memory accesses given as word addresses: 1, 4, 8, 5, 20, 17,
19, 56. Assuming a direct-mapped cache with 8 one-word blocks,
that is initially empty, trace the content of the cache for the above
sequence.
C2. Consider a collection of n binary strings S
1
, . . . , S
n
. Each S
i
is of
length l
i
bits where 1 l
i
k.
(a) Write a function prex(S,T) in C programming language that
takes two binary strings S, T and returns 1 if S is a prex of T,
else it returns 0. For example, prex (001,00101) returns 1 but
prex(010,00101) returns 0.
(b) Suppose we want to report all the pairs (i, j) for which S
i
is a
prex of S
j
, (1 i ,= j n). How many times do we need to call
the prex function described above?
(c) Present an O(nk) time algorithm to report all the (i, j)s as men-
tioned in (b). (Hint: Use a binary tree with each edge marked
as 0 or 1; a path from the root to a node in the tree represents a
binary string.)
28
C3. (a) Write a computer program in the C language that takes an array
A of 2n distinct oating point numbers, and prints the maximum
and the minimum values of the array A, along with their indices.
(Full credit will be given only if your program does not make more
than (3n 2) oating point comparisons.)
(b) Briey argue that your program indeed computes the maximum
and the minimum values correctly.
C4. Let a
1
= 1, a
2
= 2, and a
n
= a
n1
+a
n2
+ 1 for n > 2.
(a) Express 63 as a sum of distinct a
i
s.
(b) Write an algorithm to express any positive integer k as a sum of
at most log
2
k| many distinct a
i
s.
(c) Prove the correctness of your algorithm.
C5. Let S = x
1
, x
2
, . . . x
n
be a set of n integers. A pair (x
i
, x
j
) is said to
be the closest pair if [x
i
x
j
[ [x

i
x

j
[, for all possible pairs (x

i
, x

j
),
i

, j

= 1, 2, . . . , n, i

,= j

.
(a) Describe a method for nding the closest pair among the set of
integers in S using O(nlog
2
n) comparisons.
(b) Now suggest an appropriate data structure for storing the ele-
ments in S such that if a new element is inserted to the set S or
an already existing element is deleted from the set S, the current
closest pair can be reported in O(log
2
n) time.
(c) Briey explain the method of computing the current closest pair,
and necessary modication of the data structure after each up-
date. Justify the time complexity.
C6. Let A be an nn matrix such that for every 22 sub-matrix
_
a b
c d
_
of A, if a < b then c d. Note that for every pair of rows i and
j, if a
ik
and a
jl
are the largest elements in i-th and j -th rows of A,
respectively, then k l (as illustrated in the 5 5 matrix below).
_

_
3 4 2 1 1
7 8 5 6 4
2 3 6 6 5
5 6 9 10 7
4 5 5 6 8
_

_
29
(a) Write an algorithm for nding the maximum element in each row
of the matrix with time complexity O(nlog n).
(b) Establish its correctness, and justify the time complexity of the
proposed algorithm.
C7. Consider a le consisting of 100 blocks. Assume that each disk I/O
operation accesses a complete block of the disk at a time. How many
disk I/O operations are involved with contiguous and linked allocation
strategies, if one block is
(a) added at the beginning?
(b) added at the middle?
(c) removed from the beginning?
(d) removed from the middle?
C8. (a) Consider the context-free grammar G = (S, A, a, b, S, P),
where
P = S AS,
S b,
A SA,
A a
Show that G is left-recursive. Write an equivalent grammar G

free of left-recursion.
(b) Consider the grammar G = (S, T, a, , (, ), +, S, P),
where
P = S a[[(T),
T T +S[S
Find the parse tree for the sentence:
(((a +a) + + (a)) +a)
C9. (a) Five batch jobs P
1
, . . . , P
5
arrive almost at the same time. They
have estimated run times of 10, 6, 2, 4 and 8 ms. Their priorities
are 3, 5, 2, 1 and 4 respectively, where 1 indicates the highest
priority and 5 indicates the lowest. Determine the average turn-
around and waiting time for the following scheduling algorithms:
(i) Round robin with time quantum of 5 ms,
30
(ii) Priority scheduling.
(b) The access time of a cache memory is 100 ns and that of main
memory is 1000 ns. It is estimated that 80% of the memory
requests are for read and the remaining 20% are for write. The
hit ratio for read access is 0:9. A write through procedure is used.
(i) What is the average access time of the system considering
only memory read cycles?
(ii) What is the average access time of the system considering
both read and write requests?
C10. (a) A program P consisting of 1000 instructions is run on a machine
at 1 GHz clock frequency. The fraction of oating point (FP)
instructions is 25%. The average number of clock-cycles per in-
struction (CPI) for FP operations is 4.0, and that for all other
instructions is 1.0.
(i) Calculate the average CPI for the overall program P.
(ii) Compute the execution time needed by P in seconds.
(b) 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 is
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.
(i) Express the maximum eciency of this network when only a
single station is active in the network.
(ii) Find an upper bound on the token rotation time when all
stations are active.
(iii) Calculate the maximum throughput rate that one host can
achieve in the network.
C11. Consider a graph G (called an interval graph) whose nodes correspond
to a set of intervals on the real line. The i-th interval is denoted by
[
i
,
i
], where 0
i
<
i
. An edge between two nodes (i, j) implies
that the corresponding intervals [
i
,
i
] and [
j
,
j
]] overlap.
(a) Consider the set of intervals [3, 7], [2, 4], [2, 3], [1, 5], [1, 2], [6, 7],
[10, 16], [11, 12]. Draw the corresponding interval graph and iden-
tify the largest subgraph where all the nodes are connected to
each other.
31
(b) Write an algorithm which takes the interval graph G as input
and nds the largest subgraph of G in which all the nodes are
connected to each other. What is the time complexity of your
algorithm?
(c) Given a list of intervals, write an algorithm to list all the con-
nected components in the corresponding interval graph. What is
the time complexity of your algorithm?
C12. (a) A functional dependency is called a partial dependency if
there is a proper subset of such that . Show that every
partial dependency is a transitive dependency.
(b) Let R = (A, B, C, D, E) be a schema with the set F = A
BC, CD E, B D, E A of functional dependencies.
Suppose R is decomposed into two schema R
1
= (A, B, C) and
R2 = (A, D, E)
(i) Is this decomposition loss-less? Justify.
(ii) Is this decomposition dependency preserving? Justify.
(c) Consider the relations r1(A, B, C), r2(C, D, E) and r3(E, F). As-
sume that the set of all attributes constitutes the primary keys
of these relations, rather than the individual ones. Let V (C, r1)
be 500, V (C, r2) be 1000, V (E, r2) be 50, and V (E, r3) be 150,
where V (X, r) denotes the number of distinct values that appear
in relation r for attribute X . If r
1
has 1000 tuples, r
2
has 1500
tuples, and r
3
has 750 tuples, then give the ordering of the nat-
ural join r
1
r
2
r
3
for its ecient computation. Justify your
answer.
C13. (a) (i) Write a Context Free Grammar (CFG) for structure deni-
tions in C. Assume that the only allowable types are char,
int, and oat (you need not handle pointers, arrays, struc-
ture, elds, etc.).
(ii) Assume that chars are stored using 1 byte each; ints and
oats are stored using 4 bytes each and are aligned at 4 byte
boundaries. Add semantic rules to your grammar to calculate
the number of bytes required to store the structure dened
by your grammar.
(b) (i) Compute the canonical collection of sets of LR(1) items (i.e.
canonical LR items) for the following grammar: S aXcd,
32
S aY ce, X b, Y b. Is the grammar LR(1)? Briey
justify.
(ii) Give an example of a grammar that is unambiguous but not
LR(2). Briey justify/explain your example.
C14. An operating system allocates memory in units of 1 KB pages. The
address space of a process can be up to 64 MB in size; however, at any
point of time, a process can be allocated at most 16 MB of physical
memory. In addition the kernel uses 65 KB of physical memory to
store page table entries of the current process. The OS also uses a
translation-lookaside buer (TLB) to cache page table entries. You
are also given the following information:
size of a page table entry is 4 bytes,
TLB hit ratio is 90%,
time for a TLB lookup is negligible,
time for a memory read is 100 nanoseconds,
time to a read a page from the swapping device into physical
memory is 10 milliseconds.
Calculate the eective memory access time for a process whose ad-
dress space is 20 MB? Assume that memory accesses are random and
distributed uniformly over the entire address space.
C15. (a) What are the conditions which must be satised by a solution to
the critical section problem?
(b) Consider the following solution to the critical section problem for
two processes. The two processes, P
0
and P
1
, share the following
variables:
var flag : array [0..1] of Boolean;
(* initially false *)
turn : 0..1;
The program below is for process P
i
(i = 0 or 1) with process P
j
(j = 1 or 0) being the other one.
repeat
flag[i] <- true;
while (flag[j])
do if (turn = j)
33
then begin
flag[i] <- false;
while (turn = j) do skip;
end;
...
CRITICAL SECTION
...
turn <- j;
flag[i] <- false;
...
REMAINDER SECTION
...
until false;
Does this solution satisfy the required conditions?
C16. (a) Construct an AVL tree of height 5 with minimum number of
nodes.
(b) Consider a B-tree of order 3.
(i) Trace the insertion of the keys a, g, f, b, k, d, h, m, into an
initially empty tree, in lexicographic order.
(ii) Sketch the B-tree upon deletion of keys h, d.
34