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 COMP3341: ADVANCED THEORY OF COMPUTATION (20 CREDITS)
Department: Computer Science
COMP3341: ADVANCED THEORY OF COMPUTATION (20 CREDITS)
| Type | Level | Credits | Availability | Module Cap | Location |
|---|---|---|---|---|---|
| Open | 3 | 20 | Available in 2010/2011 | None. | Durham |
Pre-requisites
- (COMP2181 Theory of Computation) Or (Level 2 Maths modules which demonstrate to the satisfaction of the Computer Science Director of Undergraduate Studies that the student has met the learning outcomes associated with COMP2181)
Corequisites
- None.
Excluded Combinations
- Advanced Theory of Computation (40 credits) COMP3342.
Aims
- To equip students with the ability to use techniques and methods to efficiently solve fundamental problems in Computer Science and also to identify barriers to efficient solutions.
Content
- advanced algorithms: graphs and graph algorithms.
- probabilistic and randomised algorithms.
- approximation and heuristic algorithms.
- advanced computational complexity: core complexity classes.
- reductions.
- completeness.
- models of computation.
- Church-Turing thesis.
- unsolvability and unsolvable problems.
- Theory and practice: graph-theoretical methods for practical problems.
- ad hoc mobile networks.
- fundamental algorithmic problems such as routing and broadcasting.
Learning Outcomes
Subject-specific Knowledge
- Understand the inherent limitations of computation through the appreciation of two topic areas.
- Appreciate computational parameters and models of computation relevant to each of the two topics.
Subject-specific Skills
- Apply techniques and methods from the two topics to tackle the computational solution of fundamental problems in Computer Science.
- Demonstrate, for each of the two topics, that they have conducted research and self-study to further their knowledge beyond the taught material.
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 applications of the theory to practical examples.
- Homework problems identify areas where further independent research should be conducted.
- Summative examinations test the knowledge acquired and the students' ability to use this knowledge to solve complex problems.
Teaching Methods and Learning Hours
| Activity | Number | Frequency | Duration | Total Hours | Attendance Monitored |
|---|---|---|---|---|---|
| Lectures | 40 | 2 per week | 1 hours | 40 | |
| Preparation and Reading | 160 | ||||
| Total | 200 |
Summative Assessment
| Component | Component Weighting | Element | Length/Duration | Element Weighting | Resit Opportunity |
|---|---|---|---|---|---|
| Coursework | 30% | Practical work | 100% | No | |
| Examination | 70% | Examination | 1.5 hours | 100% |
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.