COMP0003 Theory of Computation

This database contains the 2018-19 versions of syllabuses. These are still being finalised and changes may occur before the start of the session.

Syllabuses from the 2017-18 session are available here.

Academic session

2018-19

Module

Theory of Computation

Code

COMP0003

Module delivery

1819/A4U/T1/COMP0003 Undergraduate

Related deliveries

None

Prior deliveries

COMP102P

Level

Undergraduate

FHEQ Level

L4

FHEQ credits

15

Term/s

Term 1

Module leader

Brotherston, James

Contributors

Brotherston, James

Nakamura, Yuzuko

Module administrator

Ball, Louisa

Levit, Getrud

Aims

The module aims to introduce formal methods for reasoning about algorithms and, more generally, to formalise the reasoning process.

Learning outcomes

On successful completion of the module, a student will be able to:

  1. identify and reason with the logical content of arguments;
  2. recognise, write down and reason about automata and language grammars;
  3. carry out standard proofs and refutations involving logic and computational models.

Availability and prerequisites

This module delivery is available for selection on the below-listed programmes. The relevant programme structure will specify whether the module is core, optional, or elective.

In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.

Programmes on which available:

  • BSc Computer Science (Year 1)
  • MEng Computer Science (International Programme) (Year 1)
  • MEng Computer Science (Year 1)
  • MEng Mathematical Computation (International Programme) (Year 1)
  • MEng Mathematical Computation (Year 1)
  • BASc Arts and Sciences (Sciences and Engineering)
  • BSc Security and Crime Science

Prerequisites:

In order to be eligible to select this module, students must have A-level Mathematics, or equivalent.

Content

This course introduces students to the theory of computation. The first 5 weeks of the course will focus on mathematical logic, including: propositional logic, first-order logic, proof by induction and modal logic. The second 5 weeks will focus on fundamentals of computation, automata and language theory.

An indicative reading list is available via http://readinglists.ucl.ac.uk/departments/comps_eng.html.

Delivery

The module is delivered through a combination of lectures, tutorials, seminars, written and programming exercises, and project work.

Assessment

This module delivery is assessed as below:

#

Title

Weight (%)

Notes

1

Written examination (2hrs 30mins)

95

 

2

Coursework

5

 

In order to pass this module delivery, students must:

  • achieve an overall weighted module mark of at least 40%; and
  • achieve a mark of at least 30% in any components of assessment weighed ≥ 30% of the module.

Where a component comprises multiple assessments, the minimum mark applies to the overall component.