CMI 2020

Question 1
Which of the following languages over the alphabet {0, 1} are not recognized by de-terministic finite state automata (DFA) with three states?
A
Words which do not have 11 as a contiguous subword
B
Binary representations of multiples of three
C
Words that have 11 as a suffix
D
Words that do not contain 101 as a contiguous subword
Question 1 Explanation: 
For (a), the automaton has states {q0, q1, q2} with q0 as start state, q0 and q1 as accept states, and transition function given below: 0 1 q0 q0 q1 q1 q0 q2 q2 q2 q2 For (b), the automaton has states {q0, q1, q2} with q0 as start and accept state, and transition function given below: 0 1 q0 q0 q1 q1 q2 q0 q2 q1 q2 For (c), the automaton has states {q0, q1, q2} with q0 as start state, q2 as accept state, and transition function given below: 0 1 q0 q0 q1 q1 q0 q2 q2 q0 q2 For (d), an automaton with three states is not possible, since we need at least four states to remember the four prefixes of 101 that have been seen as a contiguous subword in the input read so far. a
Question 2
Consider the following regular expressions over alphabet {a, b}, where the notation (a + b)+ means (a + b)(a + b)∗ : r1 = (a + b)+ a (a + b)∗ r2 = (a + b)∗b (a + b)+ Let L1 and L2 be the languages defined by r1 and r2, respectively. Which of the following regular expressions define L1 ∩ L2?
A
(a + b)+ a (a + b)∗b (a + b)+
B
(a + b)∗ a b (a + b)∗
C
(a + b)∗b (a + b)∗ a (a + b)∗
D
(a + b)∗ a (a + b)∗b (a + b)∗
Question 2 Explanation: 
L1 is the set of all words of length n ≥ 2 containing an a at one of the positions 2, · · · , n. L2 is the set of all words of length n ≥ 2 containing a b in one of the positions 1, · · · , n − 1. The intersection L1 ∩ L2 is the set of all words containing a b at one of the positions 1, . . . , n − 1 and an a at one of the positions 2, . . . , n. This is given by the expression in (c). Option (a) is incorrect since it accepts only words of length at least 4. Option (b) is incorrect since it accepts ab, which is not in L1 ∩ L2. Option (d) is incorrect once again as it accepts ab.
Question 3
Some children are given boxes containing sweets. Harish is happy if he gets either gems or toffees. Rekha is happy if she gets both bubble gums and peppermints. Some of the boxes are special, which means that if the box contains either gems or toffees, then it also contains bubble gums and peppermints. If Harish and Rekha are given boxes that are not special, which of the following can we infer?
A
Harish is happy
B
No bubble gums in Rekha’s box
C
No toffees in Harish’s box
D
There are peppermints in Rekha’s box
Question 3 Explanation: 
Let t denote that a box has toffees, g denote that it has gems, b denote the presence of bubble gums and p the presence of peppermints. If a box is special, it satisfies (g ∨ t) ⇒ (b ∧ p). A non-special box satisfies (g ∨ t) ∧ (¬b ∨ ¬p). Since g ∨ t holds, Harish is happy and (a) can be inferred. Since it is possible
Question 4
In a class, every student likes exactly one novelist and one musician. If two students like the same novelist, they also like the same musician. The class can be divided into novelist groups, each group consisting of all students who like one novelist. Similarly, musician groups can be formed. So each student belongs to one musician group and one novelist group. Which of the following is a valid conclusion?
A
There are more musician groups than novelist groups
B
There are at least as many novelist groups as musician groups
C
For every musician group, there is a bigger novelist group
D
For every novelist group, there is a musician group of the same size
Question 4 Explanation: 
Each novelist group is a subset of some musician group. So the number of novelist groups are at least as large as the number of music groups, which is option (b). Options (a), (c) and (d) are all violated in a scenario where there are two students s1 and s2, two novelists n1 and n2, and one musician m, with s1 liking n1 and m, and s2 liking n2 and m.
Question 5
A boolean function on n variables is a function f that takes an n-tuple of boolean values x ∈ {0, 1} n as input and produces a boolean value f(x) ∈ {0, 1} as output. We say that a boolean function f is symmetric if, for all inputs x, y ∈ {0, 1} n with the same number of zeros (and hence the same number of ones), f(x) = f(y). What is the number of symmetric boolean functions on n variables?n + 1
A
n + 1
B
n!
C
∑n i=0(n i)
D
2 n+1
Question 5 Explanation: 
Let Ci = {x ∈ {0, 1} n | x has i occurrences of 0}. For any i ≤ n, a symmetric function has to choose the same output for each x ∈ Ci . Thus a symmetric function can be described by an (n + 1)-tuple of binary values, and hence the number of symmetric functions is 2 n+1 .
Question 6
There are n songs segregated into 3 playlists. Assume that each playlist has at least one song. For all n, the number of ways of choosing three songs consisting of one song from each playlist is:
A
>n3/27
B
≤n3/27
C
(n 3)
D
n3
Question 6 Explanation: 
Suppose the number of songs in each playlist is n1, n2, n3 respectively. We have n1, n2, n3 ≥ 1. The number of ways of choosing three songs with one from each playlist is n1 · n2 · n3. Since the geometric mean of the numbers is less than or equal to the arithmetic mean, it follows that n1 · n2 · n3 ≤ n 3 27 . So, the answer is Option (b). Options (a) and (d) cannot be correct because of the above inequality. Option (c) cannot be true for all n. For instance, choose n1 = 2, n2 = n3 = 1. Then Option (c) gives 4 as the answer which is wrong. a 3 The next two questions are based on the following facts. Basketball shots are classified into close-range, mid-range and long-range shots. Long range shots are worth 3 points, while close-range and mid-range shots are worth 2 points. Of the shots that LeBron James attempts, 45% are close-range, 25% are mid-range, and 30% are long-range. He successfully makes 80% of the close-range shots, 48% of the mid-range shots, and 40% of the long-range shots.
Question 7
What is the probability that a LeBron shot attempt is successful?
A
1/2
B
4/5
C
3/5
D
4/7
Question 7 Explanation: 
For every 100 shots that LeBron James attempts, he makes 80/100 ∗ 45 + 48/100 ∗ 25 + 40/100 ∗ 30 = 36 + 12 + 12 = 60 of them. So the probablity that LeBron shot is successful is 60/100 = 3/5.
Question 8
What is the probability that a successful 2-point shot attempt by LeBron is a close- range shot?
A
2/5
B
3/5
C
3/7
D
3/4
Question 8 Explanation: 
From the previous solution, we see that out of every 100 shots, 36 are successful close- range shots, and 12 are successful mid-range shots. So out of every 100 shots attempted by LeBron James, 48 are successful 2-point shots, and 36 of them are close-range. Thus the probability that a successful 2-point attempt by LeBron is a close-range shot is 36/48 = 3/4.
Question 9
A fair coin is repeatedly tossed. Each time a head appears, 1 rupee is added to the first bag. Each time a tail appears, 2 rupees are put in the second bag. What is the probability that both the bags have the same amount of money after 6 coin tosses?
A
1/2.6
B
6!/2!.4!.2.6
C
2.2/2.6
D
6!/2.6
Question 9 Explanation: 
For the money to be equal in the bags, the number of heads should be twice the number of tails. This means in 6 tosses, there should be 2 tails and 4 heads. The number of ways of getting 2 tails and 4 heads in 6 coin tosses is 6C2. The total number of different occurrences of the coin tosses is 2 6 . Hence probability is 6C2 2 6 .
Question 10
We have a procedure P(n) that makes multiple calls to a procedure Q(m), and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in Q(m), and it had to be replaced by R(m), which runs in exponential time in m. Thankfully, P is still correct when we replace each call to Q(m) with a call to R(m) instead. Which of the following can we definitely say about the modified version of P?
A
P(n) still runs in polynomial time in n.
B
P(n) requires exponential time in n.
C
P(n) runs in polynomial time in n if the number of calls made to Q is proportional to log n.
D
P(n) runs in polynomial time in n if, for each call Q(m), m ≤ log n.
Question 10 Explanation: 
If m ≤ log n for each call to Q with argument m, then the running time of R(m) is exponential in m but polynomial in n. Since the number of calls to Q originally (and R after the modification) is a polynomial in n, the overall running time of P is polynomial. None of the other options definitively hold.
Question 11
Answers to Part B must be written only in the designated space after the corresponding question. 1. There are two cities, City X and City Y. Each city has a metro system consisting of three different lines — red line, blue line, and green line. Each station (in both cities) is classified as either interesting or uninteresting, depending on the places of interest near the station. Both cities have a designated station called City Centre. From every station, there is a red line, blue line and a green line, each going to different destinations. A sequence of colours represents a journey through the metro system. For example, with the sequence RGGB, one would first take the red line, get down and then take the green line, get down and again take the green line, and so on. Starting from the City Centre, following a sequence of colours will lead to a destination, which may or may not be interesting. Design an algorithm to check if there is a sequence of colours following which one can reach an interesting destination from the City Centre in X, but not from the City Centre in Y.
A
The metro system in each city can be modeled as a finite state automaton, with the alphabet being {R, G, B}. Every metro station is a state. There is a transition from station 1 to station 2 on R (respectively G, B) if the red line (respectively green line, blue line) from station 1 goes to station 2. Final states are the interesting destinations. Now the question is whether there exists a word in the language of the automaton for the first city but not in the language of the automaton for the second city. Letting A1 and A2 be the automaton corresponding to the first and second city respectively, we have to determine if L(A1) \ L(A2) 6= ∅. We can use standard constructions to first define an automaton A3 such that L(A3) = {R, G, B} ∗ \L(A2), and then an automaton A4 such that L(A4) = L(A1)∩L(A3). Finally we use the standard emptiness checking algorithm to check if L(A4) 6= ∅.
Question 11 Explanation: 
The metro system in each city can be modeled as a finite state automaton, with the alphabet being {R, G, B}. Every metro station is a state. There is a transition from station 1 to station 2 on R (respectively G, B) if the red line (respectively green line, blue line) from station 1 goes to station 2. Final states are the interesting destinations. Now the question is whether there exists a word in the language of the automaton for the first city but not in the language of the automaton for the second city. Letting A1 and A2 be the automaton corresponding to the first and second city respectively, we have to determine if L(A1) \ L(A2) 6= ∅. We can use standard constructions to first define an automaton A3 such that L(A3) = {R, G, B} ∗ \L(A2), and then an automaton A4 such that L(A4) = L(A1)∩L(A3). Finally we use the standard emptiness checking algorithm to check if L(A4) 6= ∅.
Question 12
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Assume we are dealing with finite, undirected, simple graphs with at least two vertices. A graph is connected if there is a path between any two vertices in the graph, and is disconnected otherwise. The complement G of a graph G has the same vertex set as G, and contains an edge {u, v} if and only if G does not contain the edge {u, v}. For the first and third questions below, you will get the credit only if you also provide the justification. If your answer is yes, drawing an example of such a graph G and its complement G suffices as the justification. If your answer is no, then you should argue why this is the case.
A
Does there exist a graph G with at least two vertices such that both G and G are disconnected? Justify your answer.
B
Give an example of a graph G on four vertices such that G is isomorphic to its complement G.
C
Does there exist a graph G with at least two vertices such that both G and G are connected? Justify your answer.
Question 12 Explanation: 
(a) No, there are no such graphs. Let G be a disconnected graph, and let u, v be two vertices in G such that there is no path in G from u to v. Let Cu be the set of vertices of the connected component of G to which u belongs, and let R = V (G) \ Cu be the rest of the vertices. Then v ∈ R and no vertex in Cu has a neighbour in R. So in G every vertex in Cu is a neighbour of every vertex in R. If |Cu| = 1 then this means that G is connected. So let |Cu| ≥ 2. Let x, y be any two vertices in G. If one of these is in Cu and the other is in R then (as shown above) {x, y} is an edge in G. If both x and y are in Cu then {x, v} and {y, v} are edges in G. If both x and y are in R then {x, u} and {y, u} are edges in G. Thus there is a (short!) path between every pair of vertices in G, and so G is connected. (b) We take G = (V, E) where V = {v1, v2, v3, v4} and E = {{v1, v2}, {v2, v3}, {v3, v4}}. G = (V, F) where F = {{v1, v3}, {v1, v4}, {v2, v4}}. G is isomorphic to G, as given by the map {v1 7→ v2, v2 7→ v4, v3 7→ v1, v4 7→ v3}. (c) Yes. G from part (b) is an example.
Question 13
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Assume we are dealing with finite, undirected, simple graphs with at least two vertices. A graph is connected if there is a path between any two vertices in the graph, and is disconnected otherwise. The complement G of a graph G has the same vertex set as G, and contains an edge {u, v} if and only if G does not contain the edge {u, v}. For the first and third questions below, you will get the credit only if you also provide the justification. If your answer is yes, drawing an example of such a graph G and its complement G suffices as the justification. If your answer is no, then you should argue why this is the case.
A
Does there exist a graph G with at least two vertices such that both G and G are disconnected? Justify your answer.
B
Give an example of a graph G on four vertices such that G is isomorphic to its complement G.
C
Does there exist a graph G with at least two vertices such that both G and G are connected? Justify your answer.
Question 13 Explanation: 
(a) No, there are no such graphs. Let G be a disconnected graph, and let u, v be two vertices in G such that there is no path in G from u to v. Let Cu be the set of vertices of the connected component of G to which u belongs, and let R = V (G) \ Cu be the rest of the vertices. Then v ∈ R and no vertex in Cu has a neighbour in R. So in G every vertex in Cu is a neighbour of every vertex in R. If |Cu| = 1 then this means that G is connected. So let |Cu| ≥ 2. Let x, y be any two vertices in G. If one of these is in Cu and the other is in R then (as shown above) {x, y} is an edge in G. If both x and y are in Cu then {x, v} and {y, v} are edges in G. If both x and y are in R then {x, u} and {y, u} are edges in G. Thus there is a (short!) path between every pair of vertices in G, and so G is connected. (b) We take G = (V, E) where V = {v1, v2, v3, v4} and E = {{v1, v2}, {v2, v3}, {v3, v4}}. G = (V, F) where F = {{v1, v3}, {v1, v4}, {v2, v4}}. G is isomorphic to G, as given by the map {v1 7→ v2, v2 7→ v4, v3 7→ v1, v4 7→ v3}. (c) Yes. G from part (b) is an example.
Question 14
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Prove or disprove: There exists a finite, undirected, simple graph with at least two vertices in which each vertex has a different degree. To give a proof it suffices to draw an example of such a graph. To disprove the result, you should provide an argument as to why such a graph cannot exist.
A
There are no such graphs. If G is such a graph on n vertices then the possible degrees for its vertices are 0, 1, . . . ,(n − 1), and since there are exactly n of these values, all of them must appear as a degree of some vertex exactly once. If a vertex of G has degree (n − 1) then it must be adjacent to every other vertex in G, and in this case no vertex can have the degree 0. So G cannot exist.
Question 15
Consider the procedure Mystery described in pseudocode below. The procedure takes two non-negative integers as arguments. For a real number x the notation bxc denotes the largest integer which is not larger than x. Mystery(p, q) 1 if p == 0 2 then return 0 3 r ← bp/2c 4 s ← q + q 5 t ← Mystery(r, s) 6 if p is even 7 then return t 8 else return t + q
A
What does Mystery(100, 150) return?
B
How many times is the statement on line 8 executed in a call to Mystery(100, 150)?
C
In general, what does Mystery(m, n) return for m, n ≥ 0? Justify your answer with a proof.
Question 15 Explanation: 
(a) 15000 (b) This is the number of 1s in the binary representation of 100. So the answer is 3. (c) Mystery computes the product of the two input numbers. It is an implemen- tation of the following recurrence: x × y =    0 if x = 0 bx/2c × 2y if x is even (bx/2c × 2y) + y if x is odd a 5. Let Σ = {a, b}. For two non-empty languages L1 and L2 over Σ, we define Mix(L1,
Question 16
A password contains exactly 6 characters. Each character is either a lowercase letter {a, b, . . . , z} or a digit {0, 1, . . . , 9}. A valid password should contain at least one digit. What is the total number of valid passwords?
A
Here is an incorrect answer to the above question. Find the flaw in the argument. Let Pi denote the number of passwords where the i-th character is a digit, for i ∈ 1, . . . , 6. P1 = 10 · (36)5 P2 = 36 · 10 · (36)4 . . . P6 = (36)5 · 10 Therefore, total number of valid passwords is 6 · 10 · (36)5 (the sum of the right hand sides above).
B
What is the correct answer? Provide a justification for your answer. You do not need to simplify your expressions (for example, you can write 265 , 5!, etc.).
Question 17
We are given an array of N words W[1 · · · N], and a length array L[1 · · · N], where each L[i] denotes the length (number of characters) of W[i]. We are also given a line width M, which is assumed to be greater than every L[i]. We would like to print all these words, in the same order, without breaking any word across multiple lines. To illustrate, suppose M = 15, N = 7, and the words and lengths are as given below: Word Can you solve this using dynamic programming? Length 3 3 5 4 5 7 12 Here are four example ways of laying out this text. Note that there should be a space between adjacent words on the same line. Layout 1 Layout 2 Layout 3 Layout 4 Can Can you Can you solve Can you solve you solve this this using this using dynamic solve using dynamic dynamic programming? this programming? programming? using dynamic programming? Of the four layouts above, Layouts 1, 2 and 3 are valid since each line has at most 15 characters, while Layout 4 is invalid since line 2 requires 18 characters, which will spill over beyond the line width of 15. Each valid layout has a cost, computed as follows. Let the text be spread out over K lines. For each line i, let si be the number of spaces that are appended at the end of the line to make the line exactly M characters long. The cost of the layout is ∑K i=1 s 3 i . For example, Layout 1 has cost (15 − 3)3 + (15 − 3)3 + (15 − 5)3 + (15 − 4)3 + (15 − 5)3 + (15 − 7)3 + (15 − 12)3 = 7326. Layout 2 has cost (15 − 7)3 + (15 − 10)3 + (15 − 13)3 + (15 − 12)3 = 672. Layout 3 has cost (15 − 13)3 + (15 − 10)3 + (15 − 7)3 + (15 − 12)3 = 672. We can use dynamic programming to compute the smallest cost of any layout for N words W[1 · · · N] with lengths given by L[1 · · · N], and line width M. For 1 ≤ i ≤ N, let C[i] denote the minimum cost of any layout for words W[i· · · N].
A
Write a recurrence relation for C[i] in terms of C[i + 1], C[i + 2], . . . , C[N].
B
Implement your recurrence as a dynamic programming algorithm.
C
How much time and space does your algorithm need, in terms of N?
Question 17 Explanation: 
(a) It is convenient to define C[N + 1] = 0. For i ≤ N, if we print words W[i] to W[j] on the first line, the number of spaces at the end of the first line is si,j = M −(L[i]+· · ·+L[j]+j−i). We then have to distribute W[j+1], . . . , W[N] on the remaining lines, and the minimum cost for that is C[j + 1]. Thus C[i] = min{s 3 i,j + C[j + 1]|i ≤ j ≤ N, si,j ≥ 0}. (b) We solve this by filling in the C array from entry C[N + 1] = 0 onwards. To compute C[i], we require si,j values for j ≥ i. Rather than naïvely recomputing each sij as a separate summation, we use the recurrence si,j = si,j−1 − L[j] − 1 to compute the values on the fly. The full program is given below. array C[1..N+1] of int; int i, j, C, s; C[N+1] = 0; i = N; while (i >= 1) { j = i; s = M-L[i]; C = s^3 + C[i+1]; while (j <= N and s >= 0) { C = min (C, s^3 + C[j+1]); j = j+1; s = s-L[j]-1; } C[i] = C; i = i-1; } (c) From the above program, we see that each C[i] can be computed in O(N) time, given the C[j] values for j ≥ i. Thus the overall time needed is O(N2 ). Since we only store the C[i] values, and a constant number of variables to keep track of the current values of i, j and si,j , the space needed is O(N).
There are 17 questions to complete.