As you know, I am teaching Computability and Complexity at Berkeley. Here is the midterm I gave today. It may be fun for my younger readers to look through it. Leave comments.
Monday, March 16, 2009
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.
Posted by Mihai at 6:26 PM