CMI 2019

Question 1
Let L1={anbm | m,n >=0 and m>=n} and L2={anbm | m,n >=0 and m he language L1 U L2 is:
Regular, but not context free
Context free, but not regular
Both regular and context free
Neither regular nor context free
Question 1 Explanation: 
Question 2
Let A be an NFA with n states. Which of the following is necessarily true?
The shortest word in L(A) has length at most n-1.
The shortest word in L(A) has length at least n.
The shortest word not in L(A) has length at most n-1.
The shortest word not in L(A) has length at least n.
Question 2 Explanation: 
Assume that L(A) is non-empty. If A accepts a word of length >= n, there is an accepting run of A that has at least one loop. If we cut out all the loops in this run, we get an accepting run (on some other word) that visits each of the n states at most once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.
Question 3
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node A?
Question 3 Explanation: 
The predecessor of A is the rightmost node in the left subtree of A.
Question 4
There are five buckets, each of which can be open or closed. An arrangement is a specification of which buckets are open and which are closed. Every person likes some of the arrangements and dislikes the rest. You host a party, and amazingly, no two people on the guest list have the same likes and dislikes. What is the maximum number of guests possible?
Question 4 Explanation: 
Let us say a person's profile is a function from the set of all arrangements to {0,1} (indicating whether a particular arrangement is liked by that person or not). There are 25 possible arrangements. Thus there are 225 possible profiles. Two people with the same profile have the same likes and dislikes, and thus, no two guests have the same profile. Thus the maximum number of guests possible is 225
Question 5
Question 5 Explanation: 
For i ϵ {1,...,n}, let Pi be the set of all permutations x1;x2,..., xn for which x1 > x2 >... > xi.
Question 6
Suppose you alternate between throwing a normal six-sided fair die and tossing a fair coin. You start by throwing the die. What is the probability that you will see a 5 on the die before you see tails on the coin?
Question 6 Explanation: 
Question 7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match requires a team of referees and linesmen. Two matches that overlap require disjoint teams of referees and linesmen. The tournament organizers would like to determine how many teams of referees and linesmen they need to mobilize to effectively conduct the tournament. To determine this, which graph theoretic problem do the organizers have to solve?
Find a minimal colouring.
Find a minimal spanning tree.
Find a minimal cut.
Find a minimal vertex cover.
Question 7 Explanation: 
Matches are nodes. There is an edge between two matches if they overlap. Each team of referees and linesmen is a colour. A valid colouring assigns disjoint teams to overlapping matches. A minimal colouring determines the smallest number of such teams that are needed.
Question 8
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario?
We know of polynomial time algorithms for both A and B.
We only know of exponential time algorithms for both A and B.
We only know an exponential time algorithm for A, but we have a polynomial time algorithm for B.
We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
Question 8 Explanation: 
If we have a polynomial time solution for B, the reduction gives us a polynomial time solution for A. So it cannot be the case that we only know an exponential time algorithm for problem A.
The next two questions refer to the following program.
In the code below reverse(A,i,j) takes an array A, indices i and j with i <= j, and reverses the segment A[i], A[i+1],. . . ,A[j]. For instance if A = [0,1,2,3,4,5,6,7] then, after we apply reverse(A,3,6), the contents of the array will be A = [0,1,2,6,5,4,3,7].
function mystery (A[0..99]) {
int i,j,m;
for (i = 0; i < 100; i++) {
m = i;
for (j = i; j < 100, j++) {
if (A[j] > A[m]) {
m = j;
Question 9
When the procedure terminates, the array A has been:
Sorted in descending order
Sorted in ascending order
Left unaltered
Question 9 Explanation: 
This procedure is call pancake sort. Each iteration (of the outer for loop) moves the maximum value in A[i..99] to A[i].
Question 10
The number of times the test A[j] > A[m] is executed is:
Depends on the contents of A
Question 10 Explanation: 
In the first iteration, it is tested 100 times. As we proceed, it is tested 100+99+...+1 times, so the answer is 5050.
Question 11
Descriptive Explanation
Question 11 Explanation: 
Question 12
Descriptive Explanation
Question 12 Explanation: 
Question 13
There is a party of n people. Each attendee has at most r friends in the party. The friend circle of a person includes the person and all her friends. You are required to pick some people for a party game, with the restriction that at most one person is picked from each friend circle. Show that you can pick n/(r2+1) people for the game.
Descriptive Explanation
Question 13 Explanation: 
Consider an undirected graph where each vertex represents a person and there is an edge between two vertices if the corresponding people are friends. Suppose we pick two people who are at distance <= 2 from each other. Then they are either friends or share a friend, so they have overlapping friend circles (which could be the same circle). Thus we should ensure that no two people we pick for the party game are at distance <= 2 from each other.
We can now follow a simple strategy: pick an arbitrary vertex, then exclude everything else in the sphere of radius 2 around the picked vertex. The sphere will have at most r2 + 1 vertices, of which we have picked one. We continue similarly for the remaining vertices to pick at least n/(r2+1) vertices. From any friend circle, if we have picked one person, all others in that circle are excluded (since they are within distance 2), and thus our restriction for the party game is satisfied.
Question 14
Consider the assertion: Any connected undirected graph G with at least two vertices contains a vertex v such that deleting v from G results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
Descriptive Explanation
Question 14 Explanation: 
The assertion is true. Consider a longest path v0v1 ... vt in G. The vertex v0 can play the role of the vertex v in the question. Suppose deleting v0 results in a graph with two or more components. All of v0v1 ... vt will be together in one component. There is a vertex u in a di erent component of G-v0 such that uv0v1 ... vt is a longer path in G, a contradiction.
Question 15
In the land of Twitter, there are two kinds of people: knights (also called outragers), who always tell the truth, and knaves (also called trolls), who always lie. It so happened that a person with handle @anand tweeted something offensive. It was not known whether @anand was a knight or a knave. A crack team, headed by Inspector Chitra, rounded up three suspects and interrogated them.
The first interrogation went as follows.
Chitra : What do you know about @anand?
Suspect 1 : @anand once claimed that I was a knave.
Chitra : Are you by any chance @anand?
Suspect 1 : Yes.
The second interrogation:
Chitra : Have you ever claimed you were @anand?
Suspect 2 : No.
Chitra : Did you ever claim you are not @anand?
Suspect 2 : Yes.
The third suspect arrived with a defense lawyer (also on Twitter):
Lawyer : My client is indeed a knave, but he is not @anand.
Suspect 3 : My lawyer always tells the truth.
Which of the above suspects are innocent, and which are guilty?
Explain your reasoning.
Description Explanation
Question 15 Explanation: 
If Suspect 1 were Anand, then since he answers truthfully to the second question, he is a knight, but then his first reply means that he once claimed he was a knave, which knights will not do. Hence Suspect 1 is not Anand.
If Suspect 2 were Anand, then he is either a knight or a knave. If he were a knight, then the answer to question 2 means he claimed he was not Anand, which is a lie. Hence he is a knave. But then the answer to question 1 is a lie, which means he has once claimed he is Anand, which a liar will not do. This contradiction means that he is not Anand.
Now Suspect 3 cannot be a knight, since he says his lawyer is truthful, and the lawyer says that he is a knave. So Suspect 3 is a knave. And so what he said is false, and his lawyer is a knave. But then the lawyer has uttered a falsehood. Of the conjuction he uttered, at least one conjunct is false. But the first conjunct is true, so the second is false. And Suspect 3 is indeed Anand!
Question 16
Let A be an nXn matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number k appears in A. If k is present, we should report its position that is, the row i and column j such that A(i; j) = k.
Otherwise, we should declare that k is not present in A.
(a) Describe an algorithm that solves this problem in time O(n log n). Justify the complexity of your algorithm.
(b) Describe an algorithm that solves this problem by examining at most 2n values in A. Justify the complexity of your algorithm.
(c) For both algorithms, describe a worst-case input where k is present in A.
Descriptive Explanation
Question 16 Explanation: 
(a) Since each row is sorted, we can do binary search on each of the n rows. Since binary search works in O(log n) time, the algorithm works in O(n log n) time.
(b) Compare k against the top right corner element A(1; n). If k = A(1; n), we are done. Else there are two cases to consider. Case 1: k < A(1; n). Then k cannot appear in the last column (since A(1; n) is the smallest entry in that column) so we have to search for A in rows 1 to n, columns 1 to n - 1.
Case 2: k > A(1; n). Then k cannot appear in the first row (since A(1; n) is the largest entry in that row) so we have to search for A in rows 2 to n, columns 1 to n.
In the next step, we compare k against the top right corner of the remaining matrix of interest (the top right corner is A(1; n - 1) if Case 1 holds and A(2; n) if Case 2 holds) and repeat the earlier analysis.
With each step we reduce the matrix of interest by pruning eliminating one row or one column. Since we started with n rows and n columns, within 2n steps (actually 2(n - 1) steps) we would have pruned the matrix down to a single row and column, i.e. a single element.
(c) For the O(n log n) algorithm, the worst case input is when k appears in the last row (assuming we search each row in order from top to bottom).
For the algorithm with 2n steps, since the search proceeds from the top right to the bottom left, the search goes on longest if the element is at the bottom left corner, A(n; 1).
Question 17
Descriptive Explanation
Question 17 Explanation: 

There are 17 questions to complete.