Undergraduate Programme and Module Handbook 2015-2016 (archived)
Module COMP4071: THEORETICAL COMPUTER SCIENCE IV
Department: Computer Science
COMP4071: THEORETICAL COMPUTER SCIENCE IV
| Type | Open | Level | 4 | Credits | 20 | Availability | Available in 2015/16 | Module Cap | Location | Durham |
|---|
Prerequisites
- Theoretical Computer Science III
Corequisites
- None
Excluded Combination of Modules
- None.
Aims
- To introduce students to applications of theory of computation in economics.
- To give students a detailed knowledge of algorithmic solutions for computationally hard problems.
- To extend the students' knowledge of the latest advances in understanding hardness of computation.
Content
- There are four strands:
- Advanced Algorithms. Topics will be chosen from advanced data structures and hashing.
- Advanced topics in Complexity theory. Topics will be chosen from parameterized complexity, cryptography, circuit complexity, alternation and polynomial-time hierarchy and probabilistic complexity classes.
- Computational Complexity of Game Theory. Topics will be chosen from Nash equilibrium, complexity class PPAD and applications of game theory in computational complexity.
- Coding Theory. Topics will be chosen from error-correction codes and bounds on error correction.
Learning Outcomes
Subject-specific Knowledge:
- On completion of this module, students will be able to demonstrate:
- a comprehensive understanding of how the theory of computation is applied
- a critical evaluation of a variety of approaches to the algorithmic solution for hard problems
- a critical awareness of the latest advances in research on hardness of computation.
Subject-specific Skills:
- On completion of this module, students will be able to demonstrate:
- an ability to critically apply notions from the theory of computation
- an ability to choose and evaluate the best way to tackle hard computational problems
- an ability to demonstrate hardness of computational problems
- an ability to judge research on the cutting edge of the theory of computation.
Key Skills:
- On completion of this module, students will be able to demonstrate: a capacity for independent self-learning and research.
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.
- Homework problems identify areas where further independent research should be conducted.
- Summative assessments 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 | 44 | 2 per week | 1 hour | 44 | |
| problem classes | 8 | 4 and 4 in terms one and two | 1 hour | 8 | |
| preparation and reading | 148 | ||||
| Total | 200 |
Summative Assessment
| Component: Examination | Component Weighting: 66% | ||
|---|---|---|---|
| Element | Length / duration | Element Weighting | Resit Opportunity |
| Examination | 2 hours | 100% | No |
| Component: Coursework | Component Weighting: 34% | ||
| Element | Length / duration | Element Weighting | Resit Opportunity |
| Practical work | 100% | No | |
Formative Assessment:
Example formative exercises given during the course. Additional revision 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