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.