CMI 2021
Question 1 
If the milkman doesn’t deliver milk or the geyser doesn’t work, then Akash will be
late for school and lunch will be cooked late. Suppose lunch was actually cooked on
time. Which of the following is definitely true?
Akash was late for school  
Akash reached school in time  
Geyser worked  
Milkman did not deliver milk 
Question 1 Explanation:
If either the milkman doesn’t deliver milk or the geyser doesn’t work, then (in partic
ular) lunch will be cooked late. But lunch was actually cooked on time. So it follows
that the milkman delivered on time and the geyser actually worked. So option (c) is
definitely true, and option (d) is definitely false. Akash can either be a dutiful student
and reach school on time, or be lazy and not go to school on time. So neither (a) nor
(b) can be asserted for certain.
Question 2 
Let L be the language over {a, b} that contains the same number of occurrences of a
and b. Which of the following languages is regular?
L ∩ a∗b  
(L ∩ a∗b∗) ∪ a∗b  
L ∪ a∗b  
(L ∩ a∗b∗) ∪ b∗a 
Question 2 Explanation:
(L ∩ a
∗
b
∗
) ∪ b
∗a
∗
Answer: (b) (L ∩ a
∗
b
∗
) ∪ a
∗
b
∗
(a) L ∩ a
∗
b
∗ = {a
n
b
n
 n ≥ 0} is not a regular language.
(b) (L ∩ a
∗
b
∗
) ∪ a
∗
b
∗ = {a
mb
n
 m, n ≥ 0} is a regular language.
(c) If L3 = L ∪ a
∗
b
∗ were regular, then L3 ∩ b
∗a
∗ would also be regular. But L3 ∩ b
∗a
∗
is {b
na
n
 n ≥ 0}, which is not regular.
(d) If L4 = (L ∩ a
∗
b
∗
) ∪ b
∗a
∗ were regular, then L4 ∩ a
∗
b
∗ would also be regular. But
L4 ∩ a
∗
b
∗
is {a
n
b
n
 n ≥ 0}, which is not regular.
Question 3 
Which of the following regular expressions represents binary strings that are multiples
of 3? Note that we consider the leftmost bit to be the most significant.
((11)0∗)∗  
1(01∗)∗  
(10∗)∗  
(11 + 101∗01 + 0)∗ 
Question 3 Explanation:
Let L(r) denote the language represented by the regular expression r.
(a) It can be checked that L(((11)0∗
)
∗
) does not contain the string 1001, which rep
resents 9.
(b) L((10∗
)
∗
) contains 1, which represents a nonmultiple of 3.
(c) L(1(01∗
)
∗
) contains 101 (representing 5), as also 1 (representing 1).
(d) This is the only remaining option. One can prove it by first constructing a DFA
for binary strings that are multiples of 3, and converting it to a regular expression.
Question 4 
Consider the following statements about finite simple graphs G:
(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a
subgraph.
(ii)If the number of edges of a graph G is at least as large as the number of its
vertices, then G contains a cycle as a subgraph.
Which of the above two statements holds for all graphs?
(i) only  
(ii) only  
both (i) and (ii)  
neither of them 
Question 4 Explanation:
(i) Let P = ⟨v1, v2, . . . , vt⟩ be a maximal path in G. Since vt has degree at least 2
in G, there is an edge {vt
, x} in G which is different from the edge incident on
vt
in the path P. Since P is a maximal path the vertex x must belong to P. So
x = vi
for some 1 ≤ i < (t − 1). The path ⟨vi
, v(i+1), . . . , vt⟩ together with the
edge {vt
, vi} forms a cycle in G.
(ii) Suppose not, and let H be a graph with the smallest number of vertices which
contradicts the statement. That is, H has at least as many edges as vertices,
and does not contain a cycle. From the solution to part (a) above we get that
there must be a vertex v in H whose degree is at most one. Deleting v from
H results in a graph H′ with (i) one fewer vertex, and (ii) at most one fewer
edge, so H′ also satisfies the premise of the statement. But then H′ does not
have any cycle, because H did not have any by assumption. Thus H′
is a graph
with fewer vertices than H for which the statement holds, which contradicts our
assumption about H. Hence proved.
Question 5 
One day, Dumbledore assigns Harry Potter the task of obtaining the Philosopher’s
Stone that lies in an inner chamber surrounded by many rooms. To guide him along,
he is given the Marauder’s Map which contains the following graph.
Harry wishes to color every wall with colors such that walls that meet at a corner
get different colors. Harry also wishes to color every room so that adjacent rooms get
different colors. What is the minimum number of colors to accomplish this?
4 colors for walls and 4 colors for the rooms  
3 colors for walls and 4 colors for the rooms  
2 colors for walls and 3 colors for the rooms  
2 colors for walls and 5 colors for the rooms 
Question 5 Explanation:
Consider the undirected graph G where every vertex corresponds to a wall and there
is a edge between two vertices whenever two walls are incident on (or adjacent to)
each other. Now, coloring for walls is the same as coloring the vertices of G such that
no two adjacent vertices get the same color. This can be done with 3 colors and the
graph G is often called the line graph (of the image given above).
Consider the undirected graph G′ where every region(polygon in the above image)
is a vertex and there is an edge between two vertices whenever the regions share a
boundary. Now, coloring the rooms is the same as coloring the vertices of G′
such
that no two adjacent vertices get the same color. This can be done using 4 colors.
Interestingly, note that you can draw G′ on paper (or a plane) such that no two
edges cross each other. Such a graph is said to be a planar graph. The question is a
rephrasing of the Planar 4Color Theorem.
Question 6 
In the chamber containing the Philosopher’s stone, Harry sees a deck of 5 cards, each
with a distinct number from 1 to 5. Harry removes two cards from the deck, one at
time. What is the probability that the two cards selected are such that the first card’s
number is exactly one more than the number on the second card?
1/5  
4/25  
1/4  
2/5 
Question 6 Explanation:
Letting (i, j) be the event that card i was drawn first and then card j, the
Question 7 
You are given a sequence of letters x1x2 . . . xn where each xi ∈ {a, b, c, d, e, f, g, h}.
You can form a new sequence from the given sequence as follows. Start with x1. Place
xm+1 either to the left or to the right of the sequence already built from x1x2 . . . xm.
For instance, from dcbeb you can form ecdbb through the steps d → cd → cdb →
ecdb → ecdbb and bbcde through the steps d → cd → bcd → bcde → bbcde.
What is the largest sequence in lexicographic (dictionary) order that you can form
from the input sequence becgdfg?
ggebcdf  
ggfedcb  
ggecbdf  
ggfebcd 
Question 7 Explanation:
We can generate ggebcdf through the sequence b, eb, ebc, gebc, gebcd, gebcdf , ggebcdf .
We cannot generate ggfedcb, since after the first g, d and f have to come to its right
in the same order. We cannot generate ggecbdf , because it is not possible to generate
ecb from {b, e, c}. We cannot generate ggfebcd, since after the first g, d and f have to
come to its right in the same order.
Question 8 
There is a basket full of apples, oranges, mangoes, pears and pomegranates. You want
to pick three fruits from the basket. Multiple pieces of the same fruit can be picked.
However, if you pick mangoes, you cannot pick apples.
In how many ways can you pick three fruits satisfying this condition?
14  
30  
28  
20 
Question 8 Explanation:
There are the 35 different ways to pick three fruits from five kinds of fruits:
• all three fruits are of the same kind (5 ways).
• two are of one kind and the third is different (5 × 4 = 20 ways).
• each fruit is of a different kind ((
5
3
)
= 10 ways).
Of these, we should avoid the following 5 choices (letting M, A, P, G, O represent
mango, apple, pear, pomegranata and orange respectively):
MMA MAA MP A MGA MOA
Thus the final answer is 30. ⊣
The next two questions refer to the following procedure.
The procedure operates on three arrays A[0..99], B[0..99] and C[0..99], which are
initialized with integer values.
4
procedure mystery() {
for (i = 0; i < 100; i++) { C[i] = A[i]; }
p = 99;
for (i = 0; i < 100; i++) {
B[p] = C[0];
p = p1;
for (j = 1; j < 100; j++) {
C[j1] = C[j];
}
}
}
Question 9 
When the procedure terminates, which of the following statements can be asserted
about the array B?
All elements of B are equal to A[0]  
B contains the elements of A sorted in descending order  
All values of B are the same  
B contains the elements of A in reverse order 
Question 9 Explanation:
We copy A into C to begin with. In each iteration of the outer for loop, we place
the first element of C at position p of B. Since we decrement p in each iteration, we
are essentially placing the elements in positions 99, 98, ..., 0 of B, in order. At each
iteration, we shift C left by one place, so what was C[i+1] in the previous iteration
is C[i] in the current iteration. So essentially we are copying A[0], A[1], . . . , A[99]
into B[99], B[98], . . . , B[0].
Question 10 
When the procedure terminates, which of the following statements can be asserted
about the array C?
It contains the elements of A sorted in ascending order  
It contains the elements of A sorted in descending order  
All values are equal to A[99]  
All values are equal to A[0] 
Question 10 Explanation:
As explained above, each iteration of the outer loop shifts C to the left by one place.
At the end of iteration i, C[99], which is the same as A[99], is copied to positions
99i, 99i+1, . . . , 99 of C. Since the outer loop is run for 100 iterations, the result
follows.
Question 11 
Let A = (√3 + √2)1000, B = (√3 −√2)1000. Prove the following statements.
A + B is an integer.  
The digit immediately after the decimal point in B is 0.  
The digit immediately after the decimal point in A is 9.  
Both A, B are irrational. 
Question 11 Explanation:
(a) A+B is an integer, because for odd i, the (
1000
i
)
terms in A and B cancel out, and
for even i, the (
1000
i
)
terms in both A and B are of the form (
1000
i
)
(
√
3)i
(
√
2)1000−i
,
which is an integer (since both i and 1000 − i are even).
(b) √
3 −
√
2 < 0.318, and (
√
3 −
√
2)6 < 0.0011. So the first two digits after the
decimal in B are 0.
(c) The above fact forces the first digit after the decimal in A to be 9, since A + B is
an integer.
(d) A and B are both irrational, since we
Question 12 
Imagine you are playing a computer game that consists of different types of coins.
You have the power to cast two magic spells s1 and s2. Each spell consumes some
number of coins of each type and produces some number of coins of each type. Spell
s1 consumes one coin of type t1 and produces two coins of type t2, written in short as
(−1 t1, +2 t2). Spell s2 is (−1 t2, +1 t1). You are allowed to cast the two spells any
number of times, but a spell cannot be cast if there aren’t enough coins present for
consumption. For example, s2 cannot be cast if there are 0 coins of type t2.
Suppose you start with n coins of type t1 and 0 coins of type t2. If you repeatedly
cast spell s1 till it can no longer be cast, what is the total number of coins (of
both types) at the end?  
Suppose you start with n coins of type t1 and 0 coins of type t2. You are allowed
to cast both the spells s1 and s2. Give a sequence of spells that will lead you to
4n total coins. Can you extend the sequence to produce more than 4n coins?  
Suppose we provide you with a third type of coin t3, and you start with n coins
of type t1 and 0 coins of types t2 and t3. Come up with a new spell s3 satisfying
the following three properties:Suppose we provide you with a third type of coin t3, and you start with n coins
of type t1 and 0 coins of types t2 and t3. Come up with a new spell s3 satisfying
the following three properties:Suppose we provide you with a third type of coin t3, and you start with n coins
of type t1 and 0 coins of types t2 and t3. Come up with a new spell s3 satisfying
the following three properties Suppose we provide you with a third type of coin t3, and you start with n coins
of type t1 and 0 coins of types t2 and t3. Come up with a new spell s3 satisfying
the following three properties:  
Question 13 
A cut edge of a connected graph G is any edge e = {u, v} of G such that the graph
G − e obtained by deleting edge e (and not deleting u or v) is disconnected. In fact,
G−e will have exactly two connected components. Let G be an arbitrary finite simple
connected graph in which every vertex has an odd degree, and let e be an arbitrary
cut edge of G. Let H1, H2 be the two connected components of G − e.
Prove or disprove the following statement: Each of H1, H2 must necessarily have an
odd number of vertices.
To disprove this statement it suffices to exhibit a graph which contradicts the state
ment. A proof must take the form of an argument.
The sum of the degrees of any graph is twice the number of its edges. So the number
of vertices of odd degree in any graph is even. It follows that G has an even number
of vertices. So the counts of vertices of H1, H2 are either both odd, or both even. Each
of H1, H2 has exactly one vertex of even degree: this is the erstwhile endpoint of the
edge e which ends up in that graph. If the vertex count of H1 is even, then this means
that H1 has an odd number of vertices of odd degree, which is impossible. Similarly
for H2. So each of H1, H2 has an odd number of vertices. 
Question 14 
For a language L over an alphabet Σ, define
SW(L) := { y ∈ Σ∗ ∃x ∈ Σ∗s.t. xyx ∈ L}
Prove that if L is regular, SW(L) is also regular.
Suppose L is regular, and let A be an automaton recognizing L. Nondeterministically
pick a state q. Run A on a guessed string x from the start state s as well as from q.
At any point if the simulation from q reaches a final state and the first component
is at some state p you may nondeterministically move to a phase which checks if the
input word y can take you from p to q.
Formally, if A is given by (Q, s, →, F), with t ̸∈ Q, we define B (an NFA with ε
transitions) recognizing SW(L) to be B = (Q′
, s′
, ⇒, F′
) where:
• Q′ = {(p, q, r)  p ∈ S ∪ {t}, q, r ∈ S}
• s
′ = {(t, q, q)  q ∈ S}
• (p, q, r)
a=⇒ (p
′
, q′
, r′
) iff one of the following conditions holds:
– p = p
′ = t, q = q
′ and r
a−→ r
′
(this is the phase that runs on y);
– p = t, p
′ = q, q
′ = s, r
′ = r and a = ε (this is the phase change);
– p ̸= t, p
′ = p, a = ε and for some b ∈ Σ, q
b
−→ q
′ and r
b
−→ r
′
(this is the phase
that checks that there are appropriate runs on a guessed x).

Question 14 Explanation:
Suppose L is regular, and let A be an automaton recognizing L. Nondeterministically
pick a state q. Run A on a guessed string x from the start state s as well as from q.
At any point if the simulation from q reaches a final state and the first component
is at some state p you may nondeterministically move to a phase which checks if the
input word y can take you from p to q.
Formally, if A is given by (Q, s, →, F), with t ̸∈ Q, we define B (an NFA with ε
transitions) recognizing SW(L) to be B = (Q′
, s′
, ⇒, F′
) where:
• Q′ = {(p, q, r)  p ∈ S ∪ {t}, q, r ∈ S}
• s
′ = {(t, q, q)  q ∈ S}
• (p, q, r)
a=⇒ (p
′
, q′
, r′
) iff one of the following conditions holds:
– p = p
′ = t, q = q
′ and r
a−→ r
′
(this is the phase that runs on y);
– p = t, p
′ = q, q
′ = s, r
′ = r and a = ε (this is the phase change);
– p ̸= t, p
′ = p, a = ε and for some b ∈ Σ, q
b
−→ q
′ and r
b
−→ r
′
(this is the phase
that checks that there are appropriate runs on a guessed x).
• F
′ = {(q, q, f)  q ∈ S, f ∈ F}.
Any accepting run of B on y is of the following form:
(t, p, p)
y
=⇒ (t, p, q)
ε=⇒ (p, s, q)
∗=⇒ (p, p, f).
Furthermore, the run before the phase shift is witnessed by an Arun on y (from p to
q), and the run after the phase shift is witnessed by two Aruns on the same string
(say x), one from s to p, and another from q to f. Thus there is an accepting Brun
on y iff there is an accepting Arun on xyx, for some x.
Question 15 
Given a list A of N elements and a number K, your task is to output the N − K + 1
values listing the minimum among A[i] · · · A[i + K − 1] for every 1 ≤ i ≤ N − K + 1.
Provide an algorithm for this task, that runs in time at most O(N log K).
Let M[i][j] denote the minimum among A[i] · · · A[i + 2j − 1], for j ≤ K and 1 ≤
i ≤ N − 2
j + 1. Our aim is to compute M[i][K] for 1 ≤ i ≤ N − K + 1. Observe
that M[i][j + 1] = min (M[i][j], M[i + 2j
][j]). This suggests the following dynamic
programming algorithm.
for (i = 1; i <= N; i++) {
M[i][0] = A[i];
}
s = 1; l = log(K);
8
for (j = 1; j <= l; j++) {
for (i = 1; i <= N2*s+1; i++) {
M[i][j] = min(M[i][j1], M[i+s][j1]);
}
s = 2*s;
}
output M[1][log(K)], M[2][log(K)], ..., M[NK+1][log(K)];
The inner loop runs in time O(N), and there are log K iterations of the outer loop.
So we have the desired running time. 
Question 15 Explanation:
Let M[i][j] denote the minimum among A[i] · · · A[i + 2j − 1], for j ≤ K and 1 ≤
i ≤ N − 2
j + 1. Our aim is to compute M[i][K] for 1 ≤ i ≤ N − K + 1. Observe
that M[i][j + 1] = min (M[i][j], M[i + 2j
][j]). This suggests the following dynamic
programming algorithm.
for (i = 1; i <= N; i++) {
M[i][0] = A[i];
}
s = 1; l = log(K);
8
for (j = 1; j <= l; j++) {
for (i = 1; i <= N2*s+1; i++) {
M[i][j] = min(M[i][j1], M[i+s][j1]);
}
s = 2*s;
}
output M[1][log(K)], M[2][log(K)], ..., M[NK+1][log(K)];
The inner loop runs in time O(N), and there are log K iterations of the outer loop.
So we have the desired running time.
Question 16 
Let A = A[1]A[2] · · · A[n] be an array of n numbers where n = 2k − 1 for some k > 0.
Consider a binary tree T built from the array in the following manner. The root of
T is the middle element of A. Let AL and AR denote the left and right subarrays
resulting from the removal of the middle element from A. The left and right subtrees
of the root node are binary trees defined similarly on AL and AR, respectively.
Each element A[i] of the array is a node in this tree T. Let Si denote the indices
occurring in the unique path from the root node to the element A[i]. We say that
index i is good if for every j1, j2 in Si with j1 < j2, we have A[j1] ≤ A[j2].
Prove that the subarray A[i1]A[i2] · · · A[im] consisting only of good indices is sorted.
Consider any two good indices i and j, with i < j. Let A[k] be the lowest common
ancestor of A[i] and A[j] in the tree T (it is possible that k ∈ {i, j}). Clearly i ≤ k ≤ j.
Now i, k ∈ Si and j, k ∈ Sj
, and both i and j are good. Therefore A[i] ≤ A[k] and
A[k] ≤ A[j], and hence A[i] ≤ A[j]. The desired result follows. 
Question 16 Explanation:
Consider any two good indices i and j, with i < j. Let A[k] be the lowest common
ancestor of A[i] and A[j] in the tree T (it is possible that k ∈ {i, j}). Clearly i ≤ k ≤ j.
Now i, k ∈ Si and j, k ∈ Sj
, and both i and j are good. Therefore A[i] ≤ A[k] and
A[k] ≤ A[j], and hence A[i] ≤ A[j]. The desired result follows.
Question 17 
Consider the functions foo and bar described in pseudocode below, where // denotes
quotient (integer division) and % denotes remainder.
int foo(int n) {
int i = 1;
while (bar(i) < n) {
i = 2*i;
}
return(i);
}
int bar(int n) {
if (n == 0) {
return(1);
}
int x = bar(n // 2);
if (n % 2 == 0) {
return(x*x);
} else {
return(2*x*x);
9
}
}
(a) What function does bar(n) compute? Justify your answer.
(b) If foo(n) computes x, how do n and x relate to each other. Justify your answer.
(c) How many recursive calls to bar are made in a computation of foo(100)?
bar(n) computes 2
n
. This can be shown easily by induction. The base case, when
n = 0, returns 1. Otherwise, if n = 2m, we compute 2
m · 2
m = (2m)
2 = 22m = 2n
,
and if n = 2m + 1, we compute 2 · 2
m · 2
m = 2(2m)
2 = 22m+1 = 2n
.  
In foo(n), we are repeatedly computing 2
1
, 2
2
, 2
4
, 2
8
, . . . till we reach x such that
2
x ≥ n. So the x computed by foo(n) is the smallest number m such that m is a
power of 2 and 2
m ≥ n.  
In foo(100), there are recursive calls to bar(1), bar(2), bar(4) and bar(8). We
stop with this since 2
8 ≥ 100. Now, bar(2^(i)) has i + 1 further calls to bar. So
overall we have a total of 2 + 3 + 4 + 5 = 14 calls to bar. 
Question 17 Explanation:
(a) bar(n) computes 2
n
. This can be shown easily by induction. The base case, when
n = 0, returns 1. Otherwise, if n = 2m, we compute 2
m · 2
m = (2m)
2 = 22m = 2n
,
and if n = 2m + 1, we compute 2 · 2
m · 2
m = 2(2m)
2 = 22m+1 = 2n
.
(b) In foo(n), we are repeatedly computing 2
1
, 2
2
, 2
4
, 2
8
, . . . till we reach x such that
2
x ≥ n. So the x computed by foo(n) is the smallest number m such that m is a
power of 2 and 2
m ≥ n.
(c) In foo(100), there are recursive calls to bar(1), bar(2), bar(4) and bar(8). We
stop with this since 2
8 ≥ 100. Now, bar(2^(i)) has i + 1 further calls to bar. So
overall we have a total of 2 + 3 + 4 + 5 = 14 calls to bar.
There are 17 questions to complete.