|
CS355 - Theory of Computation
Department of Computer Science
National University of Ireland, Maynooth
|
This is the CS355 homepage
This course runs every second year, in academic years that begin in an even year (e.g. the 2004-2005 academic year). In odd years (e.g. the 2005-2006 academic year) the module is "Computation and Complexity." 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: 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.
Continue reading this page for CS355 - Theory of Computation. Follow this link for CS370 - Computation and Complexity.
Academic year: 2004-2005. Semester: I
Lecturer: Tom Naughton
CS355 course outline
Laboratory demonstrators: Damien Woods, Aidan Delaney
Handout for introductory mathematics
Lab sheets, lab tests, and sample solutions
Lab marks and test marks are posted online
Mirror of Paul Ming's Perl Virtual Turing Machine (VTM)
Previous exam papers:
2004-2005 (autumn)
2004-2005 (winter)
In the following previous exam papers, questions that use the phrases countable, recursively enumerable, undecidable, reduction, and NP-complete, are not relevant to this course any more (this material has been moved to the course CS370 - Computation and Complexity):
2002-2003 (autumn)
,
2002-2003 (summer)
,
2002-2003 (winter)
,
2002-2003 (sample)
Lectures and tutorials (academic year 2004-2005, semester I)
Time: Thu 09h CS1, Fri 16h CS1
Location: CS1: Callan Extension Ground Floor
Laboratory Sessions
Tue 10h-12h Lab4, Callan Extension Ground Floor
Consultation Hours
Immediately after lectures, or any time you find me in Office 2.104 (Callan Extension, upstairs)
