2022 Admission to PhD in Computer Science (CS) for

awardees of CSIR/UGC Junior Research Fellowships

(Channel 2)
Test Date: June 06, 2022
Test Code: CS2

The CS2 question paper has TWO parts: PART A (20 marks)
and PART B (40 marks).

Sample Questions (PART A and PART B)

Note that all questions in the sample set are not at the same level
of difficulty, and may not carry equal marks in an examination.

PART A

1. Let us consider the following 2-person game: the players alternately

choose a number. The first player starts with a number between 1 and
10, and the players then pick up a number within the next ten of the
number that his opponent has chosen earlier. The player who is able
to select the number 100 first, wins the game. Can the first player
pick up a number between 1 and 10 such that whatever may be the
strategy of his opponent, the first player will be able to reach 100 first?

2. Five men A, B, C, D, E are wearing caps of black or white color with-

out each knowing the color of his cap. It is known that a man wearing
a white cap will always speak the truth while a man wearing a black
cap always lies. They make the following statements.
A: I see three white and one black cap.
B: I see four black caps.
C: I see one white and three black caps.
D: I see four white caps.

Find the color of each person’s cap.

1
3. Consider the pseudo-code given below.
Input: Integers b and c.
1. a0 ← max(b, c), a1 ← min(b, c).
2. i ← 1.
3. Divide ai−1 by ai . Let qi be the quotient and ri be the remainder.
4. If ri = 0, then go to Step 8.
5. ai+1 ← ai−1 − qi ∗ ai .
6. i ← i + 1.
7. Go to Step 3.
8. Print ai .
What is the output of the above algorithm when b = 28 and c = 20?
What is the mathematical relation between the output ai and the two
inputs b and c?

4. Write pseudo-code to print a diamond formed using the character * as

shown in the figure below. Let H and W denote the number of rows,
and the number of columns occupied by the upper half and the left
half of the diamond, respectively. In the example shown below, H = 5
and W = 9. Your code should take H and W as input parameters.
You may assume that W − 1 is an integral multiple of H − 1.
W columns

*
*****
H rows *********
*************
*****************
*************
*********
*****
*

5. Let A be an array of n integers containing the numbers {1, 2, . . . , n} in

some arbitrary order. For integers i and j such that 1 ≤ i < j ≤ n, let
Reverse(A, i, j) be a procedure that reverses the subarray A[i], A[i +
1], . . . , A[j] of the array A while leaving the remaining elements of
the array unaffected. For example, if A = [3, 4, 1, 2, 5], then, after
Reverse(A, 2, 4), we will have A = [3, 2, 1, 4, 5].

2
 Precisely what will happen to the array A if the following piece of
code is executed? Justify your answer with an example enumerating
different steps.

for i := 1 to n − 1
while A[i] ̸= i do
Reverse(A, i, A[i]).

6. The integers 1, 2, 3, 4 and 5 are to be inserted into an empty stack

using the following sequence of push() operations:
push(1) push(2) push(3) push(4) push(5)
Assume that pop() removes an element from the stack and outputs the
same. Which of the following output sequences can be generated by
inserting suitable pop() operations into the above sequence of push()
operations? Justify your answer.
(a) 5 4 3 2 1
(b) 1 2 3 4 5
(c) 3 2 1 4 5
(d) 5 4 1 2 3.

7. Given a function f : A → A, an element x ∈ A is said to be a

fixed point of f if and only if f (x) = x. Let f : {1, 2, . . . , 100} →
{1, 2, . . . , 100} be a function. For all S ⊆ {1, 2, . . . , 100}, suppose a
procedure FIXED(S) can determine whether the function f has at least
one fixed point in S or not. Define a strategy to determine whether
the function f has at least two fixed points by executing the procedure
FIXED at most 15 times.

8. Give a strategy to sort four distinct integers a, b, c, d in increasing order

that minimizes the number of pairwise comparisons needed to sort any
permutation of a, b, c, d.

9. An n × n matrix is said to be tridiagonal if its entries aij are zero

except when |i − j| ≤ 1 for 1 ≤ i, j ≤ n. Note that only 3n − 2 entries
of a tridiagonal matrix are non-zero. Thus, an array L of size 3n − 2
is sufficient to store a tridiagonal matrix.
Given i, j, write pseudo-code to (a) store aij in L, and (b) get the
value of aij stored in L.

3
10. Given an array A = {a1 , a2 , . . . , an } of unsorted distinct integers, write
a program in pseudo-code for the following problem: given an integer
u, arrange the elements of the array A such that all the elements in
A which are less than or equal to u are at the beginning of the array,
and the elements which are greater than u are at the end of the array.
You may use at most 5 extra variables apart from the array A.

11. Let n be a positive integer. Consider the set

S = {−n, −n + 1, −n + 2, . . . , −1, 0, 1, 2, . . . , n − 1, n}.

Let f : S ×S → {−1, 1} be a function. If f (−a, −b) = −f (a, b) ∀a, b ∈

S, f is said to be odd. If f (−a, −b) = f (a, b) ∀a, b ∈ S, f is said to
be even.
(a) What is the total number of different functions from S × S to
{−1, 1}?
(b) How many of these are odd?
(c) How many of these are neither odd nor even?

12. How many functions f : {1, 2, . . . , n} → {1, 2, . . . , n} are there that

are monotone; that is, for i < j we have f (i) ≤ f (j)?

13. How many 0’s are there at the end of 50! ?

14. Let bq bq−1 . . . b1 b0 be the binary representation of an integer b, i.e.,

X
q
b= 2j bj , bj = 0 or 1, for j = 0, 1, . . . , q
j=0

Show that b is divisible by 3 if b0 − b1 + b2 − . . . (−1)q bq = 0.

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

16. Show that if S is any subset of {1, 2, . . . , 2n} such that |S| > n, then
S contains two numbers such that one of them divides the other.

4
17. Prove that every natural number n ≥ 1 has a multiple whose decimal
representation contains only 1s and 0s. (Hint: Consider the numbers
1, 11, 111, 1111, . . . and their remainders modulo n).

18. How many k-element subsets of {1, 2, . . . , n} exist that contain no two
consecutive numbers?

19. Let T be an equilateral triangle of unit area. Let P1 , . . . , P9 be 9 points

inside T . Show that, out of these 9 points, we can always find 3 points
such that the area of the triangle formed by these three points will be
at most 41 unit.

20. Let N denote the set of natural numbers. For each of the following
sets, state whether it is finite or infinite. Justify your answers.
(a) {f : N → {0, 1} | ∀n ∈ N, f (n) ≤ f (n + 1)}
(b) {f : N → {0, 1} | ∀n ∈ N, f (2n) ̸= f (2n + 1)}
(c) {f : N → {0, 1} | ∀n ∈ N, f (n) ̸= f (n + 1)}

21. Find the number of distinct positive integers that can be formed using
0, 1, 2 and 4, where each of these integers is used at most once.

22. Derive an expression for the maximum number of regions that can be
formed within a circle by drawing n chords.

23. Given A = {1, 2, 3, . . . , 70}, show that for any six elements a1 , a2 , a3 ,
a4 , a5 and a6 belonging to A, there exists one pair ai and aj for which
|ai − aj | ≤ 14 (i ̸= j).

24. Calculate how many integers in the set {1, 2, 3, . . . , 1000} are not di-
visible by 2, 5, or 11.

5
25. Consider all the permutations of the digits 1, 2, . . . , 9. Find the number
of permutations each of which satisfies all of the following:
• the sum of the digits lying between 1 and 2 (including 1 and 2)
is 12,
• the sum of the digits lying between 2 and 3 (including 2 and 3)
is 23,
• the sum of the digits lying between 3 and 4 (including 3 and 4)
is 34, and
• the sum of the digits lying between 4 and 5 (including 4 and 5)
is 45.

26. State, with justification, which of the following expressions f , g and

h, define valid real-valued functions over the set of positive rational
numbers. We denote a rational number by m/n, where m and n are
positive integers.
(a) f (m/n) = 2m − 2n .
(b) g(m/n) = log m − log n.
(c) h(m/n) = (m2 − n2 )/(mn).

27. There are n students in a class. The students have formed k commit-
tees. Each committee consists of more than half of the students. Show
that there is at least one student who is a member of more than half
of the committees.

28. Consider an m × n integer grid. A path from the lower left corner at
(0, 0) to the grid point (m, n) can use three kinds of steps, namely (i)
(p, q) → (p + 1, q) (horizontal), (ii) (p, q) → (p, q + 1) (vertical), or (iii)
(p, q) → (p + 1, q + 1) (diagonal). Derive an expression in terms of m
and n for Dm,n , the number of such distinct paths.

29. The numbers 1, 2, . . . , 10 are circularly arranged. Show that there are
always three adjacent numbers whose sum is at least 17, irrespective
of the arrangement.

30. Consider six distinct points in a plane. Let m and M denote respec-
tively the minimum and the √ maximum distance between any pair of
points. Show that M/m ≥ 3.

6
31. A group of 15 boys plucked a total of 100 apples. Prove that two of
those boys plucked the same number of apples.

32. Suppose X is a set such that for every function f : X → X, f is one-

to-one if and only if f is onto. Show that every one-to-one function
f : P (P (X)) → P (P (X)) is onto, where P (A) denotes the set of all
subsets of a set A.

P
33. Find the value of ij, where the summation is over all integers i and
j such that 1 ≤ i < j ≤ 10.

34. Let S = {x ∈ R : 1 ≤ |x| ≤ 100}. Find all subsets M of S such that

for all x, y in M , their product xy is also in M .

35. How many triplets of real numbers (x, y, z) are simultaneous solutions
of the equations x + y = 2 and xy − z 2 = 1?

7
 PART B

The questions in this PART appear in three groups: I. Computer Science,

II. Mathematics for Computer Science, and III. Mathematics.

I. Computer Science

C1. Let A be an array containing n distinct integers, and w be a positive

integer. Your task is to select the maximum number of elements of A
such that the sum of the selected elements is less than or equal to w.
Devise O(n) time algorithms (with justification) for this task for the
following two cases:
(a) the array A is sorted;
(b) the array A is unsorted.
hint: For case (b), you may consider a divide-and-conquer type
algorithm, and use the fact that the median of an array of n elements
can be found in O(n) time.

C2. Suppose a lockdown has been announced at your place. You plan to
spend the very first day of the lockdown by watching movies on a TV
with no recording facility. You have received a schedule of movies to
appear on all the channels on the said day. You do not like to switch
over from one movie to another, and your aim is to watch as many
complete movies as possible. Suppose there are n distinct movies for
which the corresponding start and end times are available across all
the channels. Write an efficient program (using pseudo-code) to find
the maximum number of complete movies that you can watch on the
day. Analyze the time complexity of your algorithm.

C3. Consider a hard disk whose storage space S is divided into a number
of logical sectors (segments) of equal length l. A batch of requests
for storing data into it is served in such a way that no piece of data
is fragmented to accommodate the same over more than one sectors
under the assumption that the length of each piece of data is less than
the sector size and a single sector can accommodate multiple pieces of
data.
Write an algorithm to store a given set of m successive storage requests
{s1 , s2 , ..., sm } using the minimum number of sectors, where si is the

8
 size
P of i-th data request, si < l, for each i and
i s i < S. For example, consider the set of data storage requests
{2kb, 5kb, 4kb, 7kb, 1kb, 3kb, 8kb} into a hard disk of sector length
10kb. The minimum number of sectors required for the storage is 3
and a possible distribution of the data pieces into 3 sectors are {2kb,
8kb}, {4kb, 1kb, 5kb} and {7kb, 3kb}.

C4. Consider the task of multiplying two integer matrices A and B, each
of size 500 × 500. Each matrix can have at most 500 non-zero entries.
Any row of A or B that contains at least one non-zero element, must
have no less than 50 non-zero elements.
(a) Propose a space-efficient data structure for this task.
(b) Based on your proposed data structure, design an efficient algo-
rithm to multiply A and B. The resulting matrix should be stored
separately.
(c) What is the maximum number of integer multiplications needed
to complete this task as per your implementation?

C5. Consider a set A containing n positive integers a0 , a1 , . . . , an−1 such

X
i−1


that ai > (j + 1)aj for i = 1, 2, . . . , n − 1. You are also given a
j=0
target positive integer T .
(a) Write an efficient algorithm to determine whether there is any
subset of A, such that the sum of the elements in this subset is
T.
(b) Analyse the worst case time complexity of your algorithm.

C6. Let S = {1, 2, . . . , n} and f : S → S. If R ⊆ S, define f (R) =

{f (x) | x ∈ R}.
(a) Suppose you are given the values of f (1), f (2), . . . , f (n), in order.
Propose a data structure for storing these values so that, for a
given x, the values of f (x) and f −1 (x) = {y | f (y) = x} can be
determined efficiently.
(b) Suppose that we call a set R ⊆ S “special” if f (R) = R. For
n = 3, give an example of a function f and subsets Ri ⊆ S such
that Ri is special, and |Ri | = i for i = 1, 2, 3.

9
 (c) Using your data structure from (a), design an efficient algorithm
to find a set R ⊆ S that is special (as defined in (b)). You will
get full credit only if your algorithm takes O(n) time in the worst
case.

C7. There are n students standing in a line. The students have to rearrange
themselves in ascending order of their roll numbers. This rearrange-
ment must be accomplished only by successive swapping of adjacent
students.
(a) Design an algorithm for this purpose that minimises the number
of swaps required.
(b) Derive an expression for the number of swaps needed by your
algorithm in the worst case.

C8. Let S = {x1 , x2 , . . . xn } be a set of n integers. A pair (xi , xj ) (where

i ̸= j) is said to be the closest pair if |xi − xj | ≤ |xi′ − xj ′ |, for all
possible pairs (xi′ , xj ′ ), i′ , j ′ = 1, 2, . . . , n, i′ ̸= j ′ .
(a) Describe a method for finding the closest pair among the set of
integers in S using O(n log2 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(log2 n) time.
(c) Briefly explain the method of computing the current closest pair,
and necessary modification of the data structure after each up-
date. Justify the time complexity.

C9. Let M be an (n × n) matrix where each element is a distinct positive

integer. Construct another matrix M ′ by permuting the rows and/or
permuting the columns, such that the elements of at least one row
appear in increasing order (while looking from left to right) and those
of at least one column appear in decreasing order (while looking from
top to bottom). Describe an O(n2 ) time algorithm for constructing
M ′ . Justify your analysis.

10
C10. Let A be an n × n matrix of integers whose element in the i-th row
and j-th column is denoted by aij . Further, we shall denote by µi the
maximum value that appears in the i-th row, i.e. µ(i) = max{aij : j ∈
{1, 2, . . . , n}}. Suppose that for any i, j such that i < j, if aik = µ(i)
and ajl = µ(j), 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
(a) Write an algorithm for finding the maximum element in each row
of the matrix with time complexity O(n log n).
(b) Establish its correctness, and justify the time complexity of the
proposed algorithm.

C11. Consider three parallel lines L1 , L2 and L3 . On each line Li , a set of

n points {pi1 , pi2 , . . . , pin } is placed.
The objective is to identify a triplet of indices (k, `, m) (if it exists)
such that a straight line can pass through p1k , p2ℓ and p3m on L1 , L2
and L3 respectively. [See Figure 1 for a demonstration.]

L1 L1
L2 L2

L3 L3

(a) (b)

Figure 1: Two instances for Question C11.

In Figure 1(a), there does not exist any triplet (k, `, m) such that a
straight line can pass through p1k , p2ℓ and p3m . In Figure 1(b), the
triplet (3, 3, 4) is a solution since a straight line passes through p13 , p23
and p34 .
Present an efficient algorithm for solving this problem. Justify its
correctness and worst case time complexity. It can be assumed that
the x, y-coordinates of the points are given as input.
[Full credit will be given if your algorithm is correct, and of worst case time
complexity O(n2 ).]

11
C12. A least expensive connection route among n houses needs to be de-
signed for a cable-TV network. Consider the following algorithm A
for finding a spanning tree.

Algorithm A
Input: G = (V, E)
Output: Set of edges M ⊆ E
Sort E in decreasing order of cost of edges;
i ← 0;
while i < |E| do
begin
Let temp = (u1 , u2 ) be the i-th edge E[i] in E;
Delete E[i], i.e., replace E[i] by φ;
if u1 is disconnected from u2 then
restore temp in list E as E[i];
i ← i + 1;
end
return the edges in E which are not φ;

(a) Prove that the algorithm A can be used to correctly find a least
cost connection route, given a set of n houses and information
about the cost of connecting any pair of houses.
(b) What is the worst case time complexity of A?
(c) If all the edges have distinct cost, how many solutions can there
be?

C13. You are given k sorted lists, each containing m integers in ascending
order. Assume that (i) the lists are stored as singly-linked lists with
one integer in each node, and (ii) the head pointers of these lists are
stored in an array.
(a) Write an efficient algorithm that merges these k sorted lists into
a single sorted list using Θ(k) additional storage.
(b) Next, write an efficient algorithm that merges these k sorted lists
into a single sorted list using Θ(1) additional storage.
(c) Analyse the time complexity of your algorithm for each of the
above two cases.

12
C14. Let A and B be two arrays, each containing n distinct integers. Each
of them is sorted in increasing order. Let C = A ∪ B. Design an
algorithm for computing the median of C as efficiently as you can.

C15. Let B be a rooted binary tree of n nodes. Two nodes of B are said
to be a sibling pair if they are the children of the same parent. For
example, given the binary tree in Figure 2 below, the sibling pairs are
(2, 3) and (6, 7). Design an O(n) time algorithm that prints all the
sibling pairs of B.

2 3

4 5

6 7

Figure 2: Rooted binary tree for Question C14.

C16. Let H1 and H2 be two complete binary trees that are heaps as well.
Assume H1 and H2 are max-heaps, each of size n. Design and analyze
an efficient algorithm to merge H1 and H2 to a new max-heap H of
size 2n.

C17. Let G = (V, E) be an undirected weighted graph with all edge weights
being positive. Design an efficient algorithm to find the maximum
spanning tree of G.

C18. The diameter of a tree T = (V, E) is given by max {δ(u, v)}, where
u,v∈V
δ(u, v) is the shortest path distance (i.e., the length of the shortest
path) between vertices u and v. So, the diameter is the largest of all
shortest path distances in the tree.
(a) Write pseudo-code for an efficient algorithm to compute the di-
ameter of a given tree T .
(b) Analyze the time complexity of your algorithm.
(c) What is its space complexity?

13
 (d) Clearly mention the data structure(s) used by your algorithm.
(e) A vertex c is called a center of a tree T if the distance from c to
its most distant vertex is the minimum among all vertices in V .
Write an algorithm to determine and report a center of the given
tree T .

C19. A connected, simple, undirected planar graph G(V, E) is given where

V denotes the set of vertices and E denotes the set of edges. In V ,
there is a designated source vertex s and a designated destination
vertex t. Let P (v) denote the shortest path (may contain repetition
of nodes/edges) from s to t that passes through v, and let l(v) denote
the path length (i.e., the number of edges) of P (v).
(a) Describe an O(|V |) time algorithm that determines the value of
τ where τ = max l(v). Justify your analysis.
∀v∈V
(b) Propose a data structure that supports your algorithm. For ex-
ample, in the graph shown in Figure 3, τ = 10, which corresponds
to P (6 : s → 2 → 3 → 4 → 7 → 6 → 7 → 4 → 14 → 13 → t.

Figure 3: The example graph of Question C19.

C20. A vertex cover of a graph G = (V, E) is a set of vertices V ′ ⊆ V such

that for any edge (u, v) ∈ E, either u or v (or both) is in V ′ . Write an
efficient algorithm to find the minimum vertex cover of a given tree T .
Establish its correctness. Analyse its time complexity.

C21. (a) Assume you have a chocolate bar containing a number of small
identical squares arranged in a rectangular pattern. Our job is
to split the bar up until each piece is one of the small squares

14
 by breaking along the lines between the squares. We obviously
want to do it with the minimum number of breakings. How many
breakings will it take?
(b) Consider that the chocolate bar has n breaking lines along the
length and m breaking lines along the breadth. Write the pseu-
docode of an algorithm that will take n, m as inputs and print
the line numbers of the lines along which your strategy does the
breaking of the chocolate.

C22. Let a1 = 1, a2 = 2, and an = an−1 + an−2 + 1 for n > 2.

(a) Express 63 as a sum of distinct ai ’s.
(b) Write an algorithm to express any positive integer k as a sum of
at most ⌈log2 k⌉ many distinct ai ’s.
(c) Prove the correctness of your algorithm.

C23. Consider a hypothetical gate G(A, B, C) for which the Karnaugh map
is given in Figure 4.

Figure 4: Karnaugh map for the hypothetical gate G in Question C23.

(a) Implement the NOT, 2-input AND, and 2-input OR operations

using minimum number of G gates. Assume that the logical value
1 is available as an input.
(b) Consider the switching function f (w, x, y, z) defined as follows
X
f (w, x, y, z) = (0, 1, 2, 4, 7, 8, 9, 10, 12, 15).

Realize f by means of minimum number of G gates.

C24. Suppose instead of a decoder with n input bits (n is even) to access

a memory of size 2n , one uses two decoders of input sizes k bits and
(n − k) bits. Explain how these two decoders can be used to access the
memory of size 2n .

15
 Determine the value of k that achieves minimum address decoding
time. Justify your answer. Assume that the time complexity of the
decoder is measured by the number of output lines of that decoder.
Explain with a diagram how to solve the aforementioned decoding
problem if n = 17.

C25. Let C denote a logic block that is capable of comparing two 4-bit 2’s
complement numbers A (a3 , a2 , a1 , a0 ) and B (b3 , b2 , b1 , b0 ), where
ai , bi ∈ {0, 1} for i = 0, 1, 2, 3. The circuit C has eight input lines
a3 , a2 , a1 , a0 , b3 , b2 , b1 , b0 , and three output lines E, L, G (Equal: E;
Less than: L; Greater than: G). For example, if A > B, then the
outputs should be E = 0, L = 0, and G = 1.
Write the Boolean equations for the three outputs E, L, and G.
C26. A Boolean function f is said to be positive unate if f can be expressed
in a form where all the variables appear in uncomplimented form, and
only the AND and OR Boolean operators are used. For example, the
function g1 = X1 X2 + X2 X3 is positive unate but g2 = X1 X2 + X̄2 X3
is not. Consider the following circuit in Figure 5 and determine which
of the two functions f1 and f2 are positive unate.

Y f1

X
Y
f2

Figure 5: Boolean circuit for Question C25.

C27. Let us consider a household, as shown in Figure 6, with two lights.

One of these lights is at porch gate and the other is inside the room.
The lights are controlled by three switches A, B and C; out of which
two are inside the house and one is outside the house. Both the lights
are OFF when all the switches are OFF. Both the lights are ON when
all the three switches are ON. If any two switches are ON then the
porch light is ON. If exactly one of A, B or C is ON, the light inside
the room is ON. Design a circuit using only NAND gates to realize

16
 the above scenario. Justify whether this circuit involves the minimum
number of NAND gates.

Figure 6: A household with a pair of lights for Question C27.

C28. Let α be the percentage of a program code which can be executed

simultaneously by n processors in a computer system. Assume that
the remaining code must be executed sequentially by a single processor.
Each processor has an execution rate of x MIPS, and all the processors
are of equal capability.
(a) Derive an expression for the effective MIPS rate when the code
is executed using n processors, in terms of n, α and x.
(b) Given n = 16 and x = 4 MIPS, determine the value of α to yield
a system performance of 40 MIPS.

C29. (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 2’s
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.

17
C30. A machine M has the following five pipeline stages; their respective
time requirements in nanoseconds (ns) are given within parentheses:
F -stage — instruction fetch (9 ns),
D-stage — instruction decode and register fetch (3 ns),
X-stage — execute/address calculation (7 ns),
M -stage — memory access (9 ns),
W -stage — write back to a register (2 ns).
Assume that for each stage, the pipeline overhead is 1 ns. A program
P having 100 machine instructions runs on M, where every 3rd in-
struction needs a 1-cycle stall before the X-stage. Calculate the CPU
time in micro-seconds for completing P .

C31. The CPU of a computer has a ripple-carry implementation of a 2’s

complement adder that takes two 8-bit integers A = a7 a6 . . . a0 and
B = b7 b6 . . . b0 as inputs, and produces a sum S = s7 s6 . . . s0 , where
ai , bi , ci ∈ {0, 1} for (0 ≤ i ≤ 7).
Let A = 1001 1001 and B = 1000 0110. What will be the output S of
the adder? How will the value of S be interpreted by the machine?

C32. Add the following two floating point numbers A and B given in IEEE-
754 single precision format and show the sum S in the same format.
A: 0000011000100 0000 000000000000001
B: 1000011000100 0000 000000000000001

C33. Draw a complete binary tree T with (N − 1) nodes where N = 2n .

Suppose each node in T is a processor and each edge of T is a physical
link between two processors through which they can communicate.
Given M arrays Ai = {e1i , e2i , . . . , eN i } for 1 ≤ i ≤ M , develop an
algorithmPfor the given architecture to compute the sum of each array
SUMi = N j=1 eji for all i in O(log N + M ) time.

C34. 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.
(a) What is the average access time of the system considering only
memory read cycles?
(b) What is the average access time of the system considering both
read and write requests?

18
C35. Consider a machine with four registers (one of which is the accumulator
A) and the following instruction set.
• LOAD R and STORE R are indirect memory operations that load
and store using the address stored in the register R. Thus, LOAD
R loads the contents of memory[R] into A and STORE R stores the
contents of A in memory[R].
• MOV R1 R2 copies the contents of register R1 into register R2.
• ADD R and SUB R operate on the accumulator and one other reg-
ister R, such that A = A op R.
• LDC n stores the 7-bit constant n in the accumulator.
• BRA, BZ, and BNE are branch instructions, each taking a 5-bit
offset.
Design an instruction encoding scheme that allows each of the above
instructions (along with operands) to be encoded in 8 bits.

C36. A program P consisting of 1000 instructions is run on a machine at 1

GHz clock frequency. The fraction of floating point (FP) instructions
is 25%. The average number of clock-cycles per instruction (CPI) for
FP operations is 4.0 and that for all other instructions is 1.0.
(a) Calculate the average CPI for the overall program P .
(b) Compute the execution time needed by P in seconds.

C37. The average memory access time for a microprocessor with first level
cache is 3 clock cycles.
• If data is present in the cache, it is found in 1 clock cycle.
• If data is not found in the cache, 100 clock cycles are needed to
get it from off-chip memory.
It is desired to obtain a 50% improvement in average memory access
time by adding a second level cache.
• This second level cache can be accessed in 6 clock cycles.
• The addition of this second level cache does not affect the first
level cache.
• Off-chip memory accesses still require 100 clock cycles.
To obtain the desired speedup, how often must data be found in the
second level cache?

19
C38. Two modules M1 and M2 of an old machine are being replaced by
their improved versions M3 and M4 , respectively in a new machine.
With respect to the old machine, the speed-up of these modules (M3
and M4 ) are 30 and 20, respectively. Only one module is usable at
any instant of time. A program P , when run on the old machine, uses
M1 and M2 for 30% and 20% of the total execution time, respectively.
Calculate the overall speed-up of P when it is executed on the new
machine.

C39. The page size in a system is increased while keeping everything else
(including the total size of main memory) the same. For each of the
following metrics below, explain whether its value is generally expected
to increase, decrease, or not change as a result of this increase in page
size:
(a) size of the page table of a process;
(b) TLB hit rate.

C40. The byte-addressable logical address space in a lightweight computing

platform consists of 128 segments, each of capacity 32 pages, each of
which can hold 4096 bytes. The physical memory (also byte-addressable)
consists of 214 page frames, each 4096 bytes long.
(a) Formulate the logical and physical address formats.
(b) If segment table entries and page table entries both occupy 4
bytes each, compute the size in bytes of (i) the segment table and
(ii) page tables for any process.
(c) Assume that no swap space is available. If the kernel takes up
12 × 220 bytes, and the rest of the physical memory may be used
to hold processes, compute the maximum number of processes
that the kernel can handle concurrently in the worst case.

C41. In a Buddy memory allocation system, a process is allocated an amount

of memory whose size is the smallest power of 2 that is greater than
or equal to the amount requested by the process.
A system using buddy memory allocation has 1MB memory. For a
given sequence of nine processes, their respective memory requirements
in KB are: 50, 150, 90, 130, 70, 80, 120, 180, 68.
(a) Illustrate with an allocation diagram to justify whether all the
requests, in the given order, can be complied with. Assume that

20
 memory once allocated to a process is no longer available during
the entire span of the above sequence.
(b) Calculate the total memory wasted due to fragmentation in your
memory allocation by the above scheme.

C42. Figure 7 pictorially shows the layout of a file descriptor of a file system.
It uses 4 direct, 1 indirect, and 1 doubly indirect block addresses. If
the size of a disk block is 64 bytes and the size of each disk block
address is 8 bytes, calculate the maximum possible file size this file
system may have. Give the answer in the form of a × 2A , where a (not
divisible by 2) and A both denote integers.

Figure 7: A file system with direct and indirect blocks.

21
C43. Two processes P1 and P2 have a common shared variable count. While
P1 increments it, P2 decrements it. Given that R0 is a register, the
corresponding assembly language codes are:
P1 : count++ P2 : count–
MOV count R0 MOV count R0
ADD #1 R0 SUB #1 R0
MOV R0 count MOV R0 count
Give an example to justify whether a race condition may occur if P1
and P2 are executed concurrently.

C44. Consider the following solution to the critical section problem for two
processes. The two processes, P0 and P1 , share the following variables:

char flag[2] = {0,0};

char turn = 0;

The program below is for process Pi (i = 0 or 1) with process Pj (j = 1

or 0) being the other one.
do {
flag[i] = 1;
while (flag[j])
if (turn == j) {
flag[i] = 0;
while (turn == j) {};
}
...
CRITICAL SECTION
...
turn = j;
flag[i] = 0;
...
REMAINDER SECTION
...
} while (1);

Does this solution satisfy the mutual exclusion, progress and bounded
waiting properties?

22
C45. Suppose that an operating system provides two functions, block()
which puts the calling process on the blocked queue, and wakeup(P)
which moves process P to the runnable queue if it is currently on the
blocked queue (otherwise, its behaviour is unpredictable).
Consider two processes A and B running the code given below. The
intended behaviour of the code is to have A and B run forever, alter-
nately printing their names on the screen.
void A() void B()
{ while(1) { { while(1) {
block(); printf("B");
printf("A"); wakeup(A);
wakeup(B); block();
} }
} }
(a) Construct a scenario in which the intended behaviour would not
be observed.
(b) Redesign the code using semaphore(s) so that it works correctly.
You should show the initialisation of the semaphore(s), and the
calls to wait() and signal() made by A and B.

C46. A system has 4 processes A, B, C, D and 5 allocatable resources

R1 , R2 , R3 , R4 , R5 . The maximum resource requirement for each pro-
cess and its current allocation are as follows.

Process Maximum Allocation

R1 , R 2 , R 3 , R 4 , R 5 R1 , R 2 , R 3 , R 4 , R 5

A 1, 1, 2, 1, 3 1, 0, 2, 1, 1
B 2, 2, 2, 1, 0 2, 0, 1, 1, 0
C 2, 1, 3, 1, 0 1, 1, 0, 1, 0
D 1, 1, 2, 2, 1 1, 1, 1, 1, 0

Suppose the currently available count of resources is given by 0, 0, X,

1, 1. What is the minimum value of X for which this is a safe state?
Justify your answer.

23
C47. Consider a uniprocessor system with four processes having the follow-
ing arrival and burst times:

Arrival Time CPU Burst Time

P1 0 10
P2 1 3
P3 2.1 2
P4 3.1 1

(a) Calculate the average waiting time and also the average
turnaround time if shortest (remaining) job first (SJF) schedul-
ing policy is used with pre-emption. Assume that the context
switching time is zero. Note that in SJF, if at any point there is
a tie, then the job that arrived earlier will get priority.
(b) Now consider the continuous arrival of new jobs at times 4, 5,
6, 7, . . . following P 4, with CPU burst times of 2 units each. In
this case, what will be the turnaround time of P 1? Justify your
answer.

C48. Let us consider the relation schema <CTHRSG>, where the attributes
are C ≡ Course, T ≡ Teacher, H ≡ Class Hour, R ≡ Classroom, S ≡
Student, G ≡ Grade. We assume the following:
• Each course is taught by one teacher.
• Only one course can be taught in a classroom at one time.
• A teacher can be in only one classroom at one time.
• Each student has one grade in each course.
• A student can be in only one classroom at one time.
(a) Write down the above statements in terms of functional depen-
dencies.
(b) Determine a candidate key for the schema <CTHRSG>.
(c) Show that the schema <CTHRSG> is not in BCNF. Decompose
it into schemas which are in BCNF.
(d) Justify whether the above decomposition is dependency preserv-
ing or not.

24
C49. (a) Consider the following relations:
Student(snum: integer, sname: string, major: string, level: string,
age: integer)
Class(name: string, meets at: string, room: string, fid: integer)
Enrolled(snum: integer, cname: string)
Faculty(fid: integer, fname: string, deptid: integer).
Write an SQL query to find the names of faculty members who
teach in every room in which some class is taught.
(b) Let R be a relation with functional dependencies F. For any
subset of attributes X ⊂ R, the closure of X is defined as the set

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

For two non-empty attribute sets Y and Z in R, prove or disprove

each of the following statements:
(i) (Y + Z)+ = (Y Z)+ ;
(ii) (Y Z)+ = Y + Z + .

C50. Let R = (A, B, C, D, E, F ) be a schema with the set F = {A → BC,

CD → E, B → D, E → A} of functional dependencies. Suppose R is
decomposed into two schemata R1 = (A, B, C) and R2 = (A, D, E, F )
(a) Is this decomposition loss-less? Justify.
(b) Is this decomposition dependency preserving? Justify.
(c) Identify all the candidate keys for R.
(d) Decompose R into normalized sets of relations using 3NF.
(e) If a new dependency A ↠ F (multi-valued dependency) is intro-
duced, what would be the new set of normalized relations?

C51. Consider the relations r1(A, B, C), r2(C, D, E) and r3(E, F ). Assume
that the set of all attributes constitutes the primary keys of these rela-
tions, 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 r1 has 1000 tuples, r2 has 1500 tuples, and r3 has 750 tuples,
then give the ordering of the natural join r1 ./ r2 ./ r3 for its efficient
computation. Justify your answer.

25
C52. A school database maintains the following relations for its students,
teachers and subjects:

• Student(st_name, st_address, class, section, roll_no, regn_no)

• Teacher(t_name, t_address, tel_no)
• Subject(s_name, t_name, text_book, class)

Consider the following constraints on the existing data.

• A student after admission to the school is assigned with a unique

regn_no. However, a student also gets a roll_no that starts from
1 for each class and section. A class can have many sections and
a student is placed in only one class and section as expected in a
school.
• In the school a teacher’s name (t_name) has been found to be
unique. However, more than one teacher may stay at the same
address and the tel_no is a land line connection where an address
will have only one such telephone.
• A subject name (s_name) is unique but the same subject may
be taught in many classes (for example, History may be taught
in many classes with different contents but s_name remains the
same). Every subject has a set of standard text_books for a
class and there may be more than one teacher who can teach the
subject. Any teacher may use any of the standard text books to
teach a subject.
(a) Considering the above constraints, identify the functional/multi-
valued dependencies present and normalize the relations.
(b) Using the normalized set of relations answer the following query
using relational algebra or SQL: List all the teachers (t_name)
who can teach History in Class V and reside in “Baranagar”
(name of a locality). Consider that any address offers a local-
ity name.

26
C53. Two queries equivalent to each other are specified for a relation
R(A, B, C, D, E, F ). The queries are:

• πA,B,C (σB>500 (R))

• σB>500 (πA,B,C (R))

The system maintains a B+ tree index for (A, B, C) on R. However,

the index is unclustered. The relation R occupies 100 pages and the
index structure needs 5 pages only. Compute the number of disk ac-
cesses required for each of the queries and thereby decide which one of
the two queries will be preferred by the query optimizer for minimum
cost of execution. The cost of query execution is primarily dependent
on the number of disk accesses.

C54. Recall the stop-and-wait and sliding window protocols for a packet-
based data transmission. The stop and wait protocol sends one packet
and waits for the acknowledgment to arrive. The waiting mechanism
results in wastage of network bandwidth. In order to improve the
bandwidth utilization, the sliding window protocol utilizes pipelined
communication where multiple packets are sent without waiting for
acknowledgements. In the latter case, each packet is stamped with
a sequence number. The sequence number in each packet helps the
sender to decide whether it should continue the transmission or wait
for acknowledgement. It also helps the receiver to arrange the packets
in order and to prepare acknowledgements.
Consider that a sliding window protocol is used for data transmission
between two stations, say P and Q, located at a distance of d km.
Assume that all the packets are k bits long. The propagation delay is t
sec/km and the channel capacity is b bits/sec. Calculate the minimum
number of bits required for the sequence number field in a packet for
maximum utilization of the bandwidth. Assume that the processing
delay is negligible.

C55. A block of bits with n rows and m columns uses horizontal and vertical
parity bits for error detection. If exactly 4 bits are in error during
transmission, derive an expression for the probability that the error
will be detected.

27
C56. In a computer network, 2k host computers H0 , H1 , . . . , H2k −1 are con-
nected via routers that are connected in the form of a binary tree. An
example is shown in Figure 8 below for k = 3. Each node labelled Ri
corresponds to a router at level 3 − i (i = 1, 2, 3); the nodes at the
leaf level correspond to the hosts.

R0
Level 3

R1 R1
Level 2

R2 R2 R2 R2
Level 1
H0 H1 H2 H3 H4 H5 H6 H7

Figure 8: Binary tree of routers in Question C56.

All the lines are full-duplex, and routers are faster than the links. Also,
all links at the same level are of the same capacity. Traffic is always
routed via shortest path. Suppose the capacity of each link at level 1
is 1 Mbps.
(a) Find the minimum capacities to be assigned to the links at upper
layers i (1 < i ≤ k), such that the router R0 is never congested.
Prove the correctness of your result.
(b) With the link capacities found in (i), show that there always
exist traffic patterns that may congest any router Ri other than
R0 . Justify your answer.
C57. 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.
(a) Express the maximum efficiency of this network when only a sin-
gle 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.

28
C58. Station A is sending data to station B over a full duplex error free chan-
nel. A sliding window protocol is being used for flow control. The send
and receive window sizes are 6 frames each. Each frame is 1200 bytes
long and the transmission time for such a frame is 70 µS. Acknowl-
edgment frames sent by B to A are very small and require negligible
transmission time. The propagation delay over the link is 300 µS.
What is the maximum achievable throughput in this communication?

C59. Consider a large number of hosts connected through a shared commu-

nication channel. The hosts transmit whenever they have any data.
However, if two data packets try to occupy the channel at the same
time, there will be a collision and both will be garbled. The hosts
retransmit these packets that suffered collisions. Assume that the gen-
eration of new packets by a host is a Poisson process and is independent
of other hosts. The total number of transmissions (old and new pack-
ets combined) per packet time follows Poisson distribution with mean
2.0 packets per packet time. Compute the throughput of the channel.
(Packet time is the amount of time needed to transmit a packet.)

C60. A heavily loaded 1 km long, 10 Mbps token ring network has a propaga-
tion speed of 200 meter per micro-second. Fifty stations are uniformly
spaced around the ring. Each data packet is 256 bits long, including 32
bits of header. The token is of 8 bits. What is the effective data rate
of the network assuming the stations always have packets to transmit?

29
 II. Mathematics for Computer Science

MC1. Let p and q be distinct primes and m = pq +q p . What is the remainder

if m is divided by pq?

MC2. Let H = {1 + 4k : k ∈ Z, k ≥ 0}. An element x ∈ H is called H-prime

if x ̸= 1 and x cannot be written as product of two strictly smaller
elements of H.
(a) Show that xy ∈ H for all x, y ∈ H.
(b) Prove that every x ∈ H greater than 1, can be factored as a
product of H-primes but unique factorisation does not hold.

X
n X
n
MC3. Let f (x) = j
aj x and b(x) = bj xj , where aj , bj ∈ Z, j = 0, . . . , n.
j=0 j=0
For m ∈ N, we say f ≡ g mod m if aj = bj mod m for 0 ≤ j ≤ n.
For an odd prime p > 0, let

f (x) = xp−1 − 1 and g(x) = (x − 1)(x − 2) · · · (x − p + 1).

Prove that
(a) the polynomial f (x) − g(x) has degree p − 2, and
(b) f ≡ g mod p.

n
MC4. For n ≥ 1, let fn = 22 + 1. Show that if m and n are relatively
prime then fm and fn are relatively prime. Hence show that there are
infinitely many primes.

MC5. Show that for n ≥ 2, 1 + 1/2 + · · · + 1/2n is not an integer. You may
use the fact that there is a prime p between n and 2n for n ≥ 2.
(hint: Show that such a prime divides the denominator of 1 + 1/2 + · · · + 1/2n.)

MC6. Let p be a prime and let A = {1, 2, . . . , p − 1}. Prove that there is a
bijection f from A onto A such that kf (k) ≡ 1 (mod p) for each k ∈ A.
Hence deduce that if p is an odd prime, then p divides the numerator
of 1 + (1/2) + · · · + (1/(p − 1)).

30
 MC7. Let p be a prime number. What is the largest power of p that divides
p2 ! ?

MC8. Show that the 100 digit number 11 · · · 1 is divisible by the prime num-
ber 101.

MC9. Let p and q be prime numbers. If q divides 2p − 1 then show that p

divides q − 1.

MC10. If a and b are integers such that 9 divides a2 + ab + b2 then show that
3 divides both a and b.

MC11. Let c be a 3n digit number whose digits are all equal. Show that 3n
divides c.

MC12. Show that, for distinct positive integers m and n, the greatest common
m n
divisor of 22 + 1 and 22 + 1 is 1. Deduce that the number of prime
integers is infinite.

MC13. Let D = {d1 , d2 , . . . , dk } be the set of distinct divisors of a positive

integer n (D includes 1 and n). Show that

X
k
p π
sin−1 logn di = × k.
4
i=1

√
hint: sin−1 x + sin−1 1 − x2 = π
2

(p−1)!
MC14. Let p be a prime and r an integer, 0 < r < p. Show that r!(p−r)! is an
integer.

MC15. Show that if a prime number is divided by 30, then the remainder is
either one or a prime number.

√ √
MC16. Prove that n−1+ n + 1 is an irrational number for all positive
integers n.

31
MC17. Show that n5 and n have the same last digit for all positive integers
n.

MC18. For all integers n ≥ 1, show that 22n − 3n − 1 is divisible by 9.

q
3n−5
MC19. Find all the integers n for which n+1 is also an integer.

MC20. Let p, q be distinct odd primes. Prove that the equation x2 = 1 has
exactly four (distinct) solutions in the ring of integers modulo pq.

MC21. For any x ∈ R, let [x] be the greatest integer not exceeding x. Let m
be a positive integer. Show that
√ √ √
[(1 + 3)2m+1 ] = (1 + 3)m+1 + (1 − 3)m+1 .

MC22. Let m, n be natural numbers. Show that m and m4n+1 have same last
digit in their decimal expansions.

MC23. Does there exist an integer x satisfying the following congruences?

10x = 1 (mod 21)

5x = 2 (mod 6)
4x = 1 (mod 7)
Justify your answer.

MC24. Let M be a 4-digit positive integer. Let N be the 4-digit integer

obtained by writing the digits of M in reverse order. If N = 4M , then
find M . Justify your answer.

MC25. Let A1 , A2 , . . . , An be distinct subsets of a set X. Show that there

exists a subset B of X having at most n elements such that B ∩
A1 , B ∩ A2 , . . . , B ∩ An are all distinct.
(hint: Use induction on n).

MC26. Find the number of squares in [0, 8] × [0, 8] ⊆ R2 whose vertices have
integer coefficients and the sides are parallel to the coordinate axes.

32
   Xn  
n m−1
MC27. (a) Show that = .
k k−1
m=k
(b) Prove that
       
n 1 n 1 n n−1 1 n 1 1 1
− + − · · · +(−1) = 1+ + +· · ·+ .
1 2 2 3 3 n n 2 3 n

MC28. Prove that any set of n2 + 1 points in a square with side length one
contains
√ two points with distance between them less than or equal to
2
n .

MC29. Let n be a positive integer and p a prime. Show that the number of
ordered basis of a vector space of dimension n over a field of order p is

(pn − 1)(pn − p)(pn − p2 ) . . . (pn − pn−1 ).

Deduce that this number is a multiple of n!.

MC30. If p is an odd prime, show that

!
2p − 1
≡ 1 mod p2 .
p−1

MC31. Let X be a set consisting of 5 elements. Let

A = {f : X → X; f (f (x)) = x for each x ∈ X}.

Compute the number of elements of A.

MC32. Let L and L′ be two sets of parallel lines in R2 consisting of m and n

lines, respectively. Assume that every line in L intersects every line in
L′ . Find the number of parallelograms formed by the lines in L ∪ L′ .

MC33. A square in the plane is subdivided into n2 squares S1 , · · · , Sn2 of

equal size by horizontal and vertical lines. Determine the number of
squares in the plane that are unions of a subcollection Si1 , · · · , Sik .

MC34. Find all sets of consecutive natural numbers whose sum is 54.

33
MC35. If 70% of students in a class pass the algebra test, 75% pass the analysis
test, 80% pass the geometry test, and 85% pass the number theory test,
what is the least percentage of students who pass all four subjects?

MC36. Find the number of elements in the set

S = {(a, b, c) ∈ N3 : a + b + c = 25},

where N is the set of natural numbers.

MC37. Let r be a positive real number. Prove that among the numbers
r, 2r, . . . , (n − 1)r there is at least one number which differs from an
integer by at most n1 .

MC38. How many of the n! terms in the expansion of a determinant of order

n remain, if all the elements of the main diagonal are set to zero ?

MC39. Find the divisors between 60 and 65 of 248 − 1.

MC40. Show that every member of the sequence

1107, 10017, 100117, . . .

is divisible by 53.

MC41. There are 102 distinct points in the unit square [0, 1] × [0, 1]. Show
that there are at least two distinct points such that the square of the
distance between them is at most 0.02.

MC42. Suppose that there are n boxes labelled 1, 2, . . . , n and there are n balls
also labelled similarly. The balls are thrown into boxes completely
randomly so that each box receives one ball.
(a) How many possible arrangements of balls in boxes is possible?
(b) Find the probability that the ball labelled 1 goes into the box
labelled 1.
(c) Find the probability that at least one ball is in the box with the
same label.

34
MC43. Show that the number of bijections f of {1, 2, . . . , n} such that f (i) ̸= i
for any i is equal to
Xn
n!
(−1)j .
j!
j=0

MC44. Find the smallest integer n > 0 such that 2012 divides 9n − 1. (Hint:
251 and 503 are prime numbers).

MC45. Let pk be the k-th prime number. Show that there are infinitely many
k such that
pk+1 − pk > 2.

MC46. For a real number x, [x] denotes the largest integer less than or equal
to x.
(a) For reals x, y show that [x + y] − [x] − [y] is zero or one.
(b) For m ≥ 1 and a prime p, let αp (m) be the largest power of p
which divides m (i.e., pαp (m) divides m but pαp (m)+1 does not.) It
X∞  
n

log 2n
is known that αp (n!) = k
. Show that αp 2nn ≤ .
p log p
k=1
(hint: How many terms in the formula for αp (n!) are non-zero?)

MC47. Consider the sets X and Y given below:

(a) (b) (a) (b) (a) (b)
X = {x1 , x1 , x2 , x2 , . . . , xk , xk }
(a) (b) (c) (a) (b) (c)
Y = {y1 , y1 , y1 , y2 , y2 , y2 , . . . , ym , ym , ym }.
(a) (b) (c)

Construct an undirected graph G = (X ∪ Y, E) by including the fol-

lowing edges in E:
(a) (b)
• for each i = 1, 2, . . . , k, join xi and xi by an edge;
(a) (b)
• for each i = 1, 2, . . . , m, join yi and yi by an edge; also join
(b) (c) (c) (a)
yi and yi by an edge, and yi and yi by an edge;
• for each y ∈ Y , join y to exactly one element x of X.
(a) Show that a vertex cover of G cannot have less than k + 2m
elements.

35
 (b) Suppose G′ is obtained from G by deleting all edges of the form
(x, y) where x ∈ X and y ∈ Y . Compute the number of distinct
vertex covers for G′ .
[ Recall that, for a graph G = (V, E), a subset V ′ of V is a vertex
cover, if for every e = (v1 , v2 ) ∈ E, either v1 ∈ V ′ or v2 ∈ V ′ . ]

MC48. In a LAN, n2 routers are connected in an n × n mesh such that R(i, j)

represents a router in the i-th row and j-th column of the mesh.
(a) Find how many distinct shortest paths exist between two routers
R(i1 , j1 ) and R(i2 , j2 ) (1 ≤ i1 , j1 , i2 , j2 ≤ n). Two paths are
distinct if they differ in at least one link.
(b) At most how many of these distinct shortest paths will be node
disjoint, i.e., with no common node except the source and the
destination? Justify your answer.

MC49. Let G be a graph on n vertices and having m edges. Prove the following
statements.
(a) If the maximum degree of a vertex in G is ∆, then there is no
independent set in G containing more than n − m
∆ vertices.
(b) There is a bipartite subgraph of G that contains at least m/2
edges.

MC50. Construct a tree such that no matter how you colour its vertices prop-
erly using two colours (i.e. two adjacent vertices do not get the same
colour), every maximum independent set of the tree contains vertices
of both colours.

MC51. Let G be a connected graph that cannot be disconnected by the re-

moval of fewer than k edges. If every vertex of G has even degree and
S is a set of k edges that disconnects G, then show that k is even.

MC52. Let G be a graph in which every vertex has odd degree. Let u be a
vertex and C a connected component of G − u. Prove that u has an
odd number of neighbours in C if and only if |C| is odd.

36
MC53. A planar graph is said to be an outerplanar graph if it has a planar
drawing in which every vertex appears on the boundary of the outer
face. Let G be a planar graph. Show that if it is possible to add edges
to G in order to make it a planar graph that contains a Hamiltonian
cycle, then there exist two subgraphs G1 , G2 of G such that G1 and
G2 are both outerplanar and E(G) = E(G1 ) ∪ E(G2 ).

MC54. Construct a planar graph with as many vertices as possible that has
the property that it can be obtained by removing three edges from a
complete graph.

MC55. Let G be a directed acyclic graph in which there is no directed path

containing more than k vertices. Then prove that the vertices of G
can be coloured with k colours such that no two adjacent vertices get
the same colour.

MC56. Let T = (V, E) be a rooted tree, and let v ∈ V be any vertex of T .

• The eccentricity of v is the maximum distance from v to any other
vertex in T .
• The centre C of T is the set of vertices which have the minimum
eccentricity among all vertices in T .
• The weight of v is the number of vertices in the largest subtree
of v.
• The centroid G of T is the set of vertices with the minimum
weight among all vertices in T .
Construct a tree T that has disjoint centre and centroid, each having
two vertices, i.e., C ∩ G = ∅ and |C| = |G| = 2.

MC57. Consider an urn containing 10 red balls, 10 white balls, and 10 black
balls. Balls are drawn at random with replacement one by one. Let T
be the minimum number of draws required to get balls of three colours.
Find the distribution of T .

MC58. Suppose X is a non-negative integer-valued random variable such that

6+k
P (X = k + 1) = P (X = k) for k = 0, 1, 2, . . . ,
3k + 1
and P (X = 0) = 1/4. Find E(X).

37
MC59. Suppose an urn contains w white balls, b black balls, and r red balls;
w, b, r > 0. Balls are drawn one by one without replacement and at
random until all balls are exhausted. Find the probability that, among
the three colours, the white balls are exhausted first.

MC60. Suppose there are five pairs of shoes in a closet, from which four shoes
are taken out at random. Calculate the probability that among these
four shoes, there is at least one complete pair.

MC61. (a) Consider an alphabet A = {0, 1, . . . , 9}. Design a Determinis-

tic Finite Automaton (DFA) that accepts strings over A whose
decimal equivalent leaves the remainder 3 if divided by 6.
(b) Using Pumping Lemma, prove that the language {an : n is a
perfect square} is not regular.

MC62. Let M = (Q, Σ, δ, qo , F ) be a Deterministic Finite Automaton (DFA),

and let L = L(M ) be the language accepted by M . Consider another
DFA M ′ = (Q, Σ, δ, qo , Q), and let L′ = L(M ′ ).
(a) Give an example of a language L ⊆ {0, 1}∗ for which L(M ′ ) =
prefix (L).
(b) Give an example of a language L ⊆ {0, 1}∗ for which L(M ′ ) ̸=
prefix (L).
Justify your answer in each case.
Recall that for a given alphabet Σ, a string β ∈ Σ∗ is said to be a
prefix of a string α ∈ Σ∗ if α = βγ for some γ ∈ Σ∗ . For example, the
prefixes of 010 are ε, 0, 01 and 010. Given a language L ⊆ Σ∗ , prefix (L)
is defined as

prefix (L) = {x ∈ Σ∗ | x is a prefix of some y ∈ L}.

MC63. Construct a finite state machine that accepts all the binary strings in
which the number of 1’s and number of 0’s are divisible by 3 and 2,
respectively.

38
MC64. Describe the language recognized by the following machine.
a
b
a b
b b

a a

a,b

MC65. Consider the grammar E → E + n|E × n|n. For a sentence n + n × n,

find the handles in the right sentential form of the reductions.

MC66. Design a Turing machine that recognizes the unary language consisting
n
of all strings of 0’s whose length is a power of 2, i.e., L = {02 |n ≥ 0}.

MC67. Write a context-free grammar for the language consisting of all strings
over {a, b} in which the number of a’s is not the same as that of b’s.

MC68. Let the set D = {p | p is a polynomial over the single variable x, and
p has a root which is an integer (positive or negative)}.
(a) Design a Turing machine (TM) to accept D.
(b) Can D be decided by a TM? Justify your answer.

MC69. Give a context-free grammar G that generates L = {0i 1j 0k | i+k = j}.

Prove that L = L(G).

MC70. Write a regular expression for all strings of 0’s and 1’s in which the
total number of 0’s to the right of each 1 is even. Justify your answer.

39
MC71. Construct a deterministic finite automaton accepting the following lan-
guage:
{w ∈ {0, 1}∗ : w has an equal number of 01’s and 10’s }.
For example, 101 is in the language because it contains one instance
of 10 and one instance of 01 as well.

MC72. Define a language L ⊆ {0, 1}∗ as follows:

L = {x | The number of 1s in x that are not immediately

preceded by a 0 is even}.

For example, 011011 ∈ L because it has two 1s that are not

immediately preceded by a 0, whereas 111 ̸∈ L because it has three
1s that are not immediately preceded by a 0. Draw a Deterministic
Finite Automaton (DFA) to recognize L. You will get full credit if
your DFA has no more than 4 states.

MC73. Consider the following statement:

For all languages L ⊆ {0, 1}∗ , if L∗ is regular then L is regular.
Is the above statement true? Justify your answer.

40
 III. Mathematics
Unless otherwise specified,
N denotes the set of positive integers;
Z denotes the set of integers;
Q denotes the set of rational numbers;
R denotes the set of real numbers;
C denotes the set of complex numbers.

M1. Let C be a closed, symmetric (i.e., if x ∈ C then −x ∈ C) convex

subset of Rn such that
[
mC = Rn , where mC = {mx | x ∈ C}.
m∈N

Prove that there exists r > 0 such that

B(0, r) = {x ∈ Rn | ∥x∥ < r} ⊆ C.

R∞
M2. Define f (x) = ex /2 x e−t /2 dt for x > 0. Show that 0 < f (x) < 1/x
2 2

and f (x) is monotonically decreasing for x > 0.

M3. Evaluate    

1
lim x 2
1 + 2 + 3 + ··· +
x→0 |x|
For any real number a, [a] is the largest integer not greater than a.

M4. (a) Let the sequences {an }∞ ∞

n=1 and {bn }n=1 be given by

a2n + b2n a n + bn
0 < b1 < a1 , an+1 = and bn+1 = for n ∈ N.
a n + bn 2
Show that both sequences are monotone and they have the same
limit.
(b) Let the polynomial fn (x) = xn + a1 xn−1 + · · · + an−1 x + an , n ∈
N with all integer coefficients be such that fn (b1 ) = fn (b2 ) =
fn (b3 ) = fn (b4 ) = fn (b5 ) = 19 for five distinct integers b1 , b2 , b3 , b4
and b5 . How many different integer solutions exist for fn (x) = 23?
Justify your answer.

41
 (c) Consider the matrix
 
1 3 2
 
A= 
 0 4 5 .
0 0 9
How many square roots does A have? Justify your answer.

M5. (a) Suppose f is a real-valued continuous function defined on [−2, 2]

and is three times differentiable in (−2, 2). If f (2) = −f (−2) = 4
and f ′ (0) = 0, then show that there exists x ∈ (−2, 2) such that
f ′′′ (x) ≥ 3.
(b) Suppose f is a real-valued continuous function defined on [0, 1]
such that (2x−1)(2f (x)−x) > 0 for all x ̸= 1/2. If f ′ (1/2) exists,
then show that it cannot be smaller than 1/2.
(c) Find all values of α ∈ R for which the sum
X α
nn e−n
n≥1

is convergent.

M6. (a) Compute the following limit with full justification:

sin 1 + 2 sin 12 + 3 sin 31 + · · · + n sin n1
lim .
n→∞ n
(b) Show that there exists no one-to-one function f : R → R with
the property that for all x ∈ R, f (x2 ) − (f (x))2 ≥ 1/4.
(c) If f is real-valued continuous function defined on [0, 1] such that
Z 1
f (x) xn = 0
0

for all n = 0, 1, 2, . . ., then show that f (x) = 0 for all x ∈ [0, 1].

M7. (a) Let fn : R → R be differentiable for each n = 1, 2, . . . with

| fn′ (x) |≤ 1 for all n and x. Assume
lim fn (x) = g(x),
n→∞

for all x. Prove that g : R → R is continuous.

42
 (b) Let f : [0, 1] → R be continuous over [0, 1], differentiable over
(0, 1), f (0) = 0, and 0 ≤ f ′ (x) ≤ 2f (x).
Show that f is identically 0.
(c) Let f : [0, 1] → R be a continuous function. Show that
Z 1
lim (n + 1) xn f (x)dx = f (1).
n→∞ 0

M8. (a) Let {an }n≥0 be a non-negative sequence satisfying

am+n < am + an + 1, for all positive integers m, n. Show that
(i) a17 < 2a8 + a1 + 2.
(ii) ann converges as n → ∞.
(b) Let εn be the fractional part of n!e, where n is a positive integer.
1
(i) Show that n+1 < εn < n1 for all positive integers n.
(ii) Prove that n sin(2n!eπ) converges to 2π as n → ∞.

M9. (a) Find the number of positive integers with k digits, that do not
contain the digit 7.
(b) Let S denote the set of all positive integers that do not contain
the digit 7. Prove that the infinite series
X1
n
n∈S

converges.

M10. (a) Let x be an irrational number. Show that for any positive integer
k ≥ 1, there exists δk > 0, such that the open interval (x − δk , x +
δk ) does not contain any rational number of the form kp , where p
is an integer.
(b) Consider the function f defined on [1, 2] as follows:



 0 if x ∈ [1, 2] is irrational
p
k if x ∈ [1, 2] is a rational k where p and
f (x) = 1


 k are integers prime to each other

Show that f is discontinuous at every rational x ∈ [1, 2] and

continuous at every irrational x ∈ [1, 2].

43
M11. (a) Show that for every θ ∈ (0, π/2), there exists a unique real xθ
such that
3
(sin θ)xθ + (cos θ)xθ = .
2
(b) Find all possible real values of α for which the following improper
integral exists: Z 1
|x|α dx.
−1

M12. Let f : R → R be such that f is differentiable at c ∈ R. Let {yn }

be a decreasing sequence of real numbers and {xn } be an increasing
sequence of real numbers, both converging to c. Show that

f (xn ) − f (yn )
lim = f ′ (c).
n→∞ x n − yn

M13. Suppose f : R → R is a continuous function. If it is an injective

function, show that f is monotone. Hence or otherwise, show that any
continuous function f with f (f (x)) = −x cannot be injective.

M14. Let
 f : R2 → R have continuous partial derivatives and satisfy
 ∂f 
 
 ∂xj (x) ≤ K for all x = (x1 , x2 ), j = 1, 2. Prove that
  √
f (x) − f (y) ≤ 2K∥x − y∥.
p
Here, ∥(x1 , x2 )∥ = x21 + x22 .

M15. Let n be a positive integer and φ : Z → Z ⊕ Zn be the homomorphism

defined by φ(1) = (n, 1̄), where 1̄ denotes the set of integers congruent
to 1 mod n. Prove that (Z ⊕ Zn )/Im(φ) is cyclic and find its order.

M16. Let α ∈ C be a root of the polynomial X 4 + 1 ∈ Q[X]. Consider the

field extension Q ,→ Q(α).
(a) With complete justification determine the degree of this
extension.
(b) Find three distinct fields K 1 , K2 , K3 such that
Q ⊊ Ki ⊊ Q(α) for i = 1, 2, 3.

44
M17. Let X be a set containing at least two elements and G be a group
with identity element e. Suppose that there is a map α : G × X → X.
Let us write α(g, x) as g · x. Assume that the following properties are
satisfied by α:

• e · x = x for all x ∈ X;
• g1 · (g2 · x) = (g1 g2 ) · x for all g1 , g2 ∈ G and x ∈ X;
• given (x1 , x2 ) ∈ X × X and (y1 , y2 ) ∈ X × X with x1 ̸= x2 ,
y1 ̸= y2 , there is a g ∈ G such that g · x1 = y1 and g · x2 = y2 .
(The case xi is same as some yj for i, j = 1, 2 is allowed).

For x ∈ X, define

Gx := {g ∈ G : g · x = x}.

Prove the following:

(a) Given any pair a, b ∈ X, there is a g ∈ G such that g · a = b.
(b) Gx ̸= G for any x ∈ X.
(c) Let x ∈ X and g ∈ G \ Gx . Then G = Gx ∪ Gx g Gx .
(d) For any x ∈ X, there is no proper subgroup of G properly
containing Gx .

M18. Let R be an integral domain. For a, b ∈ R, by “a divides b” we mean

that there is an x ∈ R such that ax = b. We recall the following
definitions.
An element d ∈ R is a gcd of a, b ∈ R if:
• d divides both a and b, and
• if c ∈ R divides both a and b, then c divides d.
An element l ∈ R is an lcm of a, b ∈ R if:
• both a and b divide l, and
• if both a and b divide m ∈ R, then l divides m.
Assuming that any two elements in R have an lcm, prove the following.
(a) Any two elements in R have a gcd.
(b) Any irreducible element in R is prime.

45
 n
M19. Let G be a group of order n, H a subgroup of G of order m, k =
m
k!
and Sk the symmetric group on k symbols. Assuming < n, show
2
that G has a nontrivial proper normal subgroup.

M20. Justify whether a group of order 48 is simple or not.

M21. (a) Let R = {f : [0, 1] −→ R | f is continuous } be a ring. In R,

consider the ideal I = {f ∈ R | f ( 12 ) = 0 = f ( 13 )}. Verify whether
I is a prime ideal.
(b) Let R be a commutative ring with unity and P be a prime ideal of
R such that P does not contain any non-zero zero-divisor. Show
that R is an integral domain.
(c) Determine whether X 6 + 4X 3 + 1 is irreducible in Q[X].
(a) Let R be a commutative ring with 1 and P be a prime ideal of
R. Consider the polynomial ring R[x] and let P [x] be the ideal
of R[x] consisting of polynomials whose coefficients all belong to
P . Show that the ideal

P [x] + ⟨x⟩ := {f (x) + xg(x) : f (x) ∈ P [x], g(x) ∈ R[x]},

is a prime ideal of R[x]. [5]

(b) Let R be an integral domain and K be a subring of R. If K is
a field and the dimension of R as a vector space over K is finite,
then show that R is a field.

M22. (a) Let k be a field and α be transcendental over k. Let E(̸= k) be

a field such that
k ⊊ E ⊆ k(α).
Prove that k(α) is a finite extension of E.
(b) Let k be a field of characteristic not equal to 2. Let a, b ∈√k be
√
such that√neither a nor b is a square in k. Prove that k( a, b) =
√ √ √
k( a + b). Also show that the degree of k( a, b) over k is 2,
if ab is a square in k; and it is 4, if ab is not a square in k.

R[X]
M23. Examine whether there is a polynomial f (X) ∈ R[X] such that
(f (X))
is isomorphic as rings to the product ring C × C.

46
M24. Prove that the following two groups are isomorphic:

• Z[X], the group of polynomials with integer coefficients under

addition, and
• Q>0 , the group of positive rational numbers under multiplication.

hint: Fundamental theorem of Arithmetic

C[X, Y ]
M25. Let A = , and x, y denote the images of X, Y in A
(X 2 + Y 2 − 1)
respectively. If u = x + iy, then prove that
(a) u is a unit in A, and
(b) u − i generates a maximal ideal of A.

M26. Find all ring automorphisms of Q [X] where Q denotes the field of
rational numbers.

M27. In the additive group of rational numbers, show that the group gener-
ated by any two elements is cyclic.

M28. Give two non-isomorphic field extensions of degree 2 of the field Q of

rational numbers. Justify your answer.

M29. Let Z[X] denote the ring of polynomials in X with integer coefficients.
Find an ideal I in Z[X] such that Z[X]/I is a field of order 4.

M30. Let F be a field whose multiplicative group is cyclic. Show that there
exists a prime number p such that px = 0 for each x in F .

M31. Let G be a finite group admitting no nontrivial automorphisms. Show

that G has atmost two elements.

M32. If m and n are distinct natural numbers, then show that the abelian
groups Zm and Zn are not isomorphic.

M33. Let I be the ideal of the polynomial ring Z[X] generated by X 2 +X +1

and 5. Is the quotient ring Z[X]/I a field? Justify your answer.

47
M34. Let I be the ideal generated by X − 3 and 7 in the polynomial ring
Z[X]. Show that, for each f (X) ∈ Z[X], there exists a unique integer
a, 0 ≤ a ≤ 6, such that f (X) − a ∈ I.

M35. If G is a group of order 111 with exactly two elements of order 3 then
show that G is cyclic.

M36. A ring R is said to be of characteristic m (m a positive integer) if x +

· · ·+x(m times) = 0 for all x ∈ R. Show that any ring of characteristic
pq (p, q prime) is the direct sum of a ring of characteristic p and one
of characteristic q.

M37. Let F be an algebraically closed field of finite characteristic p. Let

q = pe , e ≥ 1. Show that x → xq is an automorphism of F into itself.
Conclude that there is a unique subfield Fq of F having q elements
and that Fq consists of the zeroes of the polynomial X q − X.

M38. Show that the additive group of complex numbers is isomorphic to the
additive group of real numbers.
(Hint : Consider these as vector spaces over an appropriate field.)

M39. Let Sn denote the group of permutations of {1, 2, 3, . . . , n} and let k

be an integer between 1 and n. Find the number of elements x in Sn
such that the cycle containing 1 in the cycle decomposition of x has
length k.

M40. Let σ be a permutation of {1, 2, 3, . . . , n}, n odd. Show that

(σ(1) − 1)(σ(2) − 2) . . . (σ(n) − n)

is even.

M41. Let φ : G → C∗ be a non-constant group homomorphism from a finite

group G to the multiplicative group of non-zero complex numbers.
Show that X
φ (g) = 0.
g∈G

48
M42. Let ψ be an automorphism of the additive group Z/77Z of the integers
mod 77. Show that ψ 60 is the identity automorphism (here ψ 60 means
the 60-fold composition of ψ with itself).

M43. Let G be a finite group. Assume that G has exactly one element a of
order 2. Then show that Y
g = a.
g∈G

M44. Let a, b be two elements of a field F with a ̸= 0. Prove that a

polynomial f (x) ∈ F [x] is irreducible if and only if the polynomial
f (ax + b) is irreducible.

M45. Let f , g be two polynomials in Z [x]. Prove that the ideal generated
by them in Z [x] contains a non-zero integer if and only if they are
relatively prime in Q [x].

M46. Show that the polynomial x3 − 2x + 3 can not be split as a product of

two non-constant polynomials in Q [x].

M47. Let f be an irreducible cubic polynomial with rational coefficients and

let K be an extension of Q of degree ten. Prove or disprove: f remains
irreducible in K [x].

M48. Determine the group of automorphisms of the permutation group S3

on 3 elements.

M49. Find the number of elements of order 6 in the permutation group S6

on six symbols.

M50. Show that the ideal generated by 2 and x in the ring Z [x] of polyno-
mials over the ring of integers cannot be generated by one element.



M51. Can the ideal I = f : [0, 1] → R, f 12 = 0 in the ring R of all
functions from [0, 1] to R be generated by one element?

49
M52. Let K be a subfield of C that is not contained in R. Show that K is
dense in C.

M53. Let g be an element of order 143 in a group G. Show that there are
unique elements g1 , g2 in G satisfying:
I. g = g1 g2 = g2 g1 ,
II. Order of g1 = 11, Order of g2 = 13.

M54. Let A be any ring without zero divisors; that is, xy = 0 implies either
x = 0 or y = 0. If a, b ∈ A satisfy am = bm , an = bn for two fixed
relatively prime natural numbers m, n prove that a = b.

M55. If F is a finite extension field of a field E and if E ⊆ R ⊆ F for some

subring R, then prove that R is also a field.

M56. Determine the additive group of the field of 4 elements.

M57. Let Q denote the field of rational numbers. Let I be the principal ideal
in the polynomial ring Q[x] generated by the polynomial f (x) = x4 −1,
i.e.,
I = {g(x)f (x)|g(x) ∈ Q[x]} .
Show that I is contained in exactly three prime ideals of Q[x].

M58. Consider the following subgroup of S4 .

B = {Id, (1, 2)(3, 4), (1, 3)(2, 4), (1, 4)(2, 3)}.

Show that B is a normal subgroup and S4 /B is isomorphic to S3 .

M59. (a) Let G be a group of order n, H a subgroup of G of order m,

n
k = and Sk the symmetric group on k symbols. Show that
m
there is a nontrivial group homomorphism φ : G → Sk . [5]
∗
(b) Let C denote the group of non-zero complex numbers under
multiplication. Show that C∗ can be expressed as a direct product
of two proper subgroups.

50
M60. Let R be a Ring with identity. Let I and J be two ideal in R. Suppose
Φ : R → R/I × R/J defined by Φ(a) = (a + I, a + J) for a ∈ R, is a
ring isomorphism. Show that I ∩ J = {0} and I + J = R.

M61. Show that if the multiplicative group of a field in cyclic, then the field
in finite.

M62. Show that every finitely generated subgroup of the additive group of
rational numbers is cyclic.

M63. If I is a maximal ideal of the polynomial ring Z[X], show that Z[X]/I
is a finite field.

M64. Let Sn be the group of all permutations of the set {1, 2, . . . , n}. Find
the number of conjugates of the n-cycle taking i to i + 1 for 1 ≤ i ≤
(n − 1) and n to 1.

M65. Let C be the field of complex numbers and ϕ : C[X, Y, Z] → C[t] be

the ring homomorphism such that

ϕ(a) = a for all a in C,

ϕ(X) = t,
ϕ(Y ) = t2 , and
ϕ(Z) = t3 .

Determine the kernel of ϕ.

√ √
M66. Show that there is no field isomorphism between Q( 2) and Q( 3).
Are they isomorphic as vector spaces over Q?

M67. Let Q, R denote the fields of rational numbers and real numbers re-
spectively. Which of the following rings are not isomorphic.
(a) Q[x]/ < x2 + 1 > and Q[x]/ < x2 + x + 1 >.
(b) R[x]/ < x2 + 1 > and R[x]/ < x2 + x + 1 >.
Justify your answer.

51
M68. Let S4 denote the group of permutations of {1, 2, 3, 4} and let H be
a subgroup of S4 of order 6. Show that there exists an element i ∈
{1, 2, 3, 4} which is fixed by each element of H.

M69. Let P (x), Q(x) be two distinct polynomials (over R) with degree of P
and Q being at most (d − 1). Let a0 , . . . , an−1 be distinct elements of
R. Prove that |{i : P (ai ) ̸= Q(ai )}| ≥ n − d + 1.

M70. Let V1 , V2 ⊆ V be two subspaces of a vector space V and b1 , b2 ∈ V .

Show that the affine subspaces W1 = V1 + b1 and W2 = V2 + b2
have a nonempty intersection if and only if π(b1 ) = π(b2 ), where
π : V → V /(V1 + V2 ) is the quotient map.

M71. Let L1 and L2 be fields, L1 ⊆ L2 , and x1 , x2 , . . . , xk ∈ Ln1 ⊆ Ln2 .

Show that x1 , x2 , . . . , xk are linearly independent in Ln1 over L1 implies
x1 , x2 , . . . , xk are linearly independent in Ln2 over L2 . (hint: Consider
the case k = n.)

M72. (a) Suppose that V is a 4-dimensional vector space over R. Let T :

V → V be an invertible linear map and W be a proper subspace
of V , such that
V = W ⊕ T W.
If T 2 W ⊆ W , then show that T 2 W = W .
(b) Suppose that A and B are two n × n real symmetric matrices and
A is also non-negative definite. Show that all eigenvalues of the
matrix AB are real.

M73. Let W = {(x1 , x2 , x3 , x4 , x5 ) ∈ R5 | x1 = x2 , x3 = x4 = x5 } be the

subspace of R5 . Find the dimension of W .
Prove that there does not exist a linear map T from R5 to R2 , such
that its null space N (T ) = W .

M74. Let A be a diagonalisable m × m matrix with entries from C. Define

X∞
An
θexp(A) = assuming A0 is the identity matrix. Prove that
n!
n=0
det (θexp(A)) = eθT r(A) .

52
M75. Let A be a real symmetric m × m matrix with m distinct eigenvalues
and v1 , . . . , vm be the corresponding eigenvectors. Let C be an m × m
matrix satisfying ⟨Cvj , vj ⟩ = 0 for 1 ≤ j ≤ m. Prove that there exists
an m × m matrix X such that AX − XA = C.

M76. Let u = (u1 , u2 , . . . , un ) be a fixed non-zero vector in Rn such that

u1 + u2 + · · · + un = 0, and let A be the n! × n matrix whose rows are
the n! permutations of u. Show that rank(A) = n − 1.

M77. Let u = (u1 , u2 , . . . , un )T be a non-zero column vector in Cn , and u∗ be

the row vector (ū1 , ū2 , . . . , ūn ). Let A = uu∗ . Find all the eigenvalues
of A and identify the corresponding eigen subspaces.

M78. Let A = ((aij )) be an n × n complex matrix. For 1 ≤ k ≤ n, let

X
n
Dk ⊆ C be the closed disc with center akk and radius |ajk |. If λ is
j=1
j̸=k
any eigenvalue of A, then show that λ ∈ Dk for at least one k.
(hint: If x is an eigenvector corresponding to the eigenvalue λ, look at the co-
ordinate position k for which |xk | is largest.)

M79. Let Rn denote the n dimensional real vector space. Let A, B be two
linear transformations on Rn such that A ◦ A = A and B ◦ B = B,
where ◦ stands for composition of linear transformations. Show that
the ranges of A − A ◦ B and B − A ◦ B have only the zero vector in
common.

M80. Let V be the real vector space consisting of continuous real valued
functions on R. Show that the subset {sin x, cos x, ex } of V is linearly
independent.

M81. Let L and T be two linear transformations from a real vector space
V to R such that L (v) = 0 implies T (v) = 0. Show that T = cL for
some real number c.

53
M82. Let x1 , x2 , x3 , x4 be vectors in Rn such that the inner products ⟨xi , xj ⟩,
i ̸= j, are strictly negative. Show that any three of the vectors
x1 , x2 , x3 , x4 are linearly independent.

M83. Let A be an n×n square matrix such that A2 is the identity. Show that
any n × 1 vector can be expressed as a sum of atmost two eigenvectors
of A.

M84. Let A be an m × n matrix of rank 1 and G be an n × m matrix such

that AGA = A. Show that the trace of AG is 1.

M85. Let  
0 1 0 0
 
 0 0 1 0 
B=

.

 0 0 0 1 
0 0 0 0
Show that, for each nonzero scalar λ, (λI − B)−1 = Pλ (B) for some
polynomial Pλ (X) of degree 3.

M86. Let C be an invertible, real matrix of order n. If each row sum of C

is 1, then show that each row sum of C −1 also is 1.

M87. Let x and y be non-zero vectors in an inner product space over the
field of real numbers. Then ∥x + y∥ = ∥x∥ + ∥y∥ if and only if x = αy
for some positive real number α.

M88. Suppose that A is a 2 × 2 matrix over reals such that An = I for some
integer n. Show that trace of A is atmost 2.

M89. Find an n × n matrix over real numbers whose minimal polynomial is

xn−1 .

M90. If A is a matrix with real entries such that A2 = A show that A is

diagonalisable over R.

54
M91. If A is an n × n upper triangular matrix with all diagonal entries 1,
find the inverse of A as a polynomial in A.

M92. Let V1 , V2 , V3 be three-dimensional subspaces of R4 . Show that V1 ∩

V2 ∩ V3 contains a non-zero vector.

M93. Let A = (aij )1≤i,j≤n be a n × n matrix with



 1 if i = 1, j = 2,

aij =
 1 if i = j,

 0 otherwise.

Prove that A is not a diagonalizable matrix over C.

M94. Let M2 be the space of all 2 × 2 complex matrices. Take

" #
1 0
P = and N = {X ∈ M2 : P X = XP }.
0 0

Show that if A, B are in N then AB = BA.

M95. Let D be a n × n real, diagonal matrix. Show that there exists a

x ∈ Rn such that

span {Dk x : 0 ≤ k ≤ n − 1} = Rn

if and only if the eigen-values of D are distinct.

M96. Let A and B be n × n, Hermitian matrices such that AB = BA.

Suppose one of them has distinct eigenvalues. Show that A and B
have a common eigenvector.

M97. Let A be an m × n real matrix with rank r and nullity k. Let V, W be

the vector spaces of all real n × p, m × p matrices, respectively. Define
LA : V → W by LA (X) = AX(left multiplication by A). Compute
the rank and nullity of LA .

55
 M98. Let B, C be two invertible n × n complex matrices such that BC =
qCB for some complex number q. Show that q m = 1 for some m ≥ 1.
(Hint: Consider the eigenvalues of BC and CB.)

M99. Let A be an n × n complex matrix such that AX = XA for every

invertible complex matrix X. Show that A = λI for some complex
number λ.

M100. Let A and X be invertible complex matrices such that XAX −1 = A2 .

Prove that there exists a natural number m such that each eigenvalue
of A is an m-th root of unity.

M101. Let A0 , A1 be n × n complex matrices which may not commute. Let

2πi
m ≥ 2 and ω = e m . Show that

m(Am m m m 2 m
0 + A1 ) = (A0 + A1 ) + (A0 + ωA1 ) + (A0 + ω A1 ) +
· · · + (A0 + ω m−1 A1 )m .

M102. Let A and!B be n × n matrices with real entries. Show that the matrix
A I
has rank n if and only if A is nonsingular and B = A−1 .
I B

M103. Let n be a positive odd integer and let A be a symmetric n × n matrix

of integer entries such that aii = 0, i = 1, 2, . . . , n. Show that the
determinant of A is even.

M104. Suppose A, B, C are three n × n matrices such that A has n distinct

eigenvalues. If AB = BA and AC = CA, prove that BC = CB.

M105. Find a maximal linearly independent set in the following subset C of

Rk+1 : n  o
C= 1, t, t2 , . . . , tk ∈ Rk+1 | t ∈ R .

M106. Let A be a square matrix such that Ak = 0 for some k > 0. Prove
that there exists an invertible matrix B such that BAB −1 is upper
triangular with diagonal entries zero.

56
M107. Let A be an n × n integer matrix whose columns are pairwise distinct.
Show that there is a row in A, whose removal results in an (n − 1) × n
matrix with the same property.

M108. Let Sn denote the group of all permutations of {1, 2, . . . , n}. For any
σ ∈ Sn , denote by Pσ the linear transformation on Rn given by
   
x1 xσ−1 (1)
   
 x2   
Pσ  = 
x σ (2) 
−1

 ..   .. 
 .   . 
xn xσ−1 (n)

where σ −1 denotes the inverse of σ. Show that the correspondence

σ → Pσ is a homomorphism from the group Sn into the group of all
n × n orthogonal
X matrices. If (σ) denotes the signature (sign) of σ,
show that (σ)Pσ = 0 for n ≥ 3.
σ∈Sn

M109. Prove that the space [0, 1] is not homeomorphic to a product X × Y

for two subsets X and Y of R, where neither X nor Y is a single point.

M110. (a) Show that a connected subset of a metric space is either a single-
ton or uncountable.
(b) Let A be a connected subset of a connected topological space X.
Suppose that B is a clopen (closed and open) subset of X \ A in
the subspace topology of X \ A. Prove that A ∪ B is connected.

M111. (a) Suppose A and B are closed subsets of a topological space such
that A ∩ B and A ∪ B are connected. Prove that A and B are
connected.
(b) Demonstrate that the conclusion may not hold if the assumption
of A and B being closed subsets, is dropped.

57
M112. Let L1 be the line y = 1, L−1 be the line y = −1, and for every n ≥ 1,
Rn be the rectangle



Rn = {−n, n} × [−1 + n1 , 1 − n1 ] ∪ [−n, n] × {−1 + n1 , 1 − n1 } .

Define [ 
X = L1 ∪ L−1 ∪ Rn ,
n≥1

which is equipped with the subspace topology from R2 (see the figure
below).

y
L1

R1 R2 · · · Rn x

L−1

(a) Find the connected components of X.

(b) Find points a, b ∈ X in different connected components of X such
that there is no disconnection of X = A∪B with a ∈ A and b ∈ B.
[X = A ∪ B is a disconnection means A and B are disjoint open
sets.]
Justify your answers in (a) and (b).

M113. Prove that there cannot be any topological space X such that R is
homeomorphic to X × X with the product topology.

58
M114. Let (X, d) be a compact metric space, and f : X → X a function such
that
d(f (x), f (y)) < d(x, y) for all x, y ∈ X, x ̸= y.
(a) Show that g(x) = d(x, f (x)) is a continuous function on X.
(b) Show that there is a point x0 ∈ X such that f (x0 ) = x0 .

M115. Let (X, d) be a metric space. Assume that X is countable and has at
least two points. Show that X is not connected.

M116. Let  > 0 be a real number. Let d denote the Euclidean metric on Rn ,
the n dimensional real vector space. Show that there cannot exist an
uncountable subset S of Rn such that d (s, t) >  for all s ̸= t in S.

M117. Give an example of a metric space X, a continuous real valued function

f on X, and a Cauchy sequence (xn ) in X such that (f (xn )) is not
Cauchy.

M118. Let A be a closed subset of the real numbers R with respect to its
usual metric topology. Prove that there exists a countable subset of A
whose closure is A.

M119. On the open interval I = (3, 4) define a function f as

1
f (x) = .
min(|x − 3|, |x − 4|)

Define d(x, y) = |x − y| + |f (x) − f (y)| for x, y ∈ I.

(a) Show that d is a metric.
(b) Show that (I, d) is a complete metric space.

M120. Let f be a continuous map from a topological space X into a Hausdorff

space Y . Prove that the graph {(x, f (x)) : x ∈ X} of f is a closed
subset of the product space X × Y .

M121. Let X be a compact Hausdorff space. Assume that the vector space
of real-valued continuous functions on X is finite dimensional. Show
that X is finite.

59
M122. Let X be a metric space. Assume that, for each positive real number
r, the closure of each open ball of radius r is compact. Show that X
is complete.

M123. Let (X, d) be a complete metric space, A1 ⊇ A2 ⊇ . . . be a sequence

of closed sets in X such that sup{d(x, y) : x, y ∈ An } tends to zero as
n tends to infinity. Let f : X → X be a continuous map. Show that
\ \
f ( An ) = f (An ).
n n

M124. Let X be a compact metric space. Let f : X → R, g : X → R be

continuous functions such that f (x) ̸= g (x) for all x ∈ X. Show that

inf |f (x) − g (x) | > 0.

x

M125. Let X and Y be topological spaces. Consider the following statement:

If X is homeomorphic to a subspace of Y and Y is homeomorphic to
a subspace of X then X and Y are homeomorphic.
Is this statement true? Justify your answer.

M126. Let X be a metric space and A, B be disjoint closed subsets of X. If

A is compact, show that there exists  > 0 such that d(a, b) ≥  for all
a ∈ A, b ∈ B.

M127. Let X be an infinite set and let {dn }n≥1 be a sequence of metrics on
X such that dn (x, y) ≤ 1 for all x, y ∈ X and for all n ≥ 1. Show that
∞
X dn (x, y)
d(x, y) =
2n
n=1

for x, y ∈ X is a metric on X.

M128. Let X = [0, ∞). Define a metric d on X such that d(x, y) ≤ 1 for
all x, y ∈ X and such that the topology induced by d is same as the
relative real line topology on X.

60
M129. Let X = R\{0} be equipped with the relative real line topology and
let Y denote the curve Y = {(x, y) ∈ R2 : xy = 1} with the subspace
topology of the usual Euclidean topology on R2 . Prove that X is
homeomorphic to Y .

M130. Let (X, d) be a metric space and K ⊂ X be aTcompact set. Suppose

that, for every proper open subset U of X, U K is countable. Show
that K is countable.

M131. Show that R with the metric d defined by :

1 1
d(x, y) = | 2
− |
1+x 1 + y2
is not a complete metric space.

M132. Let
X = {{αn }n≥1 : αn ∈ R, lim αn = 0, sup |αn | ≤ 1}.
n→∞ n

Define a metric on X by

d({αn }n≥1 , {βn }n≥1 ) = sup |αn − βn |.

n

Show that (X, d) is not a compact metric space.

M133. Let X be a Hausdorff space. Let f : X → R be such that {(x, f (x)) :

x ∈ X} is a compact subset of X × R. Show that f is continuous.

M134. Show that the set of all rational numbers with the usual topology is
not locally compact.

M135. The cofinite topology on R is the topology in which a subset F ⊆ R is

closed if and only if F is either finite or F = R. Let X = R with the
cofinite topology and Y = R with the usual topology. Show that any
continuous map f : X −→ Y is a constant.

M136. Let f : (0, 1) → R be a continuous function. Show that the graph

G = {(x, f (x)) : x ∈ (0, 1)} of f is a non-compact subset of R2 .

61
M137. Show that the complement of a non-empty compact subset of R is not
connected.

M138. If A is a dense open subset of R, show that R = {x − y : x, y ∈ A}.

M139. Consider the set

A = {(x, y) ∈ R2 : either x ̸∈ Q, or y ̸∈ Q}.

Show that A is path-connected.

M140. Let A = {(x, y) ∈ R2 | max{|x|, |y|} ≤ 1} and B = {(0, y) ∈ R2 | y ∈

R}. Show that the set A + B = {a + b | a ∈ A, b ∈ B} is a closed
subset of R2 .

M141. Let
C = {(x, y) ∈ R2 | x3 = y 2 }.
Prove that R with its usual topology is homeomorphic to C with its
subspace topology induced from R2 .

M142. Let X be a Hausdorff space. Let f : X → R be such that {(x, f (x)) :

x ∈ X} is a compact subset of X × R. Show that f is continuous.

M143. Let f, g : X → Y be continuous functions between topological spaces

X and Y. Assume that Y is Hausdorff. Let

E = {x ∈ X|f (x) = g(x)}.

Prove that E is a closed set.

62