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.