- 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.