mrry (Happy New Year)
Blog Computing Science - Algorithmics 4 10/May/2005

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.




Gary Fleming said:
Desks in a toilet? I've heard stories about the ladies toilets before, but never about study areas within. As for the heavy breathing, some would say that that's a bonus.

Collleen said:
"Gary Fleming said:
Colleen: how is it as a toilet? ..."

Hm.. I never thought to check but if it was anything like the exam hall then it would be far too warm, with tiny extremely shaky fragile desks, and they'd be someone breathing very heavily next to you.

Gary Fleming said:
Colleen: how is it as a toilet?

Yeah, the algs exam was a bastard. I'm about the same level as Neil. Fecked it right up.

Colleen said:
If it makes you feel better I totally messed it up as well. Having spent most of my revsion concentrating on David Manlove's proofs and then finding none of them in the paper. Not a happy girl at all! Thankfully AC went well, though I would not rate the design studio as a good exam hall.

Neil said:
This paper annoyed me... in that it was pretty much what I wanted to come up but once I got in and started answering I realised that I didn't actually know the stuff that I thought I did. I knew all the concepts and so on but just couldn't articulate them. Hell I couldn't even remember the definitions of Matching, Augmenting Path and Convex Hull. I could draw a diagram of them but not articulate the properties. This of course led to a total loss of confidence and what resulted in a completely spacked up exam. I'd be ecstatic if I got a D for it... In fact, it even prompted me to phone my future Employer, Agilent, to confirm that I didn't need a 2:1 to get the job :P





Please enter the number 6993 in the box below:

CommentsTell a friend about this page

Your Name

Your E-Mail

Your friend's E-Mail


< # Scottish Blogs ? >
Technorati Profile
Listed on BlogShares

Subscribe to the mrry RSS feed
More about RSS.
Trackback URL for this article: