Durham University
Programme and Module Handbook

Undergraduate Programme and Module Handbook 2012-2013 (archived)

Module COMP4071: THEORETICAL COMPUTER SCIENCE IV

Department: Computer Science

COMP4071: THEORETICAL COMPUTER SCIENCE IV

Type Open Level 4 Credits 20 Availability Not available in 2012/13 Module Cap None. 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

  • Topics to be selected from:
  • Algorithmic game theory.
  • Probabilistic algorithms.
  • Approximation algorithms.
  • Fixed-parameter algorithmics.
  • Interactive proofs.
  • Hardness of approximation and the PCP theorem.
  • Cryptography and zero knowledge proofs.
  • Relativised computation and natural proofs.
  • Circuit complexity.
  • Theory and practice: graph-theoretical methods for practical problems.

Learning Outcomes

Subject-specific Knowledge:
  • On completion of this module, students will be able to demonstrate:
  • an understanding of how the theory of computation is applied
  • an understanding of a variety of approaches to the algorithmic solution for hard problems
  • an 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 apply notions from the theory of computation
  • an ability to choose the best way to tackle hard computational problems
  • an ability to demonstrate hardness of computational problems
  • an ability to appreciate 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 futher 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 11 1 per 2 weeks 1 hour 11
preparation and reading 145
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 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