This is an archived handbook for a previous year. The current undergraduate and postgraduate handbooks can be viewed using the links above.
Undergraduate Handbook 2010-2011 (archived)
Module COMP2181: THEORY OF COMPUTATION
Department: Computer Science
COMP2181: THEORY OF COMPUTATION
| Type | Level | Credits | Availability | Module Cap | Location |
|---|---|---|---|---|---|
| Open | 2 | 20 | Available in 2010/2011 | None. | Durham |
Pre-requisites
- Formal Aspects of Computer Science (COMP1021)
Corequisites
- None.
Excluded Combinations
- 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
- Finite state machines and regular expressions.
- Context-free grammars and Push-Down Automata.
- Turing machines and the Church-Turing Thesis.
- Recursive and recursively enumerable languages.
- Chomsky hierarchy.
- Undecidability.
- Basic notions of algorithm measurement.
- A selection of algorithms covering, sorting, searching, string matching, data compression, graph theory,algebra and number theory.
- Design and analysis techniques such as divide-and-conquer, greedy algorithms, dynamic programming and backtracking.
- introduction to computational complexity covering P, NP and NP-complete.
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
Key Skills
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.
- Tutorials provide active engagement and feedback to the learning process.
- The end of year examinations assess the knowledge acquired and the ability to use this knowledge to solve problems.
Teaching Methods and Learning Hours
| Activity | Number | Frequency | Duration | Total Hours | Attendance Monitored |
|---|---|---|---|---|---|
| Lectures | 40 | 2 per week | 1 hour | 40 | |
| Tutorials | 2 | 1 hour | 2 | Yes | |
| Practicals | 20 | 1 per week | 2 hours | 40 | Yes |
| Preparation and Reading | 118 | ||||
| Total | 200 |
Summative Assessment
| Component | Component Weighting | Element | Length/Duration | Element Weighting | Resit Opportunity |
|---|---|---|---|---|---|
| Coursework | 34% | Practical work | 100% | ||
| Examination | 66% | Examination | 2 hours | 100% | Yes |
Formative Assessment
Example exercises given through the course. Additional revison lectures may be arranged in the modules lecture slots in the 3rd term.
Students who do not attend monitored activities shown under Teaching Methods
and Learning Hours, or who fail to complete the summative or formative
assessment(s) specified above, may be subject to the Academic Progress
procedures defined in the University's General Regulation V, and may be
required to leave the University.