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 levelfour 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 nondominating 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 noninitialised memoisation (bookwork). The remainder of the question was—as I predicted—about SmithWaterman. I'm not quite sure what "Explain the meaning of the values s_{ij}," meant, but it was only for a couple of marks at most. There was also an opportunity for handexecution, that rare pleasure.
Question 3 was, on the face of it, a bit gentler. 16 whole marks for bookwork (definitions and the augmenting pathsearch 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 Smatching is. All I know is that, come next year, the maximum Smatching will be to Algorithmics what the track buffer is to Operating Systems. That is to say, illdefined on some godforsaken blog.
Question 4 I did not do. It was a tossup 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 6mark proof of 2approximation: 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 maximumfinding, 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.
