Algorithms, Correctness and Efficiency - CO518

Location Term Level Credits (ECTS) Current Convenor 2017-18 2018-19
Canterbury Autumn
View Timetable
5 15 (7.5) DR SA Owens

Pre-requisites

CO520 and (CO325 or equivalent A-level Mathematics) are pre-requisites. CO523 is an alternative to these and may be taken as a co-requisite.

Restrictions

None

2017-18

Overview

Testing, specification, verification
  • Specifying test properties, and more general logical properties
  • Scaling testing
  • Pre- and post-conditions, Hoare Logic, loop invariants

  • Data and Algorithm Design
  • Dynamic data structures: trees, queues, heaps and priority queues;
  • Sorting and searching algorithms, both in their own right and as components of more complex algorithms;
  • Graph algorithms: depth and breadth-first search, union-find, minimal-cost spanning trees;

  • Estimation and efficiency
  • Informal estimation and approximate calculations;
  • Detailed analysis of the time complexity of some simple algorithms including best, worst and average behaviour;
  • Techniques for analysing and comparing the asymptotic behaviour of algorithms.
  • Details

    This module appears in:


    Contact hours

    30 lectures and 10 classes

    Method of assessment

    30% coursework, 70% exam

    Preliminary reading

    See the library reading list for this module (Canterbury)

    See the library reading list for this module (Medway)

    Learning outcomes

    Students who successfully complete this module will be able to:
    specify, test, and verify program properties
    analyse the time and space behaviour of simple algorithms
    use known algorithms to solve programming problems
    make informed decisions about the most appropriate data structures and algorithms to use when designing software

    University of Kent makes every effort to ensure that module information is accurate for the relevant academic session and to provide educational services as described. However, courses, services and other matters may be subject to change. Please read our full disclaimer.