- Teaching Materials
Go to Teaching Materials

- Context
This 10-credit elective was taught four times between 2003 and 2007 to second-year undergraduates on the single honours B.Sc. computing degree in UCC's Computer Science Department.

- Workload
The workload is 6 hours per week for the whole year, and is divided roughly as follows:

- Lectures: 2 lectures per week, each lasting 1 hour.
- Tutorials: 2 tutorials per week, each lasting 1 hour.
- Private study: At least 2 hours of private study per week.

- Prerequisites
MA1015: Discrete Mathematics for Computer Science

- Assessment
- Written exam: A three-hour paper in the Summer term, worth 160 marks.
- Year's work: Two class tests, worth 20 marks each.

- Description
This module provides a gentle introduction to the theory of computation. We cover three main topics:

**Correctness:**How can we be sure that a program solves a problem?**Complexity:**How do we measure and compare the resources (time and memory) required by algorithms and by problems?**Computability:**How do we determine which problems can be solved by algorithms and which cannot?

- Aims
- Students will obtain a broad understanding of the theory of computation.
- They will be able to find short formal proofs, especially for formulae of propositional logic;
- They will be able to prove the correctness of simple imperative programs.
- They will be able to determine the worst-case time complexity of simple imperative algorithms;
- They will have an understanding of problem complexity classes;
- They will be able to prove informally the unsolvability of problems;
- They will be aware of a few different models of computation.