Cast your mind back to the Algorithmics 3 exam last year. A surprising question on Turing machines made it far less pleasant than it should have been, and, naturally, there was always the chance that its level-four counterpart could go the same way.
Question 1 concerned itself with geometric algorithms. 11 marks for convex hull bookwork, 3 marks for a reprise of a tutorial question, and 6 marks for an unseen problem to do with domination. The unseen problem was superficially very similar to a tutorial exercise, but in the opposite direction: find all the non-dominating points rather than all the dominating ones. A subtle ruse to trick us into reciting the tutorial answer? Surely not.
Question 2 was somewhat more interested in String and Text algorithms. Part (a) was an unseen (albeit more straightforward) question about a recursive algorithm with memoisation, backed up with a further six marks on the subtleties of non-initialised memoisation (bookwork). The remainder of the question was—as I predicted—about Smith-Waterman. I'm not quite sure what "Explain the meaning of the values sij," meant, but it was only for a couple of marks at most. There was also an opportunity for hand-execution, that rare pleasure.
Question 3 was, on the face of it, a bit gentler. 16 whole marks for bookwork (definitions and the augmenting path-search algorithm) and just 4 marks for an unseen question. But that unseen question was a doozy. Even now, I'm not convinced I understand what a maximum S-matching is. All I know is that, come next year, the maximum S-matching will be to Algorithmics what the track buffer is to Operating Systems. That is to say, ill-defined on some godforsaken blog.
Question 4 I did not do. It was a toss-up between 3 and 4, as both contained last parts that weren't immediately obvious. I chose 3 because it was only 4 marks, whereas 4 had a 6-mark proof of 2-approximation: the sort of thing that never sat right with me throughout revision. Apart from that, there was the tricksy proof of a lower bound on maximum-finding, and my favourite kind of proof—an inapproximability result (always they leave a lingering hope that P might just equal NP).
I think the difficulty of these exams can be measured in the amount of unexpected questions. It's difficult to judge the past papers without knowing exactly how the courses were taught in previous years, but it seems that this year's paper was a little heavier in that respect (some past papers had two questions consisting completely of bookwork). Still, it was a fair paper, and perhaps next year's cohort will get it slightly easier.
Cheers,
Derek.
|