If there's one certainty, it's that a Polynomial Time Reduction NPCompleteness 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 NPComplete was a waste. Not a murmur of the awkwardlycircularlydefined 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 MergeSort and Turing Machines. The MergeSort question was standard fare, with a nonbookwork digression about applying the algorithm to linked lists. I didn't give this too much thought, but it's probably a fairlystraightforward 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 BreadthFirst Search, in much the same way that Q3 of the 2003 exam was all about DepthFirst 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 commonlyheld opinion, that's the secondworst out of the way. Hurrah. Until Friday....
Cheers,
Derek.
PS. Stu did the multithreading question in AP on Monday. Hardcore!
