mrry (Happy New Year)
Blog Computing Science 3P - Algorithmics 3 19/May/2004

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!


Gary Fleming said:
Matt did the 2nd question in Algs. Brave or silly?

Cabumbo said:
Ahh algorithmics. Similarly to you i had spent hours learning the NP complete proofs and was saddened by the lack of even the mere mention of the letters N and P together. Turing Machines, now that was never going to come according to Q, but alas they did. Fortunately the rest of the questions were made up basically of tutorial exercises that I had elready looked at and obtained the answers off the web for. So all in all a pretty good exam, although my algorithm descriptions were, how you say, "A bit baws". All in all with 20% from assex it looks good for a good mark. Famous last words.....? 28th and we will see






Please enter the number 9197 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: