Robin Hirsch's part of COMP3004  - Computational Complexity

Material from the first part of COMP3004 concerning computability can be found  here

• Syllabus
• Course notes on complexity.
• Complexity slides. 
• Moodle.  The first assessed coursework will be a moodle quiz.  The deadline is 10/12/2010.
• Second assessed coursework, on the graph colouring problem.  The deadline has for submission is 13/Jan/2011.   Hand it in to the departmental office.  Answers.
• First set of exercises, for the problem class on 16/11/10 at 3pm.
• Second set of exercises.for the problem class on 23/11/10.
• Third set of exercises for the problem class on 30/11/10.
• Fourth exercise sheet.  This is an exam question from 2006.  For the problem class on 7/12/10.  Please attempt question 2 only (question 1 is from Mark Herbster).
• Some alternative notes of a colleague of mine, if you are interested.  For complexity see chapters 9-12.  Also, here are some exercises provided by Prof. Hodkinson.
• Alan Turing's original 1936 paper "On computable numbers."
• A video of Mark Davey's Turing Machine (and here is another Turing Machine made of lego).
• Communications of the ACM archive, Volume 52 , Issue 9 (September 2009) The Status of the P versus NP Problem.  Go to "Electronic Journals" from the library catalogue, choose Communications of the ACM and find the article.
• New Scientist article on how "smart ants" can solve the TSP quickly and another article on why this is a hard problem..
• Practice exam type question on Turing Machines and Prime Testing.  PDF version. 
• Sample exam type question on probabilistic Turing Machines.  PDF version.
• Lots of additional material on models of computation from the Ars Digita University.
• Course assessment form, for Robin Hirsch's part of the course.