CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth
This is the CS370 homepage
This course runs every second year, in academic years that begin in an odd year (e.g. the 2005-2006 academic year). In even years (e.g. the 2006-2007 academic year) the module is "Theory of Computation." The two modules are designed such that:
The only difficulty arises when a student takes a year off between third and fourth year. In such a case, the student would not be allowed to take the computer theory option in their fourth year.
- they are at a level suitable for 3rd and 4th year B.Sc. (Science and CSSE) students,
- they have a small amount of material in common,
- they can be taken in any order (one is not a prerequisite of the other),
- either one will give students a good grounding in computer theory,
- students must take the computer theory course on offer in their third year, and
- students have the option of taking the other course in their fourth year.
Some things the two modules have in common:
Continue reading this page for CS370 - Computation and Complexity. Follow this link for CS355 - Theory of Computation.
- Lecturer: Tom Naughton
- Students: 3rd yr BSc (Science), 3rd yr BSc (CSSE), 3rd yr BSc (Bioinformatics), 3rd yr BA, 4th yr BSc (Science), 4th yr BSc (CSSE), 4th yr BSc (Bioinformatics), 1st yr MCompSci, 2nd yr MCompSci, International students (Erasmus, Socrates programmes)
- Course text: Michael Sipser, Introduction to the Theory of Computation, Second Edition, Thomson, Boston, 2006, ISBN: 0619217642 or Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1997, ISBN: 053494728X. It is recommended that students purchase either of these books. Buy the first or second editions, new or used, at amazon.co.uk (more at amazon.com, amazon.de, etc.) or order from the NUIM University bookshop (give them the full information including ISBN number). I also have a limited number of copies from previous years' students; enquire immediately after lectures.
Academic year: 2005-2006. Semester: I
Lecturer: Tom Naughton
CS370 course outline
Laboratory demonstrators: Des Traynor, Niall Murphy
Lab sheets, lab tests, sample solutions, and grades
Handout: Template for undecidability proofs using a mapping reduction .
Mirror of Paul Ming's Perl Virtual Turing Machine (VTM) .
Sample paper for academic year 2003-2004
plus sample solutions .
Previous exam papers:
Lectures and labs
Time: Mon 13h CS2, Fri 09h SLT
Location: CS2 - Callan Extension, SLT - Callan Building
Tuesdays 16h-18h Lab4, Callan Extension
Immediately after lectures, or any time you can find me in Office 2.104 (Callan Extension, upstairs)