Skip to main content
Module Search
A street in Durham, with old buildings and people walking down the street
 

COMP2181: THEORY OF COMPUTATION

Please ensure you check the module availability box for each module outline, as not all modules will run in each academic year. Each module description relates to the year indicated in the module availability box, and this may change from year to year, due to, for example: changing staff expertise, disciplinary developments, the requirements of external bodies and partners, and student feedback. Current modules are subject to change in light of the ongoing disruption caused by Covid-19.

Type Open
Level 2
Credits 20
Availability Available in 2023/24
Module Cap
Location Durham
Department Computer Science

Prerequisites

  • COMP1081 Algorithms and Data Structures

Corequisites

  • None.

Excluded Combinations of Modules

  • None.

Aims

  • To introduce students to: important models of computation and how they are related.
  • fundamental notions of computation such as 'computable' and 'efficiently computable'.
  • and the design and analysis of efficient algorithms.

Content

  • Models of computation
  • Basic computability theory
  • Algorithm design
  • Computational complexity

Learning Outcomes

Subject-specific Knowledge:

  • To have an understanding of different models of computation and their relevance to computer science.
  • To have an understanding of how algorithms can be used to solve fundamental problems within Computer Science.

Subject-specific Skills:

  • On completion of the module, students will be able to demonstrate:
  • an ability to use different models of computation in context of computer science
  • an ability to apply and analyze algorithms for fundamental problems within computer science

Key Skills:

  • On completion of the module, students will be able to:
  • extract an abstract computational model from a real world problem
  • distinguish between computationally tractable an intractable problems in computer science

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

  • Lecturing demonstrates what is required to be learned and the application of the theory to practical examples.
  • Problem classes through practicals provide assessment (both formative and summative) to guide students in the correct development of their knowledge and skills.
  • The end of year examinations assess the knowledge acquired and the ability to use this knowledge to solve problems.

Teaching Methods and Learning Hours

ActivityNumberFrequencyDurationTotalMonitored
Lectures442 per week1 hour44 
Practicals211 per week2 hours42 
Preparation and Reading114 
Total200 

Summative Assessment

Component: CourseworkComponent Weighting: 34%
ElementLength / DurationElement WeightingResit Opportunity
Practical work 100Yes
Component: ExaminationComponent Weighting: 66%
ElementLength / DurationElement WeightingResit Opportunity
Examination2 hours100Yes

Formative Assessment

Example exercises given through the course.

More information

If you have a question about Durham's modular degree programmes, please visit our FAQ webpages, Help page or our glossary of terms. If you have a question about modular programmes that is not covered by the FAQ, or a query about the on-line Undergraduate Module Handbook, please contact us.

Prospective Students: If you have a query about a specific module or degree programme, please Ask Us.

Current Students: Please contact your department.