Regarding problem 3: I believe nobody should get a CS degree without being able to reason about grammars, precedence, associativity etc. This is far more important that knowing pushdown automata, the pumping lemma or anything like that.
Problems 4 and 7 are typical interview puzzles. Unfortunately, not too many people recognized problem 7 as a disguise for the streaming problem of finding a majority element. I should have asked for Socrates to use only O(n) debates.
Problem 8 is actually hard. Even if you have an intuitive idea why Inca Machines cannot recognize more than regular languages, you need to find a couple of tricks to make it a formal proof.
I think 7 is missing from the midterm?
ReplyDeleteOh. 6 is there twice... that is the problem with 7.
ReplyDeleteI'm curious as to whether anyone completely answered #8, or if you expected they would? I recall working through a similar problem in Sipser, and a) it took me a long time to work out the details, and b) my write-up was not very concise; it was kind of longish and cobbled together several pieces.
ReplyDeleteOn the other hand, I am not exactly MIT material...
Nobody did, unfortunately. On the other hand, I am quite sure some people would have solved it at MIT .
ReplyDelete1. What is INDEXING?
ReplyDelete2. It's a bit strange to say left/right associative for ternary operators.
3. The time seems quite tight to me. Perhaps that's why nobody did Q8.
rgrig,
ReplyDeleteIn indexing, alice receives an n-bit vector x, and bob receives an index i in {1,...,n}. After some communication with alice, bob outputs a bit, and we say he succeeds if his output is x_i. The relevant theorem is that if the communication consists of only one message, in the alice --> bob direction, and bob succeeds with probability at least 2/3, then sometimes alice must be sending messages that are Omega(n) bits long.
Jelani,
ReplyDeleteThanks. I don't see how to use that result though so the problem is still too hard for me. I know it can be solved obviously with O(n lg n) bits by just keeping all the n numbers in memory. Also, any approach that tries to keep track of the set of seen numbers requires Omega(n lg n).
But that's not very useful (or interesting). Since it's a lower bound I tried to transform somehow an instance of indexing into an instance of the given problem, but I can't even figure out what the basic setup could be.
I also looked at Q8 a little. Point (a) seems easy: Copy the input one cell to the right and then use only the locations with even "addresses". The answer to (c) seems to be regular languages and the proof idea I had in mind is some sort of explorations of the paths in the Turing machine to build an equivalent finite automaton. Point (b) is tricky. You need to show that the Inca machine is not stronger than a RO TM and there isn't any algorithm for transforming an Inca machine into a RO TM. So the proof has to be an existence proof (that will also do the path exploration thing). Is this right?
Ah, just noticed that Mihai actually mentions regular languages :p giving the answer to point (8c).
ReplyDeleteHi Mihai.
ReplyDeleteI like a lot your Socrates problem, with O(n) debates, provided one insists on DETERMINISTIC solution. I solved it after 5 minutes of thinking, but my solution is a bit "tricky". Not too tricky, but I suspect something simpler is possible. I put my solution below, but did I miss a simpler solution that you had in mind?
======================================
Solution: proceeds in log n rounds. In each round, split people in pairs (if odd, the "odd" guys goes to the next round). Get mutual opinions (A,B) for each pair. If A=B=honest, one guy in the pair (chosen arbitrarily) goes to the next round, the other does not. If either A or B is "lier", none of the members of the pair goes to the next round.
Claim 1: the number of people going to the next round is at most ceiling of n/2.
Proof: easy, since in each pair at most one guy goes to the next round.
Claim 2: after each round, the majority is still honest.
Proof. induction. true at the beginning. inductive step. if we get A=B=honest, either both guys are honest or both are liers. Thus, selecting one of them arbitrarily will maintain the fact that majority is honest, since number of honest-honest pair must be greater than lier-lier pairs. Similarly, whenever we drop BOTH guys, at least one of them is the lier, so majority remains honest after we drop both guys as well. QED.
Claim 3: a round cannot finish with eliminating everybody.
Proof: easy, since at least one pair must be honest-honest due to majority (if you count odd guy as a pair), and one guy survives from this pair.
Together, Claims 1-3 establish the following:
Corollary: at the end of the process, exactly one guy is left, and this guy is honest. Moreover, it took O(n) debates to get him.
The complexity follows from T(n) = T(n/2) + O(n).
Finally, one you get this one honest guy, just have him debate everybody and tell his honest opinion, which is another n-1 debates. So total is O(n).
======================================
Is this what you had in mind?
Anon, your proof certainly works. What I had in mind was a bit simpler: a sequential version of what you wrote.
ReplyDeleteIn class, I taught them the linear-time algorithm for finding a majority in an array:
cnt=0;
for(i=0; i<n; i++) {
if(!cnt) maj=a[i], cnt=1;
else if(maj == a[i]) cnt++;
else cnt--;
}
This same algorithm can be used by Socrates.