Computability (G53COM)
Semester 2, 2011-12

News

If you send me an email, please put g53com in the subject line, so I know imediately that it is about this module.

Why might you want to take this module? One reason would be to understand why $1,000,000 is being offered to solve one of the biggest challenges in computer science: Does P = NP? (or see the wiki page).It will cover fundamental results about what computers can and cannot do. These are some of the vital topics that make 'computer science' into a 'science'.

Introduction

This session this module is taught by Dr Andrew Parkes http://www.cs.nott.ac.uk/~ajp/.

• Lecture timetable:
  
  • Mondays 12:00-13:00 Amenities Building, room B12
  • Thursdays 14:00-15:00, Business South, room A24 (some weeks are in the lab: Room C11, School of CS)

  The complete reading list is here. (though be aware that the Papadimitriou book is a classic reference book, it is quite hard and we will only do small portions.)

  Previous sessions of the module:

  • 2010-11 (taught by Dr. Andrew Parkes)
  • 2009-10 (taught by Dr. Andrew Parkes)
  • (module did not run in 2008-09)
  • 2007-08 (taught by Dr. Natalio Krasnogor)
  • 2006-07 (taught by Dr. Natalio Krasnogor)

  Generally speaking, module contents do not change substantially from year to year, and so previous years are still quite relevant.

  Contact Details

  If you have any problems/suggestions/feedback etc, please feel free to email (andrew.parkes), telephone (0115 95 14210), or visit my office (CS Room C40 ).
  

  The course also has an email list http://www.cs.nott.ac.uk/local-cgi/lists.cgi?gs=g53com. I will use this mailing list for sending out information. I'll advertise when the list is updated for this session, and I start sending out emails and you should make sure that you are receiving them.

  Hence, as usual, you MUST make sure that the department (and technical services) has a working email address for you, and that it is included on the list (though note the list might not get fully updated until a few weeks into the semester).

  Timetable

  Please note that the timetable below is tentative and incomplete! It will change as we proceed, so please keep an eye on this page. When the mailing list is active, then I will also send out announcements to that list. I will also add links to the lecture notes as we proceed - though please note that the lecture notes do not necessarily cover everything I say during lectures. The dates of lectures are often just indicative; the notes are arranged in logical sections, but might not exactly coincide with the timeslots. (If you have any questions about slides please always tell me the name of the file, or the exact URL, and the page or slide number(s).)

  NOTE: files/slides are password protected. Email me if you did not get the email with the username/password.

  Date	Topic	Comments
  Week 1. Mon. Jan 30th	Introduction to the module (ppt) P-vs-NP-prize (ppt)	Usual formalities, plan of the module, and general context.
  Thurs. Feb 2nd	P-vs-NP-prize (ppt)	The first two lectures are trying to give an idea of what questions the module is concerned with, and some of the underlying intuitions and ideas.
  Week 2. Mon. Feb 6th	Start on more formal introduction to computability, and Turing Machines (docx)
  Thurs. Feb 9th NOTE: CHANGE OF ROOM Room C11 Computer Science	Exercises with programming of Turing machines.	We will use the TM simulator available here: http://ironphoenix.org/tril/tm/ Please start to do the exercises that are here Note I might update these with hints as we proceed, so reload regularly. They are also likely to take 3-4 weeks. So this lab session will repeat.
  Week 3. Mon. Feb 13th.	Sets and languages (docx) Turing Machines 2 (docx)	Languages, and "acceptance of a language"
  Thurs. Feb 16th NOTE: CHANGE OF ROOM Room C11 Computer Science	Continue exercises with programming of Turing machines.	We will use the TM simulator available here: http://ironphoenix.org/tril/tm/ Please start to do the exercises that are here Note I might update these with hints as we proceed, so reload regularly. They are also likely to take 3-4 weeks. So this lab session will repeat.
  Week 4. Mon. Feb 20th.	"REC" vs."RE" (pptx)	Decisions versus acceptance Auxiliary slides: pptx
  Thurs. Feb 23th NOTE: CHANGE OF ROOM Room C11 Computer Science	Continue exercises with programming of Turing machines.	We will use the TM simulator available here: http://ironphoenix.org/tril/tm/ Please start to do the exercises that are here Note I might update these with hints as we proceed, so reload regularly. They are also likely to take 3-4 weeks. So this lab session will repeat.
  Week 5. Mon. Feb 27th.	Halting Problem: informal version (ppt) formal version: (doc)
  Thu. Mar 1st. NOTE: No exercise classes until further notice. Back to standard room A24 in Business school	"Reductions" using "Halting problem formal version" (doc)
  Week 6. Mon. Mar 5th.	Universal and Non-deterministic Turing Machines (pptx)	Note: "Non Deterministic vs. Deterministic computation" is a vital concept for the rest of the module.
  Thur. Mar 8th	Time Complexity (pptx)	Formal lecture notes on time complexity, and NP (docx) List of standard decision problems to know (pptx)
  Week 7. Mon. Mar 12th.	Continue with time complexity and standard decision problems. Start on polytime reductions (pptx)
  Thur. Mar 15th	"Exercise class" on reductions. (I will give some reductions for you to try, and interleave with showing how to do them,)	You will need the list of standard decision problems (pptx) Reductions can form a vital part of the assessment questions that will require you to solve some problem (e.g. see previous exams). It takes some practice to be be able to do them; this is the chance to practice and get help when stuck.
  Week 8. Mon. Mar 19th.	NP-completeness. Cook Levin (pptx)
  Thu. Mar 22nd.	Other aspects of NP-completeness (pptx) Weak NP-completeness (pptx)
  Week 9. Mon. Mar 26th.	Weak NP-hardness continued. PSPACE, QBF (pptx) NPSPACE (pptx)
  Thu. Mar 29th.	PSPACE, NPSPACE and QBF (cont)
  EASTER BREAK
  Week 10. Mon. April 30th.	Parallel Complexity: PRAM (pptx)
  Thu. May 3th.	Parallel Complexity: Algorithms (pptx) Class NC and P-completeness (pptx)
  Week 11. Mon. May 7th.	(NO LECTURE - University closed - public holiday)
  Thu. May 10th.	Parallel Complexity: Algorithms and P-completeness (cont)
  Week 12. Mon. May 14th.	Revision lectures - Q&A and help sessions.
  Thu. Mar 17th.	Revision lectures - Q&A and help sessions.

  Exercises from Lectures

  Occasionally, during the lectures I will give an "Exercise" but that will not be answered in the lecture. I strongly advise that you attempt these, as they will help you keep track of your own progress and understanding. However, there is no need to submit anything, and I will (sometimes) go through the answers at the start of the next lecture.

  Coursework

  There is no formal assessed courseworks. However, informal ones are given, and it is highly recommended to do them, as they are essential to understanding the material, and good preparation for the exam.

  Exam

  This course is examined by a two hour examination, which accounts for 100% of the marks. The format will be the same as last year: Question one is compulsory, and answer 3 out of the other questions.

  ---

   

  Additional Reading Material

  • You are highly recommended to read the materials at http://www.claymath.org/millennium/P_vs_NP/. In particular:
    • The definition of the P vs. NP problem by Cook (probably only about 1/2 of this paper is at a level suitable to this module, but it might help fill in some gaps)
    • The online video lecture about P vs. NP (the lecture starts about 8 mins into the file, and is a bit long, but should all be comprehensible)
    • The pages about minesweeper - as they are given in terms of a puzzle that many of you probably already know, hence showiong the wide range of applicability of P/NP ideas.
  • Algorithm Design by Kleinberg and Tardos. Good book with chapter 8 "NP and Computational Intractability" being the most relevant. (Highly recommended to eventually read this chapter.)
  • Michael Trick on P?=NP
  • The P-vs-NP page
    • Links to some pictures of Homer Simpson: the other equation is the beautiful Euler's Identity
  • The Complexity Zoo http://qwiki.stanford.edu/index.php/Complexity_Zoo If P and NP are not enough,. then try it ... "Welcome to the Complexity Zoo... There are now 489 classes and counting!"
  • http://www.knowledgerush.com/kr/encyclopedia/Universal_Turing_Machine/
  • http://www.knowledgerush.com/kr/encyclopedia/Computable_number/
  • Wiki: Savitch's theorem
  • http://rjlipton.wordpress.com/2010/01/27/programming-turing-machines-is-hard/

   

  ---

  Last updated: 2012-05-03