CS370 - Computation and Complexity

NUIMCrest 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:

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.

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.

Some things the two modules have in common:

Lecturer: Tom Naughton
Students: 3^rd yr BSc (Science), 3^rd yr BSc (CSSE), 3^rd yr BSc (Bioinformatics), 3^rd yr BA, 4^th yr BSc (Science), 4^th yr BSc (CSSE), 4^th yr BSc (Bioinformatics), 1^st yr MCompSci, 2^nd 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.