Algorithms exam

At St. Valentine's day we had a dreadful meeting about the arbitrary manipulation of some numbers that are important to students (many of whom I don't know) in modules (many of which I don't care). I think it is now time to say something about the algorithms exam paper.

The exam paper has 6 questions and students answer 4. (I don't have any say about this.)

(1) I think I did an ok job of getting an average mark close to whatever number they want. You can easily estimate marks of students on different questions: if you want them to know how to answer, you must give them the exact same question beforehand, with only different numbers. This is the only way they know how to do something. Changing anything else would result in a very low mark.

(2) I included several straightforward (i.e. non-tricky) true/false questions, which are answered satisfactorily. (Never do tricky questions: the correct rate would be far lower than 50%).

(3) You might think that questions asking for simple counterexamples are easy, but they are not. I think this holds true for HK students as well.

(4) I believe no students can ever understand what "lower bound" means. Majority thinks "If the fastest known algorithm of a problem runs in O(n^2) time then the problem has a lower bound of Omega(n^2)" is a correct statement.

(5) There is only one dynamic programming question that you can expect people to do it correctly (and hence I put it in the exam paper) - working out longest common subsequences. They are fairly competent in filling in the tables, perhaps without knowing what they are actually doing.

(6) The divide and conquer question is a "difficult" one and as expected very few people do it. In an earlier assignment they did a question which has similar flavor - the standard maximum-sum contiguous subarray problem - and almost no one can get it correct. In fact, many do not even attempt to do it. It looks like if they decide that a question is difficult, they don't even bother to plagiarize - just leave it blank. I must say that I don't quite understand why they consider this very difficult, as I think this is a rather "natural" D&C problem - even when I first saw it in my first DAA assignment. Having said that, interestingly, a few actually accidentally discovered the linear-time algorithm.