Skip to navigation | Skip to main content | Skip to footer

COMP11212: Fundamentals of Computation (2010-2011)

This is an archived syllabus from 2010-2011

Fundamentals of Computation
Level: 1
Credit rating: 10
Pre-requisites: first semester of COMP10020 for non-CM students; none for CM students
Co-requisites: COMP10020 or equivalent mathematical background
Duration: 11 weeks
Lectures: 22 in total, 2 per week
Examples classes: 1 per week (starting in week 2)
Labs: none
Lecturers: Howard Barringer, Andrea Schalk, Thierry Scheurer
Course lecturers: Howard Barringer

Andrea Schalk

Thierry Scheurer

Additional staff: view all staff
Sem 2 Lecture ROSCOE B Mon 09:00 - 10:00 -
Sem 2 Lecture UNI PL A Thu 10:00 - 11:00 -
Sem 2 w2+ Examples IT407 Mon 13:00 - 14:00 M+W
Sem 2 w2+ Examples IT407 Mon 14:00 - 15:00 C+X
Sem 2 w2+ Examples LF15 Fri 14:00 - 15:00 Z
Sem 2 w2+ Examples IT407 Mon 15:00 - 16:00 D+Y
Assessment Breakdown
Exam: 75%
Coursework: 25%
Lab: 0%


The building of real-life computing systems, e.g. mobile phone, tv/video remote control, internet shopping, air-traffic control, internet banking, etc., is always a complex task. Mistakes can be very annoying, costly and sometimes life threatening. Methods and techniques to support the building and understanding of such systems are essential. This course unit provides an introduction to the basic computer science ideas underlying such methods. It is also a part of, and an introduction to, the Modelling and Rigorous Development theme.


This course unit provides a first approach to answering the following questions. What methods are there that can help understanding complicated systems or programs? How can we make sure that a program does what we intend it to do? How do computers go about recognizing pieces of text? If there are two ways of solving the same problem, how can we compare them? How do we measure that one of them gives the solution faster? How can we understand what computers can do in principle, and are there problems that are not solvable by a computer?

Programme outcomeUnit learning outcomesAssessment
A1 B1Be able to construct simple graph-based models of computation, e.g., finite state automata.
  • Examination
  • Individual coursework
A1 B1Understand how patterns and grammars can be used to recognise pieces of text.
  • Examination
  • Individual coursework
A1 B1Be able to build simple set-theoretic models of systems.
  • Individual coursework
  • Examination
A1 B1Be able to use models in order to reason about a system.
  • Individual coursework
  • Examination
A1 B1Appreciate that there are unsolvable problems.
  • Examination
  • Individual coursework
A1 B1Understand fundamental techniques for measuring performance of systems.
  • Examination
  • Individual coursework
A1 B1Gain skills in modelling and abstract thinking.
  • Examination
  • Individual coursework


There are three groups of topics covered.

The first (8 lectures) are concerned with expressing particular strings, and here we will introduce the methods by which a computer goes about it. The ability to recognize key strings (such as programming constructs or variable names) are, for example, required in every compiler, but they are also used by search engines such as Google.
The formalisms introduced include finite state automata, regular expressions (most often used in pattern matching), (regular) grammars. The emphasis is on students being able to use these formalisms to solve problems.

The second group (8 lectures) is central to the practice of system development. It introduces: set-theoretic models as a set of objects and associated operations; operations specified by pre and post conditions; simple techniques for determining properties of set-theoretic models.

The third group (4 lectures) provides a brief introduction to the two topics of computability and computational complexity. It covers the classical "Halting Problem" and then simple time and space complexity measures.

Reading List

The course is supported by lecture notes. Additional reading material will be supplied.