Durham University
Programme and Module Handbook

Undergraduate Programme and Module Handbook 2007-2008 (archived)

Module COMP2181: THEORY OF COMPUTATION

Department: Computer Science

COMP2181: THEORY OF COMPUTATION

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

Prerequisites

  • Formal Aspects of Computer Science (COMP1021) AND Programming and Data Structures (COMP1082).

Corequisites

  • None.

Excluded Combination of Modules

  • None.

Aims

  • To introduce students to: important models of computation and how they are related.
  • fundamental notions of computation such as 'computable' and 'efficiently computable'.
  • and the design and analysis of efficient algorithms.

Content

  • Finite state machines and regular expressions.
  • Context-free grammars and Push-Down Automata.
  • Turing machines and the Church-Turing Thesis.
  • Recursive and recursively enumerable languages.
  • Chomsky hierarchy.
  • Undecidability.
  • Basic notions of algorithm measurement.
  • A selection of algorithms covering, sorting, searching, string matching, data compression, graph theory,algebra and number theory.
  • Design and analysis techniques such as divide-and-conquer, greedy algorithms, dynamic programming and backtracking.
  • introduction to computational complexity covering P, NP and NP-complete.

Learning Outcomes

Subject-specific Knowledge:
  • To have an understanding of different models of computation and their relevance to computer science.
  • To have an understanding of how algorithms can be used to solve fundamental problems within Computer Science.
Subject-specific Skills:
    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.
      • Problem classes through practicals provide assessment (both formative and summative) to guide students in the correct development of their knowledge and skills.
      • Tutorials provide active engagement and feedback to the learning process.
      • The end of year examinations assess the knowledge acquired and the ability to use this knowledge to solve problems.

      Teaching Methods and Learning Hours

      Activity Number Frequency Duration Total/Hours
      Lectures 38 2 per week 1 hour 38
      Tutorials 2 1 hour 2
      Practicals 19 1 per week 2 hours 38
      Preparation and Reading 122
      Total 200

      Summative Assessment

      Component: Coursework Component Weighting: 34%
      Element Length / duration Element Weighting Resit Opportunity
      coursework 100%
      Component: Examination Component Weighting: 66%
      Element Length / duration Element Weighting Resit Opportunity
      two-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