Undergraduate Programme and Module Handbook 2012-2013 (archived)
Module COMP3341: ADVANCED THEORY OF COMPUTATION (20 CREDITS)
Department: Computer Science
COMP3341: ADVANCED THEORY OF COMPUTATION (20 CREDITS)
| Type | Open | Level | 3 | Credits | 20 | Availability | Available in 2012/13 | Module Cap | None. | Location | Durham |
|---|
Prerequisites
- (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 Combination of Modules
- 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
- Students will study a selection from the following topics:
- Advanced algorithms: graphs and graph algorithms.
- Probabilistic and randomised algorithms.
- Approximation and heuristic algorithms.
- Advanced computational complexity: core complexity classes.
- Reductions.
- Completeness.
- Basic concept and computational issues in games
- Algorithms for and complexity of equilibria in games
- Computational auctions and mechanism design
- 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 | |
|---|---|---|---|---|---|
| Lectures | 40 | 2 per week | 1 hours | 40 | |
| Preparation and Reading | 160 | ||||
| Total | 200 |
Summative Assessment
| Component: Coursework | Component Weighting: 30% | ||
|---|---|---|---|
| Element | Length / duration | Element Weighting | Resit Opportunity |
| Practical work | 100% | No | |
| Component: Examination | Component Weighting: 70% | ||
| Element | Length / duration | Element Weighting | Resit Opportunity |
| 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.
■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University