If there's one certainty, it's that a Polynomial Time Reduction NP-Completeness proof is a staple of the Algorithmics 3 exam. Today we learned, along with the location of the Turnbull Hall, that this is no longer true.
All the heartbreak that was poured into the past paper questions, proving CLIQUE, SAT et al to be NP-Complete was a waste. Not a murmur of the awkwardly-circularly-defined concept. Instead, they slipped in a naughty little question on Turing machines, which many wags surmised couldn't possibly come up.
Question 1, on Rob Irving's side of the course, was about Tries. A definition, a diagram and three algorithms were necessary. Without a doubt, future students will look back at this question and dismiss it as "easy", but it has a certain tricky quality about it. One had to string out a rather long definition of a trie for seven marks, and the algorithms (fifteen marks in total) were not bookwork. I didn't really like the look of this from the outset, and skipped over it, to complete it later.
Question 2, the mixed bag, juxtaposed Merge-Sort and Turing Machines. The Merge-Sort question was standard fare, with a non-bookwork digression about applying the algorithm to linked lists. I didn't give this too much thought, but it's probably a fairly-straightforward extension of the array version. The second part put just about everybody off - amongst some general theory:
Construct a Turing Machine T to perform the addition of two positive integers represented in unary. Your answer should indicate the set of states and the state transition function for T.
Now, I admit that I looked at this and baulked, but - coming back to it - it's far simpler than the examples that we did in the tutorial and the lecture, and the hint makes the operation very clear. If I had considered that this material might come up in the exam, I'd have jumped at it. One for the future generations, methinks.
Question 3 was David Manlove's, and all about Breadth-First Search, in much the same way that Q3 of the 2003 exam was all about Depth-First Search. Though, if you're reading this in 2005, don't assume that there's going to be a pattern there.
And so we're three down, and, in the commonly-held opinion, that's the second-worst out of the way. Hurrah. Until Friday....
PS. Stu did the multithreading question in AP on Monday. Hardcore!