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?
A
Akash was late for school
B
Akash reached school in time
C
Geyser worked
D
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?
A
L ∩ a∗b
B
(L ∩ a∗b∗) ∪ a∗b
C
L ∪ a∗b
D
(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.
A
((11)0∗)∗
B
1(01∗)∗
C
(10∗)∗
D
(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 non-multiple 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?
A
(i) only
B
(ii) only
C
both (i) and (ii)
D
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?
A
4 colors for walls and 4 colors for the rooms
B
3 colors for walls and 4 colors for the rooms
C
2 colors for walls and 3 colors for the rooms
D
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 4-Color 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?
A
1/5
B
4/25
C
1/4
D
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?
A
ggebcdf
B
ggfedcb
C
ggecbdf
D
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?
A
14
B
30
C
28
D
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 = p-1; for (j = 1; j < 100; j++) { C[j-1] = C[j]; } } }
Question 9
When the procedure terminates, which of the following statements can be asserted about the array B?
A
All elements of B are equal to A[0]
B
B contains the elements of A sorted in descending order
C
All values of B are the same
D
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?
A
It contains the elements of A sorted in ascending order
B
It contains the elements of A sorted in descending order
C
All values are equal to A[99]
D
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 99-i, 99-i+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
A + B is an integer.
B
The digit immediately after the decimal point in B is 0.
C
The digit immediately after the decimal point in A is 9.
D
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.
A
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?
B
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?
C
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:
D
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.
A
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 end-point 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.
A
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 A-run on y (from p to q), and the run after the phase shift is witnessed by two A-runs on the same string (say x), one from s to p, and another from q to f. Thus there is an accepting B-run on y iff there is an accepting A-run 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).
A
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 <= N-2*s+1; i++) { M[i][j] = min(M[i][j-1], M[i+s][j-1]); } s = 2*s; } output M[1][log(K)], M[2][log(K)], ..., M[N-K+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 <= N-2*s+1; i++) { M[i][j] = min(M[i][j-1], M[i+s][j-1]); } s = 2*s; } output M[1][log(K)], M[2][log(K)], ..., M[N-K+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.
A
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)?
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.
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.