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.

LAW 2007

I went to the London Algorithmic Workshop, held at King's College London a few days ago. The main purpose is to see people, and to have some feeling of being in a city. (I don't expect to understand things like counting runs in a string using automata and such; although there is a talk about my ex-boss and his student's previous work.)

For all sorts of reasons, the cost of going there had increased considerably from the original estimate.

One thing is that I ended up staying at a hotel. Finding a cheap hotel in central London is like 買大細, for you never know how bad it can be. There are always terrible comments on the web for whatever hotel you pick. At the end, I picked one which seem to have not-too-bad comments. When I arrived I was relieved - it was very small as expected, but tidy and clean. From outside, the room is like a storage room or so at a turn of the stairs, but as long as you shut yourself inside it feels alright. There is no toilet/bathroom inside - have to use the shared ones outside. Apparently, this is the default for cheap hotels.

The return trip coincided with the heaviest snow of UK in 10 years (or something like that). You look out of the train window and it is white everywhere. But while the weather was bad enough, the train was very accurately on time.