Durham University
Programme and Module Handbook

Undergraduate Programme and Module Handbook 2007-2008 (archived)

Module COMP3342: ADVANCED THEORY OF COMPUTATION (40 CREDITS)

Department: Computer Science

COMP3342: ADVANCED THEORY OF COMPUTATION (40 CREDITS)

Type Open Level 3 Credits 40 Availability Available in 2007/08 Module Cap None. Location Durham

Prerequisites

  • Theory of Computation (COMP2181).

Corequisites

  • None.

Excluded Combination of Modules

  • Advanced Theory of Computation (Single) COMP3341.

Aims

  • The aim of the Advanced Theory of Computing module is to equip students with the ability to use techniques and methods to efficiency 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 appreciation of four topic areas.
  • Appreciate computational parameters and models of computation relevant to each of the four topics.
Subject-specific Skills:
  • Apply techniques and methods from the four topics to tackle the computational solution of fundamental problems in Computer Science.
  • Demonstrate, for each of the four 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 application 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 38 2 per week 2 hours 76
    Preparation and Reading 324
    Total 400

    Summative Assessment

    Component: Coursework Component Weighting: 30%
    Element Length / duration Element Weighting Resit Opportunity
    coursework 100%
    Component: Examination Component Weighting: 70%
    Element Length / duration Element Weighting Resit Opportunity
    three- hour examination 100%

    Formative Assessment:

    Example exercises given through the course.


    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